Насколько хорошо это работает?

Для этого эксперимента я буду давать подсказки ChatGPT на основе вопросов Leetcode, заданных в Еженедельном конкурсе 321 (который был выбран случайным образом).

Я прочитаю условия задачи на Leetcode и представлю их ChatGPT. Для каждой проблемы будет запущена новая ветка обсуждения, чтобы избежать помех от предыдущих проблем.

Если сгенерированный код не работает, я повторю попытку и изменю подсказку, чтобы получить лучшие результаты. Цель этого эксперимента — понять, насколько точен код и насколько он может быть полезен разработчику.

Давайте начнем.

(Обратите внимание, что я сделал снимки Leetcode в конце после эксперимента, перезапустив код)

Задача 1: найти ведущее целое число

XQ: Для данного положительного целого числа n найдите целое число x такое, что:

Сумма всех элементов от 1 до x включительно равна сумме всех элементов от x до n включительно.
Возвращает опорное целое число x. Если такого целого числа не существует, вернуть -1. Гарантируется, что для заданных входных данных будет не более одного сводного индекса.

Пример 1:
Входные данные: n = 8
Выходные данные: 6
Объяснение: 6 — это основное целое число, поскольку: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.
Пример 2:
Входные данные: n = 1
Выходные данные: 1
Объяснение: 1 — это основное целое число, поскольку: 1 = 1.
Пример 3:
Вход: n = 4
Выход: -1
Объяснение: Можно доказать, что такого целого числа не существует.

Ограничения:
1 ‹= п ‹= 1000

Напишите код для решения этой проблемы на Python

ChatGPT. Чтобы решить эту проблему, мы можем перебрать целые числа от 1 до n и проверить, равна ли сумма элементов от 1 до x сумме элементов от x до n для каждое целое число х. Если это так, мы можем вернуть x. В противном случае, если мы дойдем до конца итерации, не найдя ни одного целого числа x, удовлетворяющего заданному условию, мы можем вернуть -1, чтобы указать, что такого целого числа не существует.

Вот возможная реализация этого решения на Python:

def pivot_integer(n: int) -> int:
    # Compute the sum of all elements from 1 to n.
    total_sum = n * (n + 1) // 2

    # Iterate over the integers from 1 to n.
    for x in range(1, n + 1):
        # Compute the sum of all elements from 1 to x.
        left_sum = x * (x + 1) // 2
        # Compute the sum of all elements from x to n.
        right_sum = total_sum - left_sum

        # Check if the sum of the elements from 1 to x equals the sum of the elements from x to n.
        if left_sum == right_sum:
            return x

    # If we reach this point, it means that we didn't find any integer x that satisfies the given condition.
    return -1

Вердикт

Получилось ПОЧТИ правильно. Этот результат был похож на первую попытку. Единственное, чего он не понял, так это слова «включительно». Единственная ошибка в коде заключалась в том, что при вычислении нужной суммы нужно было добавлять x. (поскольку X включает обе стороны).

Проблема 2: добавление символов к строке для создания подпоследовательности

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

ChatGPT. Чтобы найти минимальное количество символов, которое нужно добавить в конец s, чтобы t стало подпоследовательностью s, можно выполнить следующие действия:

  1. Инициализируйте переменную count значением 0. Эта переменная будет использоваться для хранения минимального количества символов, которые необходимо добавить в конец s.
  2. Инициализируйте две переменные, i и j, равными 0. Эти переменные будут использоваться для отслеживания текущей позиции в каждой из строк s и t соответственно.
  3. Повторяйте символы в s и t, начиная с первого символа в каждой строке. В каждой итерации сравнивайте текущий символ в s с текущим символом в t.
  4. Если текущий символ в s совпадает с текущим символом в t, увеличьте как i, так и j, чтобы перейти к следующему символу в каждой строке.
  5. Если текущий символ в s отличается от текущего символа в t, увеличьте только i, чтобы перейти к следующему символу в s.
  6. Повторяйте шаги 3–5, пока либо i не достигнет конца s, либо j не достигнет конца t.
  7. В конце итерации, если j достигло конца t, минимальное количество символов, которое необходимо добавить в конец s, равно 0, поскольку t уже является подпоследовательностью s.
  8. Если j не достигло конца t, минимальное количество символов, которое необходимо добавить в конец s, равно количеству оставшихся символов в t, которое можно рассчитать как длину t минус значение j.

Вот пример кода, реализующего описанные выше шаги:

def minCharactersToAppend(s: str, t: str) -> int:
    count = 0
    i = 0
    j = 0

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1
    
    count = len(t) - j
    return count

Этот код вернет минимальное количество символов, которое необходимо добавить в конец s, чтобы t стало подпоследовательностью s.

Вердикт

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

Проблема 3: Удалить узлы из связанного списка

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

Пример 1:
Ввод: head = [5,2,13,3,8]
Вывод: [13,8]
Объяснение: нужно удалить 5 узлов. , 2 и 3. — Узел 13 находится справа от узла 5. — Узел 13 находится справа от узла 2. — Узел 8 находится справа от узла 3.

Пример 2:
Ввод: head = [1,1,1,1]
Вывод: [1,1,1,1]
Объяснение: Каждый узел имеет значение 1, поэтому никакие узлы не удаляются. Ограничения: количество узлов в данном списке находится в диапазоне [1, 105]. 1 ‹= Node.val ‹= 105

ChatGPT:вот простой подход, который решает эту проблему с линейной временной и пространственной сложностью:

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

Вот реализация описанного выше подхода в Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: ListNode) -> ListNode:
        # Store all nodes' values in an array
        arr = []
        curr = head
        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        # Iterate over the array from right to left, and remove each element that is smaller than the maximum value seen so far
        mx = -1
        i = len(arr) - 1
        while i >= 0:
            if arr[i] > mx:
                mx = arr[i]
            else:
                arr.pop(i)
            i -= 1
        
        # Construct a new linked list from the modified array and return the head of the linked list
        dummy = curr = ListNode(-1)
        for x in arr:
            curr.next = ListNode(x)
            curr = curr.next
        return dummy.next

Этот подход имеет временную сложность O(n) и пространственную сложность O(n), где n – количество узлов в связанном списке.

Вердикт

И снова получается почти правильно. В коде есть небольшая ошибка. При переборе массива справа налево условие if должно быть if arr[i] >= mx, а не просто «больше».

Я внес это изменение и отправил код, и он прошел все тесты. Это была вторая попытка. В первый раз я не включил примеры в подсказку, что не дало желаемого результата. Затем я начал новую тему со всем вопросом, который (почти) решил без проблем.

Задача 4: подсчет подмассивов с медианой K

XQ: Вам дан массив nums размера n, состоящий из различных целых чисел от 1 до n и положительного целого числа k. Возвращает количество непустых подмассивов в nums, медиана которых равна k.

ChatGPT: чтобы найти количество непустых подмассивов nums, у которых медиана равна k, мы можем перебрать все возможные подмассивы nums и проверить, равна ли медиана каждого подмассива до k.

Чтобы найти медиану подмассива, сначала нужно отсортировать подмассив в порядке возрастания. Если длина подмассива нечетна, медиана — это просто средний элемент отсортированного подмассива. Если длина подмассива четная, медиана — это среднее значение двух средних элементов отсортированного подмассива.

Получив медиану подмассива, мы можем проверить, равна ли она k, и увеличить значение счетчика, если это так. Перебрав все возможные подмассивы, мы можем вернуть в качестве результата окончательное значение счетчика.

Вот пример кода для поиска количества непустых подмассивов в nums, медиана которых равна k:

def count_medians(nums, k):
    n = len(nums)
    count = 0

    # Iterate over all possible subarrays of nums
    for i in range(n):
        for j in range(i+1, n+1):
            # Sort the current subarray in ascending order
            subarray = sorted(nums[i:j])

            # Find the median of the current subarray
            if len(subarray) % 2 == 0:
                median = (subarray[len(subarray)//2 - 1] + subarray[len(subarray)//2]) / 2
            else:
                median = subarray[len(subarray)//2]

            # Increment the counter if the median is equal to k
            if median == k:
                count += 1

    return count

Обратите внимание, что это решение имеет временную сложность O(n³), потому что существует n возможных начальных индексов для подмассивов, n возможных конечных индексов для подмассивов, и нам нужно отсортировать каждый подмассив, который занимает O(n log n ) время. Это может оказаться недостаточно эффективным для больших входных данных, поэтому нам может потребоваться найти более эффективное решение.

Вердикт

Подход грубой силы, предложенный ChatGPT, почти правильный. Требуется изменить только 1 строку кода.

# Find the median of the current subarray
if len(subarray) % 2 == 0:
    median = subarray[len(subarray)//2 - 1]

Вместо использования фактической формулы это дается как условие в вопросе. Однако этот код не оптимизирован и давал ограничение по времени, превышающее ошибку в Leetcode.

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

Окончательный вердикт

  • Он дал удовлетворительные ответы на 3/4 вопросов еженедельного конкурса, что весьма впечатляет. Это делает его лучше, чем многие настоящие конкурсанты.
  • Как разработчик с предварительными знаниями, время, чтобы прийти к рабочему решению, было довольно быстрым. Обычно задача, на решение которой у меня ушло бы 10 минут, теперь решается всего за 2–3 минуты.
  • ChatGPT сам по себе может быть не очень полезен при решении сложных проблем, если пользователь не добавит свои знания и ценность, чтобы помочь ему решить проблему.
  • Нет, это не отнимет у вас работу. Это как личный помощник, который помогает вам программировать в 10 раз быстрее.
  • Нужно помнить о проверке правильности ответов, которые он дает, поскольку они кажутся ненадежными как источник истины.
  • Объяснения, которые он дает алгоритмам, заставляют задуматься и могут помочь разработчикам с их интуицией.
  • Я нахожу ChatGPT больше похожим на симулятор. Он имитирует вещи на связном языке. Это довольно хорошо с соединением точек и узоров, но, вероятно, не понимает, что это значит.

Что все это означает для сообщества разработчиков и продвижения соревнований по программированию?

Вот мой текущий результат.

Из того, что я видел, ChatGPT поднимает планку для нижнего уровня набора навыков. Предположим, что у каждого есть уровень навыка от 0 до 100. С ChatGPT нижний уровень, вероятно, повышается до 30. Теперь у каждого есть уровень навыка от 30 до 100. В конце концов, это все еще равные условия, когда каждый имеет доступ к это.

Возможно, это поможет новичку стать в 10 раз эффективнее. Тем не менее, это может быть 100-кратным увеличением для эксперта в предметной области, поскольку они понимают вещи, чтобы лучше подтолкнуть ChatGPT и объединить идеи, чтобы достичь того, чего они хотят. Они также будут быстро выявлять ошибки и исправлять их.

Почтовые кредиты

Давайте сделаем вещи немного мета: P

XQ: Напишите в блоге статью «Решение еженедельного конкурса Leetcode с помощью ChatGPT». Приведите несколько примеров того, как ChatGPT успешно решает вопросы Leetcode. Покажите, где ChatGPT также не решает проблему.

ChatGPT: если вы инженер-программист или специалист по данным, скорее всего, вы знакомы с Leetcode, популярной платформой для практики кодирования и решения алгоритмических задач. Одним из основных моментов использования Leetcode является еженедельный конкурс, в котором пользователи могут проверить свои навыки против других пользователей и побороться за призы.

Решение проблем с Leetcode может быть сложной и трудоемкой задачей, особенно когда речь идет о еженедельном конкурсе. Вот где ChatGPT приходит на помощь. ChatGPT — это чат-бот на основе искусственного интеллекта, который может помочь вам решить проблемы с Leetcode в режиме реального времени, предоставляя вам пошаговые решения и полезные советы.

Вот несколько примеров того, как ChatGPT успешно решает вопросы Leetcode:

  1. Две суммы. Это классическая задача Leetcode, в которой вам предлагается найти в массиве два числа, которые в сумме дают определенное целевое число. ChatGPT смог быстро решить эту проблему, предоставив пошаговое решение, которое включало создание карты для хранения индексов чисел в массиве, а затем итерацию по массиву, чтобы найти два числа, которые в сумме дают цель.
  2. Обратное целое число. В этой задаче вам нужно обратить целое число без использования каких-либо встроенных функций или библиотек. ChatGPT предоставил решение, включающее использование цикла while для перебора цифр целого числа, добавления каждой цифры к строке и последующего обращения строки в конце для получения инвертированного целого числа.
  3. Объединить два отсортированных списка. В этой задаче вам предлагается объединить два отсортированных связанных списка в один отсортированный связанный список. ChatGPT предоставил решение, включающее создание нового связанного списка, а затем повторение двух входных связанных списков, сравнение значений в каждом узле и добавление меньшего значения в новый связанный список.

Хотя ChatGPT может успешно решить многие проблемы с Leetcode, бывают случаи, когда проблему решить не удается. Например, ChatGPT не смог решить задачу Leetcode «Номер палиндрома», которая просит вас определить, является ли целое число палиндромом. Это связано с тем, что проблема связана со сложной логикой и требует глубокого понимания проблемы, что в настоящее время выходит за рамки возможностей ChatGPT.

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

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