Go算法实战 - 1.【两数相加LeetCode-2】递归解法

junedayday

发布于 2021-08-05 10:29:59

2600

发布于 2021-08-05 10:29:59

文章被收录于专栏：Go编程点滴

Leetcode-2 两数相加

原题链接 https://leetcode-cn.com/problems/add-two-numbers/

type ListNode struct {
    Val int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
}

为了能保证代码都能执行，我会贴出所有代码，重点会用注释着重说明。

递归实现的思路

简化问题

这道题的难点在于处理进位。那我们就先简化问题、把框架搭起来，看看先不考虑进位的大致代码怎么写的：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 先判断边界情况
    if l1 == nil && l2 == nil {
        return nil
    }

    var node = new(ListNode)
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val
        node.Next = addTwoNumbers(l1.Next, l2.Next)
    } else if l1 != nil {
        node.Val = l1.Val 
        node.Next = addTwoNumbers(l1.Next, l2)
    } else if l2 != nil {
        node.Val = l2.Val 
        node.Next = addTwoNumbers(l1, l2.Next)
    }

    return node
}

但这块代码有个问题- 当l1和l2都为空时，还会进入一次addTwoNumbers，导致最高位必定是0。

所以，我们需要保证最高位不要产生一个冗余，也就是l1和l2都为nil时，不要再进入addTwoNumbers函数。

修复最高位的问题

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var node = new(ListNode)
    // 这里l1和l2作为指针传递下去
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val
        l1, l2 = l1.Next, l2.Next
    } else if l1 != nil {
        node.Val = l1.Val 
        l1 = l1.Next
    } else if l2 != nil {
        node.Val = l2.Val
        l2 = l2.Next
    }

    // 如果都为空，无需继续处理
    if l1 == nil && l2 == nil {
        return node
    }

    // 继续处理下一个节点
    node.Next = addTwoNumbers(l1, l2)
    return node
}

递归函数增加进位参数carry

进位carry是一个在不同位中传递的参数，所以必须要加到函数签名中，所以我们得对递归函数进行改造。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(l1, l2, 0)
}

// 新的函数参数 carry
func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    var node = new(ListNode)
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val + carry
        l1, l2 = l1.Next, l2.Next
    } else if l1 != nil {
        node.Val = l1.Val + carry
        l1 = l1.Next
    } else if l2 != nil {
        node.Val = l2.Val + carry
        l2 = l2.Next
    } 

    var newCarry int
    if node.Val > 9 {
        node.Val = node.Val - 10
        newCarry = 1
    }

    if l1 == nil && l2 == nil && newCarry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(l1, l2, newCarry)
    return node
}

边界条件修复

到了这里，我们看似完成了功能，但还有个边界条件没有修复：引入进位后，当l1/l2为nil，carry为1时，我们很容易就修复了

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(l1, l2, 0)
}

func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    var node = new(ListNode)
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val + carry
        l1, l2 = l1.Next, l2.Next
    } else if l1 != nil {
        node.Val = l1.Val + carry
        l1 = l1.Next
    } else if l2 != nil {
        node.Val = l2.Val + carry
        l2 = l2.Next
    } else { 
        node.Val = carry // 修复进位的边界问题
    }

    var newCarry int
    if node.Val > 9 {
        node.Val = node.Val - 10
        newCarry = 1
    }

    if l1 == nil && l2 == nil && newCarry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(l1, l2, newCarry)
    return node
}

持续优化

首先，先明确一下优化的原则：

我并不是单纯地为了提升性能而去优化，而是更应该从全局入手，考虑代码的可读性和扩展性！

所以，下面的优化并不一定是性能最优的，但或多或少可能让你感受到代码的迭代升级。

A - 复用变量

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(l1, l2, 0)
}

func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    var node = new(ListNode)
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val + carry
        l1, l2 = l1.Next, l2.Next
    } else if l1 != nil {
        node.Val = l1.Val + carry
        l1 = l1.Next
    } else if l2 != nil {
        node.Val = l2.Val + carry
        l2 = l2.Next
    } else {
        node.Val = carry
    }

    if node.Val > 9 {
        node.Val = node.Val - 10
        carry = 1 // 复用carry变量
    } else {
        carry = 0
    }

    if l1 == nil && l2 == nil && carry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(l1, l2, carry)
    return node
}

删除newCarry变量，节省了内存。

虽然这点改进很小，但我想表达的重点是：**大家不要小看变量的复用，尤其是在一些递归调用的场景下，能节省大量的空间。**上面的l1与l2这两个指针也进行了变量的复用。

B - 增加位操作，去除if-else分支

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(l1, l2, 0)
}

func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    var node = new(ListNode)
    if l1 != nil && l2 != nil {
        node.Val = l1.Val + l2.Val + carry
        l1, l2 = l1.Next, l2.Next
    } else if l1 != nil {
        node.Val = l1.Val + carry
        l1 = l1.Next
    } else if l2 != nil {
        node.Val = l2.Val + carry
        l2 = l2.Next
    } else {
        node.Val = carry
    }

    carry, node.Val = node.Val/10, node.Val%10 // 引入位操作

    if l1 == nil && l2 == nil && carry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(l1, l2, carry)
    return node
}

C - 增加代码的扩展性（推荐）

在这个代码里，我们只支持2个ListNode的相加，就引入了4个if-else的分支，这就很难支持大量ListNode的扩展。

总体来说，我个人推荐这个解法，它的思路很清晰，也不会出现边界问题。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(l1, l2, 0)
}

func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    var node = new(ListNode)
    if l1 != nil {
        node.Val += l1.Val
        l1 = l1.Next
    }

    if l2 != nil {
        node.Val += l2.Val
        l2 = l2.Next
    }

    node.Val += carry
    carry, node.Val = node.Val/10, node.Val%10 // 引入位操作

    if l1 == nil && l2 == nil && carry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(l1, l2, carry)
    return node
}

实战化特性

在实际的项目中，我们会希望这个函数的扩展性能更好，例如支持多个输入参数。

引入不定参数的特性

我们进一步改造成不定参数形式的函数签名：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersWithCarry(0, l1, l2)
}

// 不定参数必须是最后一个函数签名
func addTwoNumbersWithCarry(carry int, nodes ...*ListNode) *ListNode {
    var node = new(ListNode)
    for k := range nodes {
        if nodes[k] != nil {
            node.Val += nodes[k].Val
            nodes[k] = nodes[k].Next
        }
    }

    node.Val += carry
    carry, node.Val = node.Val/10, node.Val%10 // 引入位操作

    // 判断所有node是否为空
    var isEnd = true
    for k := range nodes {
        if nodes[k] != nil {
            isEnd = false
            break
        }
    }
    if isEnd && carry == 0 {
        return node
    }

    node.Next = addTwoNumbersWithCarry(carry, nodes...)
    return node
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Go编程点滴微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度