算法历程:两数相加

c2510529649 · 收录于 2023-06-03 04:30:03 · source URL

本人菜鸡一只,在算法上被各种吊锤,但其中也受到了各路大佬的帮助,为了记录自己的成长,也为了让新人收获我的经验(虽然感觉万中无一。。。。。。),遂记录下做题过程,因为目前比较熟练的只有go语言,所以代码部分全由go语言写成,但算法部分应该大同小异,因为水平有限,所以解法可能不是最优解,甚至可能有错误,在评论区中指出的时候希望各位大佬能笔下留情,(跪.jpg)

题目来源:力扣算法:两数相加

题目:

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
在这里插入图片描述

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

思考过程:

1、写好框架

写算法的时候,个人建议哪怕啥思路都没有,也可以试着把此算法必须的部分列出来,这对思路的整理是有好处的,哪怕多余的也不要怕,又不是不能删。。。。。。当然,搭好的框架可能会限制思路的发散,反而影响对题的深度思考,这点见仁见智,反正我这个菜鸡不搭框架连往哪边像都不知道。。。

  1. 复制题目上的空函数体。
  2. 由题可得,输入的是链表,输出的也是链表,所以就新定义个结果链表吧!
  3. 节点的循环肯定也是必要的,也一同写上吧!

结果如下:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	//节点的循环
	for{
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//进入下一个节点
		l = l.Next
	}
}

2、根据题目写出大致功能

在题目要求非常直白或者在有思路的情况下,写出大致的功能,只要完成这一步并思路不出错,算法就算是解出来一大半了,所以这一步基本算是算法中最困难的部分,不过好在这道题很直白,所以这一步可能很轻松的想出来,至于能不能写出来就看大家对链表的熟悉程度了(因为学艺不精,本题目的链表实现部分本菜鸡翻了半天的链表相关资料才写出来的。。。。。。)

  1. 两数相加(暂不考虑进位)。
  2. 进入下一个节点(暂不考虑两个链表长度不一样)。
  3. 结束循环的条件(即两个链表同时到达尾节点)。

结果如下:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	//节点的循环
	for {
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//两数相加
		l.Val = l1.Val + l2.Val
		//到达尾节点
		if l1.Next == nil && l2.Next == nil {
			return ll
		}
		//进入下一个节点
		l = l.Next
		l1 = l1.Next
		l2 = l2.Next
	}
}

3、处理细节和考虑特殊情况

这部分就看大家的思路够不够发散了,毕竟有的特殊情况真的很让人傻眼。。。

特殊情况1:两数相加可能会导致进位。
这个是加法的正常现象,因为一个节点只能放一位数字,所以要把多出来的一位放在结果链表的下一位,本节点结果减10(考虑通用性的话用取余%比较合适,但是毕竟这只是加法,减10也能满足条件,毕竟加法最多只会多10),因为我们是在运算前就先申请了结果链表的下一位的空间,所以直接在下一位结果链表置1即可,加法算式和结束循环因此也需要变化一下。

...
	for{
	
		...
		//两数相加
		l.Val = l1.Val + l2.Val + l.Val
		//如果两数之和大于10
		if l.Val >= 10 {
			l.Val = l.Val - 10
			l.Next.Val = 1
		}
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		...
	}
...

特殊情况2:两链表长度不一样。
这个情况也很容易想到,如果只有一个下个节点为空,那就不符合循环结束的条件(毕竟不为空的那一条的数还没加上),对于我个人来说,想一个比较好实现的解决方法有点困难(毕竟菜鸡一只,很多方法以我水平很难实现),最后我想到的方法是:位数不够,0位补齐!

...
	for{
		...
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		//如果单个链表无下个节点
		if l1.Next == nil {
			l1.Next=new(ListNode)
		}
		if l2.Next == nil {
			l2.Next =new(ListNode)
		}
		...
	}
...

特殊情况3:链表为空。
这个在案例里面几乎必出,搞得我一想特殊情况就能想到这个,不过这个很好解决,单独写出来个情况判断就好了!

...
	//特殊情况:其中一项为空的情况
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
...

将以上特殊情况整合起来,就是最终代码啦!

最终代码:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//特殊情况:其中一项为空的情况
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	
	for {
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//两数相加
		l.Val = l1.Val + l2.Val + l.Val
		//如果两数之和大于10
		if l.Val >= 10 {
			l.Val = l.Val - 10
			l.Next.Val = 1
		}
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		//如果单个链表无下个节点
		if l1.Next == nil {
			l1.Next=new(ListNode)
		}
		if l2.Next == nil {
			l2.Next =new(ListNode)
		}
		//进入下一个节点
		l = l.Next
		l1 = l1.Next
		l2 = l2.Next
	}
}

运行结果:

在这里插入图片描述

至此此题结束,虽然还有很多优化的空间,但是因为水平有限,后面的优化就期待各位有志之士来实现吧!