ПУТЕШЕСТВИЕ ПО РАЗРАБОТКЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Решение проблем: добавьте два числа

Как я практикую решение проблем в 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 и добавление

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

  1. Выполните цикл while для listNode1 и listNode2, пока оба списка не станут нулевыми.
  2. Получите значения listNode1 и listNode2, а затем добавьте значения.
  3. Если сложение больше 10, получите 1 и добавьте его для следующего узла так же, как на шаге 2.
  4. Добавьте прибавку к результату со значением в процентах на 10
  5. Создайте узел по значению на шаге 4 и добавьте узел в узел списка результатов
  6. Проверьте, существует ли значение на шаге 3, если да, создайте последний узел и добавьте узел в список результатов

Функция addTwoNumbers

Вызовите функцию в основном методе:

Временная сложность: O(n)

Пространственная сложность: O(n)

Вы можете увидеть полный код этого решения на Github.

Заключение

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

Рекомендации

Задача в этой статье от Leetcode (Добавить два числа).