两数相加题目和测试地址: https://leetcode-cn.com/problems/add-two-numbers/
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输出:7 -> 0 -> 8
原因:342 + 465 = 807
最初实现绕了个弯,先把链表转为数字,数字相加后在转换为链表,这其中遇到了越界问题于是又手写了个大数相加函数,这样想来自然也快不起来,先展示下最初代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
num1 := BuildListSum(l1)
num2 := BuildListSum(l2)
numResult := AddTwoString(num1, num2)
//fmt.Println(numResult)
return BuildSumList(numResult)
}
func BuildListSum (listNote *ListNode) string {
num1 := ""
i := 0
for e := listNote; e != nil; e = e.Next {
num1 = fmt.Sprintf("%v%v", e.Val, num1)
i++
}
return num1
}
func BuildSumList(num string) *ListNode {
var listNote *ListNode
count := len(num)
for i := 0; i < count; i++ {
//fmt.Println(numString[i:i+1])
n,_ := strconv.Atoi(num[i:i+1])
if listNote == nil {
listNote = &ListNode{n, nil}
} else {
listNote = &ListNode{n, listNote}
}
}
return listNote
}
func AddTwoString(num1, num2 string) string {
result := ""
if len(num1) ==0 && len(num2) ==0 {
return "0"
}
if len(num2) > len(num1) {
tmp := num1
num1 = num2
num2 = tmp
}
needInc := 0
length1 := len(num1) -1
length2 := len(num2) - 1
for i := 0; i <= length2; i++ {
tmp1 := num1[length1-i] - '0'
tmp2 := num2[length2-i] - '0'
tmpSum := int(tmp1) + int(tmp2) + needInc
if tmpSum >= 10 {
needInc = 1
} else {
needInc = 0
}
c3 := tmpSum % 10 + '0'
result = fmt.Sprintf("%c%s",c3,result)
}
leftLength := length1 - length2
for leftLength > 0 {
c1 := num1[leftLength-1]-'0'
sum := int(c1) + needInc
if sum >= 10 {
needInc = 1
} else {
needInc = 0
}
c3 := (sum %10) + '0'
result = fmt.Sprintf("%c%s",c3,result)
leftLength--
}
if needInc == 1 {
result = fmt.Sprintf("1%s",result)
}
return result
}
执行用时 :20 ms, 在所有 golang 提交中击败了34.31%的用户
内存消耗 :6.1 MB, 在所有 golang 提交中击败了5.17%的用户
后面看到其他人的时间和内存都很小,才发现自己绕了一大圈,不需要转成数字,直接使用链表中的元素相加,注意进位就可以了,下面是做了一次优化的代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
result := &ListNode{}
listNote := result
left := 0
for {
e1 := l1
e2 := l2
if e1 == nil || e2 == nil {
break
}
v := e1.Val + e2.Val + left
if v >= 10 {
left = 1
} else {
left = 0
}
n := v % 10
listNote.Next = &ListNode{Val:n}
l1 = l1.Next
l2 = l2.Next
listNote = listNote.Next
}
if l1 != nil {
for e := l1; e != nil; e = e.Next {
v := e.Val + left
if v >= 10 {
left = 1
} else {
left = 0
}
n := v % 10
listNote.Next = &ListNode{Val:n}
listNote = listNote.Next
}
}
if l2 != nil {
for e := l2; e != nil; e = e.Next {
v := e.Val + left
if v >= 10 {
left = 1
} else {
left = 0
}
n := v % 10
listNote.Next = &ListNode{Val:n}
listNote = listNote.Next
}
}
if left > 0 {
listNote.Next = &ListNode{Val:1}
}
return result.Next
}
执行结果:
执行用时 :16 ms, 在所有 golang 提交中击败了63.46%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户
发现还有人有更精简的代码,于是在重写下
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
result := &ListNode{}
listNote := result
left := 0
for l1 != nil || l2 != nil || left > 0 {
sum := left
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
if sum >= 10 {
left = 1
} else {
left = 0
}
listNote.Next = &ListNode{Val:sum % 10}
listNote = listNote.Next
}
return result.Next
}
执行结果:
执行用时 :8 ms, 在所有 golang 提交中击败了97.50%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户
从20ms到 8ms算是提升了不少,每次也从6.1M降至4.9M
(592)