天马网络 网站建设,免费自助建站系统平台 贴吧,做网站如何容易被百度抓取,wordpress清新主题文章目录 题目描述示例 解题思路 - 迭代法Go语言实现 - 迭代法算法分析 解题思路 - 模拟法Go语言实现 - 模拟法算法分析 解题思路 - 优化模拟法主要方法其他方法的考虑
题目描述
给出两个非空的链表用来表示两个非负的整数。其中#xff0c;它们各自的位数是按照逆序的方… 文章目录 题目描述示例 解题思路 - 迭代法Go语言实现 - 迭代法算法分析 解题思路 - 模拟法Go语言实现 - 模拟法算法分析 解题思路 - 优化模拟法主要方法其他方法的考虑
题目描述
给出两个非空的链表用来表示两个非负的整数。其中它们各自的位数是按照逆序的方式存储的并且它们的每个节点只能存储一位数字。 如果我们将这两个数相加起来则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外这两个数都不会以 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]解题思路 - 迭代法
我们可以遍历两个链表模拟数字相加的过程。需要注意的是如果两个链表的长度不同我们需要对较短的链表进行特殊处理。另外如果相加的结果大于等于10我们需要进行进位处理。
Go语言实现 - 迭代法
下面是使用Go语言实现的迭代法代码
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {dummyHead : ListNode{Val: 0}p, q, curr : l1, l2, dummyHeadcarry : 0for p ! nil || q ! nil {x : 0y : 0if p ! nil {x p.Valp p.Next}if q ! nil {y q.Valq q.Next}sum : carry x ycarry sum / 10curr.Next ListNode{Val: sum % 10}curr curr.Next}if carry 0 {curr.Next ListNode{Val: carry}}return dummyHead.Next
}算法分析
时间复杂度: O(max(m, n))其中 m 和 n 分别为两个链表的长度。空间复杂度: O(max(m, n))我们需要一个新链表来存储结果。 这个算法的时间复杂度和空间复杂度都是线性的与较长的链表长度相同。
除了迭代法之外还可以使用递归法来解决“两数相加”的问题。递归法的基本思想是将问题分解为更小的子问题即相加两个链表的当前节点然后递归地处理下一个节点。
解题思路 - 模拟法
通过链表的形式逐位计算两个数的和同时考虑进位的情况。从两个链表的头节点开始逐对节点相加将结果创建为新的链表节点。如果两个链表的长度不一致则将较短链表的剩余部分视为0进行处理。整个过程中我们需要维护当前的进位信息。
Go语言实现 - 模拟法
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {head : ListNode{0, nil} // 创建哑节点作为返回链表的头节点curr : headcarry : 0 // 初始化进位为0for l1 ! nil || l2 ! nil || carry 0 {sum : carry // 开始时将进位加入和中if l1 ! nil {sum l1.Val // 加上第一个链表的值l1 l1.Next // 移动到下一个节点}if l2 ! nil {sum l2.Val // 加上第二个链表的值l2 l2.Next}carry sum / 10 // 计算新的进位curr.Next ListNode{sum % 10, nil} // 创建新的节点存储和的个位数curr curr.Next // 移动到新创建的节点}return head.Next // 返回哑节点的下一个节点即结果链表的头节点
}
算法分析
时间复杂度: O(max(m,n))其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的最长长度。空间复杂度: O(max(m,n))。新链表的长度最多为 max(m,n) 1。
解题思路 - 优化模拟法
实际上上述模拟法已经是相对高效的解法了。在具体实现过程中进一步的优化空间不大。如果要优化主要是代码层面的简化和优化比如简化变量的使用减少不必要的操作等但算法本身的时间复杂度和空间复杂度已经达到了最优。
在这个问题中关键是理解如何逐位相加并处理进位。优化的空间更多的在于代码的可读性和简洁性上而不是算法复杂度的提升。
对于LeetCode题目2“两数相加”实际上存在的解决方案主要围绕着迭代和递归两种思路展开。由于题目的特性和限制解题方法相对固定主要是如何处理两个链表的逐位相加以及进位处理。
主要方法
迭代法这是最直观的方法通过遍历两个链表逐位计算和并处理进位。迭代法的优点是直观易懂实现简单是大多数情况下的首选方法。递归法递归法利用递归函数来逐位相加每一层递归处理一位。递归法的优点是代码更为简洁但对于理解和调试来说可能稍微复杂一些。递归的深度等于链表的长度因此对于非常长的链表可能会导致栈溢出。
其他方法的考虑
除了这两种方法实际上没有根本上不同的算法来解决这个特定的问题。其他的所谓“方法”往往是对上述两种方法的变体或优化例如
优化存储对于迭代法可以通过直接在较长的链表上进行修改来节省空间避免额外的空间分配。但这改变了输入数据可能并不总是可接受的。并行处理理论上如果链表足够长可以考虑将链表分成几部分并行处理每一部分的加法。然而这种方法在实践中很少使用因为它增加了实现的复杂性而且链表的遍历性质和计算机的内存访问模式使得并行化的效果并不明显。
