LeetCode刷题Day2:两数相加


两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 
输出:7 -> 0 -> 8
原因:342 + 465 = 807LeetCode


 首先发一下我的思路已经给出的最初答案(大部分情况是正确的,但是超出数字范围就会和预期结果不一致),总之先把分析思路分享出来。


思路一:常规思路

分别循环两个链表,因为高位是个位,所以不断乘以10的n次方,n代表循环次数,从0开始,直到循环结束,就得到了两个无符号整数。所以,这就要求对输入数字有范围限制的要求,否则数字太大,超出整数的最大范围,得到的结果会因为发生溢出而不符合预期。

然后将两个整数进行加法运算,得到最终结果对应的int数字。

然后再将这个整数转化成字符串,循环字符串,得到字符对应的ASCII码点,然后减去48即可“间接“得到对应的数字。并按序生成链表。
 
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b

str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode

}

return current.Next
}

思路一:高级思路(学习)
对应位置的数字相加,跟10取模,即可得到该位置上十进制数相加之后的数字,然后和10进行整除,如果两个数相加小于10,则整除之后是0,否则是1,即要进位的1,所以直到两个链表都循环完,或者最后没有进位时,停止循环,最终返回。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0

for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}

return head.Next
}

 

0 个评论

要回复文章请先登录注册