LeetCode Go — 2. Сложите два числа

задняя часть алгоритм
LeetCode Go — 2. Сложите два числа

Это 17-й день моего участия в Gengwen Challenge, Подробности о мероприятии см.:Обновить вызов

Для лучшего будущего придерживайтесь чистки зубовLeetCode!

тема

дать вам дване пустойСвязный список из двух неотрицательных целых чисел. Каждая из них согласнообратный порядокхранится таким образом, и каждый узел может хранить толькоодин номер.

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

Вы можете предположить, что ни одно число не начинается с 0, кроме числа 0.

Пример 1:

leetcode-add-two-numbers

输入：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 — Жестокий цикл

Идеи решения проблем

Во-первых, уточните порядок хранения двух чисел в связанном списке.обратный порядок, так что головной узел указывает на последнюю цифру каждого числа (то есть на одну цифру), тогда мы можем сравнить головные узлы двух связанных списков.ValДобавить, указав при этом головные узлы двух ссылок на их потомков соответственноNext.

Конечно, при добавлении нам также нужнонестипроблема, перенос равен(n1 + n2 + carry) / 10.

код

мы используемheadПредставляет головной узел выходного связанного списка,tailВсегда указывайте на конец выходного списка:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if head == nil {
            head = &ListNode{Val: sum}
            tail = head
        } else {
            tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
    }
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return
}

Результаты

执行用时：24 ms，在所有 Go 提交中击败了 10.96% 的用户
内存消耗：4.7 MB，在所有 Go 提交中击败了 22.11% 的用户

Анализ сложности

  • Временная сложность: O(max(m,n)), гдеmиnдлины двух связанных списков соответственно. Нам нужно обойти все позиции двух связанных списков, и для обработки каждой позиции требуется всего O(1) времени.
  • Пространственная сложность: O(1). Обратите внимание, что возвращаемое значение не учитывает сложность пространства.

Решение 2 — Рекурсия

Идеи решения проблем

Из решения 1 мы можем обнаружить, что каждый цикл должен добавлять два числа к одному и тому же биту и в то же время вычислять, что такое перенос, тогда мы можем написать рекурсивную функцию и передать каждый перенос в качестве параметра:

  • Рекурсивная функция возвращает узел после добавления двух чисел в один и тот же бит
  • рекурсивная функция вcarryноль и завершается, когда один или оба списка пусты

код

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    return add(l1, l2, 0)
}

func add(l1, l2 *ListNode, carry int) *ListNode {
    if l1 == nil && l2 == nil && carry == 0 {
        return nil
    }
    if l1 != nil && l2 == nil && carry == 0 {
        return l1
    }
    if l2 != nil && l1 == nil && carry == 0 {
        return l2
    }

    sum := carry
    if l1 != nil {
        sum += l1.Val
        l1 = l1.Next
    }
    if l2 != nil {
        sum += l2.Val
        l2 = l2.Next
    }
    sum, carry = sum%10, sum/10
    node := &ListNode{Val: sum}
    node.Next = add(l1, l2, carry)
    return node
}

Результаты

执行用时：16 ms，在所有 Go 提交中击败了 38.47% 的用户
内存消耗：4.7 MB，在所有 Go 提交中击败了 12.74% 的用户

Анализ сложности

  • Временная сложность: O(min(m,n)), гдеmиnдлины двух связанных списков соответственно. Рекурсия завершается, когда один или оба связанных списка пусты.
  • Сложность пространства: O (мин (m, n)).

ссылка на тему

2. Добавьте два числа

Категории