Насколько хорошо это работает?
Для этого эксперимента я буду давать подсказки 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, можно выполнить следующие действия:
- Инициализируйте переменную
count
значением 0. Эта переменная будет использоваться для хранения минимального количества символов, которые необходимо добавить в конец s. - Инициализируйте две переменные,
i
иj
, равными 0. Эти переменные будут использоваться для отслеживания текущей позиции в каждой из строк s и t соответственно. - Повторяйте символы в s и t, начиная с первого символа в каждой строке. В каждой итерации сравнивайте текущий символ в s с текущим символом в t.
- Если текущий символ в s совпадает с текущим символом в t, увеличьте как
i
, так иj
, чтобы перейти к следующему символу в каждой строке. - Если текущий символ в s отличается от текущего символа в t, увеличьте только
i
, чтобы перейти к следующему символу в s. - Повторяйте шаги 3–5, пока либо
i
не достигнет конца s, либоj
не достигнет конца t. - В конце итерации, если
j
достигло конца t, минимальное количество символов, которое необходимо добавить в конец s, равно 0, поскольку t уже является подпоследовательностью s. - Если
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:вот простой подход, который решает эту проблему с линейной временной и пространственной сложностью:
- Перебрать связанный список и сохранить значение каждого узла в массиве.
- Выполните итерацию по массиву справа налево и удалите каждый элемент, который меньше максимального значения, наблюдаемого на данный момент.
- Создать новый связанный список из измененного массива и вернуть заголовок связанного списка.
Вот реализация описанного выше подхода в 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:
- Две суммы. Это классическая задача Leetcode, в которой вам предлагается найти в массиве два числа, которые в сумме дают определенное целевое число. ChatGPT смог быстро решить эту проблему, предоставив пошаговое решение, которое включало создание карты для хранения индексов чисел в массиве, а затем итерацию по массиву, чтобы найти два числа, которые в сумме дают цель.
- Обратное целое число. В этой задаче вам нужно обратить целое число без использования каких-либо встроенных функций или библиотек. ChatGPT предоставил решение, включающее использование цикла while для перебора цифр целого числа, добавления каждой цифры к строке и последующего обращения строки в конце для получения инвертированного целого числа.
- Объединить два отсортированных списка. В этой задаче вам предлагается объединить два отсортированных связанных списка в один отсортированный связанный список. ChatGPT предоставил решение, включающее создание нового связанного списка, а затем повторение двух входных связанных списков, сравнение значений в каждом узле и добавление меньшего значения в новый связанный список.
Хотя ChatGPT может успешно решить многие проблемы с Leetcode, бывают случаи, когда проблему решить не удается. Например, ChatGPT не смог решить задачу Leetcode «Номер палиндрома», которая просит вас определить, является ли целое число палиндромом. Это связано с тем, что проблема связана со сложной логикой и требует глубокого понимания проблемы, что в настоящее время выходит за рамки возможностей ChatGPT.
В целом, ChatGPT — ценный инструмент для решения проблем с Leetcode, особенно когда речь идет о еженедельном конкурсе. Пошаговые решения и полезные советы сэкономят ваше время и силы, позволяя сосредоточиться на более сложных проблемах и улучшить свои навыки инженера-программиста или специалиста по данным.
Вот что я имею в виду, когда говорю, что это похоже на симулятор. Обратите внимание, как он симулирует, что ChatGPT не может решить «число палиндрома» просто потому, что я сделал подсказку, чтобы сказать, где он не удался. Я почти уверен, что в противном случае это быстро решило бы и этот вопрос.