ПУТЕШЕСТВИЕ ПО РАЗРАБОТКЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
Решение проблем: добавьте два числа
Как я практикую решение проблем в Leetcode
Обзор
Давайте продолжим решать проблемы в нашем путешествии по разработке программного обеспечения. В этой статье я предоставлю вам способ решения задачи «Сложи два числа» — средней сложности. Теперь давайте посмотрим на проблему и на то, как я ее решаю.
Проблема
Сложность: средняя
Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке, и каждый из их узлов содержит одну цифру. Добавьте два числа и верните сумму в виде связанного списка.
Вы можете предположить, что эти два числа не содержат начальных нулей, кроме самого числа 0.
Пример
Пример 1:
Ввод: l1 = [2,4,3], l2 = [5,6,4]
Вывод: [7,0,8]
Объяснение: 342 + 465 = 807.
Пример 2:
Ввод: l1 = [0], l2 = [0]
Вывод: [0]
Пример 3:
Ввод: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Вывод: [8,9,9,9,0,0,0,1]
Ограничения
- Количество узлов в каждом связанном списке находится в диапазоне [1, 100].
- 0 ‹= Node.val ‹= 9.
- Гарантируется, что список представляет собой число, не имеющее лидирующих нулей.
Анализ проблемы
- Давайте посмотрим на «два непустых связанных списка», это означает, что нас не будет волновать проверка регистра для пустого списка ввода.
- «Цифры хранятся в обратном порядке», как вы можете видеть в примере 1, если у нас есть число 342, это означает, что мы можем сначала получить число 2, затем число 4 и последнее число 3. .
- «Сложите два числа и верните сумму в виде связанного списка», это описывает наш результат как связанный список, а данные каждой заметки представляют собой сумму двух входных связанных списков. Вы можете обратиться к примерам более четко.
Как это решить
Решение: цикл while и добавление
Теперь давайте решим проблему прямым и наиболее эффективным решением. Он просто делает цикл для каждого узла и сравнивает его значение одно за другим. Затем мы можем добавить его в наш результат, давайте посмотрим шаг за шагом, как показано ниже:
- Выполните цикл while для listNode1 и listNode2, пока оба списка не станут нулевыми.
- Получите значения listNode1 и listNode2, а затем добавьте значения.
- Если сложение больше 10, получите 1 и добавьте его для следующего узла так же, как на шаге 2.
- Добавьте прибавку к результату со значением в процентах на 10
- Создайте узел по значению на шаге 4 и добавьте узел в узел списка результатов
- Проверьте, существует ли значение на шаге 3, если да, создайте последний узел и добавьте узел в список результатов
Функция addTwoNumbers
Вызовите функцию в основном методе:
Временная сложность: O(n)
Пространственная сложность: O(n)
Вы можете увидеть полный код этого решения на Github.
Заключение
В этой статье я думаю, что вы получите больше идей о том, как работают связанные списки. Возможно, решение немного сложное, но с объяснением кода, надеюсь, вы его поймете. Если у вас есть идеи получше, чем это решение, надеюсь, вы поделитесь ими. Я буду предоставлять вам все больше и больше статей о решении проблем. Если есть какие-либо проблемы, которые вы хотите решить, вы можете связаться с нами, и мы сможем решить их вместе. Надеюсь, вам понравится контент, спасибо!
Рекомендации
Задача в этой статье от Leetcode (Добавить два числа).