Leetcode — это онлайн-платформа для проверки и улучшения ваших навыков и знаний в области кодирования. Он особенно часто используется в качестве подготовки к собеседованиям разработчиков. OpenAI’s ChatGPT не нуждается в представлении — большинство из вас видели фрагменты его разговоров на разные темы. Нас интересует одна конкретная тема — способность ChatGPT понимать язык программирования.

Проблемы программирования и искусственный интеллект с навыками программирования — вы можете видеть, к чему все идет. Решение проблем с Leetcode с помощью ChatGPT — интригующая тема, но, в конечном счете, она сводит на нет цель обучения навыкам программирования. Тем не менее, если вам интересно использовать ChatGPT для решения задачи, на github есть несколько статей на среде или подборка решений, сгенерированных ИИ. Эта статья о другом.

Как вы можете использовать ChatGPT не для того, чтобы обмануть задачу, а чтобы помочь вам узнать больше о задачах Leetcode и быстрее совершенствоваться? (TLDR: да, перейдите к главе Пример Leetcode)

Анализ кода

Вы только что потратили часы, решая задачу по кодированию на Leetcode или во время интервью, и вы спрашиваете себя… «Оптимальный ли это подход? Должно быть, верно?

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

Первый шаг — определить неоптимальный код в вашем решении. Здесь мы можем использовать ChatGPT — анализ производительности кода. Давайте попробуем это на простом примере для тестирования ИИ.

Пример 1:

Подсказка: Это оптимальный способ поиска максимума списка чисел в Python?

def find_maximum(lst):
    return sorted(lst)[-1]

Ответ: Это один из способов найти максимум списка чисел в Python, но это не самый оптимальный способ. Функция sorted создает новый список, занимающий дополнительную память. Более эффективным решением будет использование встроенной функции max, например:

def find_maximum(lst):
    return max(lst)

Это позволит найти максимальный элемент в списке за линейное время без создания нового списка. Кроме того, вы также можете использовать встроенный в Python метод heapq.nlargest для получения N самых больших элементов из списка с временной сложностью O(n log k), где k — количество самых больших элементов, которые вы хотите получить.

import heapq
def find_maximum(lst):
    return heapq.nlargest(1, lst)[0]

Мы видим, что ИИ начинает с правильного решения, используя встроенный max , и это хорошо. Объясняет, что операция max линейна во времени, и это здорово. И предлагает использовать метод heapq.nlargest, где мы видим, как ИИ просто изгибается над нами.

Пример 2

В более сложном коде мы хотим знать, где именно находится неоптимальная строка/часть. В этом примере мы просим проанализировать производительность тремя разными способами, чтобы вычислить количество букв «А» в строке.

Подсказка: Проанализируйте временную и пространственную сложность этой функции Python построчно. Ввод представляет собой список символов, и функция должна найти количество вхождений символа «A».

def counter(input):
a = {x: input.count(x) for x in input}.get(“A”) 
b = Counter(input).get(“A”) 
c = sum(1 for _ in filter(lambda x: x==”A”, input)) 
return a,b,c

Ответ:

  1. a = {x: input.count(x) for x in input}.get("A"): Эта строка создает словарь с использованием понимания словаря, где ключи — это элементы входного списка, а значения — количество вхождений каждого элемента во входном списке. Метод input.count(x) имеет временную сложность O(n), где n — длина входного списка, поэтому общая временная сложность этой строки равна O(n^2), поскольку необходимо дважды перебрать входной список. Он также создает словарь, который занимает дополнительное место. Метод .get("A") имеет временную сложность O(1), поскольку он обращается к значению в словаре по его ключу.
  2. b = Counter(input).get("A"): в этой строке класс collections.Counter используется для создания объекта, похожего на словарь, который подсчитывает количество вхождений элементов в итерируемом объекте. Временная сложность этой строки равна O(n), где n — длина входного списка, потому что необходимо выполнить итерацию по входному списку один раз, чтобы подсчитать вхождения каждого элемента. Метод .get("A") имеет временную сложность O(1), поскольку он обращается к значению в словаре по его ключу.
  3. c = sum(1 for _ in filter(lambda x: x=="A", input)): в этой строке используется генераторное выражение с функциями filter и sum. Функция filter имеет временную сложность O(n), а функция sum имеет временную сложность O(n), поэтому общая временная сложность этой строки равна O(n), где n — длина входного списка.

Четкий и корректный анализ производительности всех 3-х подходов. Он не только говорит нам, какой подход более эффективен, но и пытается объяснить, почему. При первом подходе общая сложность составляет O(n²), и это объясняется тем, что input.count O(n) повторяется на каждой итерации для каждого n. Третий подход — использование итераторов — использование меньшего пространства, о чем также может упомянуть ChatGPT.

Примеры обещают, что мы можем использовать ChatGPT для анализа нашего кода и даже предоставлять построчные пояснения. Оба они важны, когда мы хотим найти неоптимальные строки в нашем коде для задачи Leetcode. Мы хотим знать, что не так и где (какая строка). Итак, после этого простого примера мы должны быть готовы к примеру с Leetcode.

Пример Литкода

Можем ли мы использовать ChatGPT для анализа наших решений проблем Leetcode и быстрее учиться? Сделаем что-то похожее на приведенные выше примеры, но с вызовом Leetcode — Реорганизовать строку. Проблема состоит в том, чтобы переставить символы заданной строки так, чтобы любые два соседних символа не совпадали. Например, переставьте строку aab в aba.

Мы предложили решение, но является ли оно самым оптимальным решением? Вероятно, нет, так как производительность этого решения составила всего 41 %. Где мы ошиблись? Что нужно изменить? Что ChatGPT думает о нашем решении?

Подсказка: Проанализируйте временную и пространственную сложность этого решения построчно. Это решение проблемы: для заданной строки s переставьте символы s так, чтобы любые два соседних символа не совпадали. Возвращает любую возможную перестановку s или возвращает «», если это невозможно.

def reorganizeString(s: str) -> str:
    N = len(s)
    cnt = Counter(s)
    ## feasibility
    common = cnt.most_common(1)[0][0]
    if cnt[common] * 2 - 1 > N :
        return ""
        
    res = [common] * N
    cnt.update({common:-1})
    for i in range(1,N):
        top2 = cnt.most_common(2)
            
        if top2[0][0] != res[i-1]:
            res[i] = top2[0][0]
            cnt.update({top2[0][0] : -1})
        else:
            res[i] = top2[1][0]
            cnt.update({top2[1][0] : -1})
    return "".join(res)

Ответ: Временная сложность этого решения равна O(n log n), а пространственная сложность — O(n).

  1. Первая строка, N = len(s), имеет временную сложность O(1) и пространственную сложность O(1).
  2. Во второй строке, cnt = Counter(s), используется класс Counter с временной сложностью O(n) и пространственной сложностью O(n) для создания словаря, подсчитывающего количество вхождений каждого символа в строку.
  3. Третья строка, common = cnt.most_common(1)[0][0], использует метод most_common() с временной сложностью O(n log n) и пространственной сложностью O(n) для поиска наиболее часто встречающегося символа в строке.
  4. Четвертая строка, if cnt[common] * 2 - 1 > N:, имеет временную сложность O(1) и пространственную сложность O(1).
  5. Пятая строка, res = [common] * N, имеет временную сложность O(n) и пространственную сложность O(n).
  6. Шестая строка, cnt.update({common:-1}), обновляет количество наиболее распространенных символов на -1 и имеет временную сложность O(1) и пространственную сложность O(1).
  7. Седьмая строка, for i in range(1, N), представляет собой цикл for, который будет повторяться N-1 раз с временной сложностью O(n).
  8. Восьмая строка, top2 = cnt.most_common(2), использует метод most_common() с временной сложностью O(n log n) и пространственной сложностью O(n) для поиска наиболее часто встречающихся символов в строке.
  9. Девятая строка, if top2[0][0] != res[i-1]:, имеет временную сложность O(1) и пространственную сложность O(1).
  10. Десятая строка, res[i] = top2[0][0], имеет временную сложность O(1) и пространственную сложность O(1).
  11. Одиннадцатая строка, cnt.update({top2[0][0]: -1}), обновляет количество наиболее распространенных символов на -1 и имеет временную сложность O(1) и пространственную сложность O(1).
  12. Двенадцатая строка, res[i] = top2[1][0], имеет временную сложность O(1) и пространственную сложность O(1).
  13. Тринадцатая строка, cnt.update({top2[1][0]: -1}), обновляет количество наиболее распространенных символов на -1 и имеет временную сложность O(1) и пространственную сложность O(1).
  14. Четырнадцатая строка, return "".join(res), имеет временную сложность O(n) и пространственную сложность O(n).

В целом временная сложность этого решения во многом определяется двойным использованием метода most_common(), который имеет временную сложность O(n log n). Сложность пространства составляет O(n) из-за использования класса Counter и списка разрешений.

Теперь мы знаем, какая часть обходится нам так дорого — метод most_common(). Мы не только полагаемся на него, но и вызываем его внутри цикла (что было упущено ChatGPT). Это объясняет наш плохой рейтинг производительности.

Но как улучшить решение? Если бы только был кто-то, кто мог бы помочь…

Подскажите: как бы вы улучшили данное кодовое решение?

Ответ:Есть несколько способов улучшить данное кодовое решение:

  1. Вместо того, чтобы дважды использовать метод most_common(), который имеет временную сложность O(n log n), вы можете использовать приоритетную очередь (кучу) для отслеживания символов и их количества в порядке убывания. Это будет иметь временную сложность O(n log k), где k — количество уникальных символов в строке, которое обычно намного меньше, чем n.
  2. Вместо перебора символов в строке можно использовать жадный подход для построения переупорядоченной строки. Начиная с самого распространенного символа, вы можете чередовать следующий по распространенности символ со вторым по частоте символом и так далее. Это будет иметь временную сложность O(n) и пространственную сложность O(n).
  3. Вместо использования метода update() для уменьшения счетчика символов можно использовать отдельные методы heap или priority_queue для хранения счетчиков каждого символа. Это устранит необходимость обновления счетчиков и улучшит временную сложность алгоритма.
  4. Вы также можете проверить, меньше ли длина строки 2, и в этом случае вернуть строку как есть, потому что перестановка невозможна.
  5. Вы также можете добавить проверку на ввод пустой строки и в этом случае возвращать « ».

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

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

Мы воспользовались вторым советом и переработали решение. Теперь мы строим результирующую строку, начиная с самого распространенного символа. Однако мы больше не используем метод most_common(), который сортирует весь словарь, и нам нужен только максимум. Сначала мы помещаем самый распространенный символ на каждую четную позицию, затем продолжаем до конца с любым символом. Достигнув N, мы делаем еще один цикл, но на этот раз заполняем нечетные позиции.

def reorganizeString(s: str) -> str:
    N = len(s)
    counter = Counter(s)
    common, max_count = max(counter.items(), key=lambda x: x[1])

    if max_count * 2 - 1 > N :
        return ""

    res = [None] * N
    for i in range(max_count):
        res[2*i] = common
    del counter[common] #already done character

    i = 2 * max_count
    for ch, count in counter.items():
        for _ in range(count):
            if i >= N:
                i=1
            res[i] = ch
            i += 2
    return "".join(res)

Благодаря совету ChatGPT мы смогли понять свои ошибки и учиться на них. Мы избежали дорогостоящих операций и даже переработали подход на основе второго предложения по улучшению. Это решение кажется оптимальным, так как наш ранг теперь намного выше! Обратите внимание, что теперь мы превзошли 99% других заявок по сравнению с 41%, которые у нас были раньше.

При этом помните об ограничениях ChatGPT. Иногда он может с уверенностью ответить неверной информацией, поскольку его целью является диалог, а не всезнающая сущность. Во время моих экспериментов ChatGPT часто предлагал неверные решения проблемы и в большинстве случаев нуждался в доработках. Что, кажется, работает лучше, так это задавать более простые вопросы и предоставлять больше данных — например. спросите о сложности вашего кода.

Как я уже говорил, тот факт, что ChatGPT может решать такие задачи, великолепен. То, что он может анализировать ваше решение построчно и объяснять временную сложность — удивительно. И то, что вы можете просто спросить, что можно улучшить (и ответ будет точным с первой попытки без каких-либо модификаций подсказки), просто сногсшибателен. Чтобы закончить на более философской ноте, не пытайтесь использовать ChatGPT для «взлома системы» — например. решить задачу для вас и победить цель задачи, но используйте ChatGPT, чтобы улучшить себя!