Типичные ошибки
в решениях

Категория

Отладка

Уровень

Средний

Опирается на

Главы 8.4–8.8

Зачем это знать

Находить ошибку по прогону и тестам

§1Как читать ошибочный прогон

В каждом разделе два пошаговых прогона подряд. Над первым стоит красная метка «ошибочная версия», над вторым — зелёная «исправленная версия». Оба получены запуском кода на одном и том же входе, поэтому их можно идти параллельно, шаг за шагом, и найти первый шаг, на котором они расходятся. Подписи к шагам описывают, что делает строка, и не оценивают её.

Ошибку в прогоне ищут так:

1. Вспомнить инвариант функции: что должно быть верно перед каждым шагом. Для задачи 1 — «если пара есть, она внутри участка с i по j».
2. Прокрутить ошибочный прогон до конца и сравнить результат с ожидаемым.
3. Идти по шагам с начала и после каждого проверять инвариант.
4. На первом шаге, где инвариант нарушен, посмотреть строку кода, которая выполнилась прямо перед ним. Ошибка в ней.

В коде над прогонами ошибочная строка выделена красным, исправленная — зелёным.

§2Один товар дважды

Пара в задаче 1 — это два разных товара, поэтому условие цикла в pair_sum строгое: i < j. В ошибочной версии вместо него стоит i <= j. Разница проявляется только тогда, когда указатели сходятся на одном элементе: верная версия на этом заканчивает цикл, ошибочная выполняет его ещё раз.

    i, j = 0, len(prices) - 1
    while i <= j:         # ошибочная версия
    while i < j:          # исправленная версия

Вход для обоих запусков — [100, 250, 600], цель 500. Пары с такой суммой в списке нет, верный ответ — None.

Первые два хода совпадают с верной версией: исключается 600, потом 100. На шаге 12 оба указателя стоят на индексе 1, и условие 1 <= 1 истинно. На шаге 13 функция складывает цену 250 саму с собой, получает 500 и возвращает (1, 1) — один товар дважды.

В исправленной версии на шаге 12 проверяется 1 < 1. Условие ложно, цикл заканчивается, и функция возвращает None. На большинстве входов разницы между версиями не видно: пара находится раньше, чем указатели сойдутся. Поэтому для этой ошибки нужен вход, где цена одного товара равна половине цели.

§3Указатель сдвигается не в ту сторону

Правило задачи 1 такое: если сумма меньше цели, сдвигается i, если больше — j. В ошибочной версии ветки перепутаны. Синтаксических ошибок в коде нет, Python выполняет его без исключений, и неверен только ответ.

        if s < target:
            j -= 1             # ошибочная версия
            i += 1             # исправленная версия
        else:
            i += 1             # ошибочная версия
            j -= 1             # исправленная версия

Вход — каталог из главы 8.4: [300, 450, 700, 900, 1200, 1500], цель 1600. Ответ (2, 3): 700 + 900.

Расхождение начинается на шаге 6. Сумма 300 + 1500 = 1800 больше цели, и по правилу нужно исключить самую дорогую цену 1500. Ошибочная версия исключает 300. Цена 300 в ответ не входит, поэтому после этого шага инвариант ещё верен, хотя правило нарушено. Дальше ошибка повторяется на каждом ходе: левая цена становится дороже, и сумма уходит от цели всё дальше — 1950, 2200, 2400, 2700. На шаге 16 исключается 700, и пара (2, 3) уже не может быть найдена — инвариант нарушен. Функция возвращает None.

На шаге 6 исправленная версия сдвигает j и исключает 1500. Дальше сумма каждый раз приближается к цели: 1500, 1650, 1350, 1600. На шаге 25 пара найдена.

§4Запись вместо обмена

В move_zeros ненулевое число меняется местами с элементом в позиции w. В ошибочной версии вместо обмена стоит запись nums[w] = nums[r], как в задаче 2. В задаче 2 такая запись верна: после цикла хвост списка обрезается, и то, что в нём осталось, не важно. Здесь хвост не обрезается, длина списка не меняется, и всё, что осталось в хвосте, попадает в ответ.

        if nums[r] != 0:
            nums[w] = nums[r]                     # ошибочная версия
            nums[w], nums[r] = nums[r], nums[w]   # исправленная версия
            w += 1

Вход — [0, 4, 0, 0, 7, 2], ожидаемый результат [4, 7, 2, 0, 0, 0].

На шаге 6 число 4 копируется из позиции 1 в позицию 0. Ноль из позиции 0 пропадает, а в позиции 1 остаётся вторая копия 4. Инвариант «в nums[w:r] только нули» нарушен уже здесь: на шаге 8 w = 1, r = 2, и в зоне nums[1:2] стоит 4. С числами 7 и 2 происходит то же самое, и результат — [4, 7, 2, 0, 7, 2]: нулей стало меньше, 7 и 2 повторились.

На шаге 6 исправленная версия меняет 0 и 4 местами: ноль переезжает в позицию 1, туда, откуда прочитано число. После каждого обмена в зоне между w и r стоят только нули, и результат — [4, 7, 2, 0, 0, 0].

§5Сравнение с соседом справа

В dedup_sorted прочитанный элемент сравнивается с последним записанным ids[w - 1]. Есть и другой способ найти повторы: оставлять элемент, если он отличается от соседа справа ids[r + 1]. У последнего элемента соседа справа нет, поэтому цикл в такой версии идёт только до предпоследнего индекса. Из-за этого последний элемент не записывается никогда.

    w = 0
    for r in range(len(ids) - 1):
        if ids[r] != ids[r + 1]:
            ids[w] = ids[r]
            w += 1
    del ids[w:]

Вход — [101, 101, 102, 105], ожидаемый результат — список [101, 102, 105] и ответ 3.

Значения 101 и 102 записываются верно. На шаге 12 цикл заканчивается на r = 2: range(len(ids) - 1) выдаёт индексы 0, 1, 2. Элемент ids[3] = 105 не прочитан, и результат — [101, 102]. Это ошибка на единицу из занятия 7: элементов n, а пар соседей n − 1, и цикл по парам не доходит до последнего элемента. На списке из одного элемента цикл не выполнится ни разу:

>>> ids = [7]
>>> dedup_bug(ids)
0
>>> ids
[]

Исправленная версия — та, что в главе 8.7. Первый элемент остаётся всегда, цикл читает индексы с 1 до последнего, и на шаге 10 значение 105 сравнивается с последним записанным 102. Последний элемент обрабатывается так же, как остальные. Версию с соседом справа можно спасти, если после цикла отдельно записать последний элемент, но тогда в коде появляется особый случай, которого в сравнении с ids[w - 1] нет.

§6Длина серии одной строкой

В compress длина серии записывается по цифрам: для серии из 12 символов — сначала '1', потом '2', каждая цифра в свой элемент списка. В ошибочной версии вся длина записывается одним элементом str(count). Пока серии короче десяти символов, разницы нет: у однозначного числа одна цифра, и строка из неё — один символ.

        if count > 1:
            chars[w] = str(count)     # ошибочная версия
            w += 1
            for d in str(count):      # исправленная версия
                chars[w] = d
                w += 1

Вход — серия из двенадцати символов x. Ожидаемый результат — ['x', '1', '2'] и длина 3. Первые 34 шага в обоих прогонах одинаковые: внутренний цикл двигает r до конца серии, затем записывается символ 'x' и считается длина серии.

На шаге 35 в позицию 1 записывается строка '12' — два символа в одном элементе. Функция возвращает 2, список — ['x', '12']. Условие LeetCode 443 требует, чтобы каждый элемент был одним символом, поэтому такой ответ неверен.

В исправленной версии на шагах 35–40 цикл for d in str(count) выполняется дважды: '1' встаёт в позицию 1, '2' — в позицию 2. Функция возвращает 3.

§7Сводка ошибок

В таблице собраны ошибки этой главы и ошибка с неотсортированным входом из главы 8.5. По симптому в первом столбце находят строку кода, в которой искать ошибку, и вход, на котором она видна.

§8Найдите ошибку

В каждом вопросе — функция с ошибкой, которая проходит часть тестов. Выберите вход, на котором она даёт неверный ответ.

def pair_sum(prices, target):
    i, j = 0, len(prices) - 1
    while i < j:
        s = prices[i] + prices[j]
        if s == target:
            return (i, j)
        if s < target:
            i += 1
        else:
            j -= 1
            i += 1
    return None

def dedup_sorted(ids):
    if not ids:
        return 0
    w = 1
    for r in range(1, len(ids)):
        if ids[r] != ids[w - 1]:
            ids[w] = ids[r]
            w += 1
    return w