数据结构中的算法题解题思路汇总

时间:2022-06-25 09:25:27

内容会持续更新,有错误的地方欢迎指正,谢谢!

常识

1.如何分析一个问题?画图+举例=>算法,还要分析时间复杂度以判断是否可行。
2.写完代码后,如何编写测试用例?也就是两类测试用例:功能测试和边界测试!
3.如何能及时发现并纠正代码的问题?提前想好测试用例,写完代码后,立即用事先准备好的测试用例进行检查。只有确保代码通过测试后,再提交给Interviewer。因为他也是通过他事先准备的测试用例进行检查。如此,才能避免被他找出问题后,你去慌张地修改代码的窘境。
4.那什么时候可以开始写代码了?当Interviewer肯定了我们说的思路之后,可以开始写代码了。

单链表

精华:当用一个指针遍历链表不能解决问题时,可以尝试用两个指针来遍历链表:可让其中一个指针的速度快一些(一次走两步),即快慢指针;也可让前指针先走若干步,即前后指针。同理,两个指针不能解决问题,就用三个指针。如此,绝大多数链表的问题,都能轻松解决了。

代码详情请见单链表题目汇总。补充说明:下方所言的中指针即当前指针。

1、逆序构造单链表(了解)

前中指针。定义一个前指针,再在循环里申请新结点(即当前结点)的空间并为之赋值并让其next指向前指针并更新前指针。

2、从尾到头打印链表

法一:中指针+利用栈的逆序特性
法二:中指针+利用递归(递归在本质上就是一个栈结构,存到vector)的逆序特性
Interviewer期待的问题:是否允许在打印链表的时候修改链表的结构,也就是能否反转链表再从头开始输出?如果我们要修改输入的数据,一定要问面试官是不是允许修改!

3、反转链表

法一:迭代(前中后三个指针)
法二:递归(前中指针,递归前半部分使当前结点走到最后一个结点、前结点走到倒数第二个结点,递归后半部分只需利用前指针进行反转)
诚恳的建议:在Interview的时候,不要急着动手写代码,而是一开始要仔细分析和设计,这才会给Interviewer留下很好的印象。与其很快写出漏洞百出的代码,不如仔细分析后写出鲁棒的代码。

4、找出单链表的中间结点(了解)

快慢指针(快指针一次两步,慢指针一次一步)

5、链表中环的入口结点

利用快慢指针判断是否存在环的同时,求得环中任意一个结点,再利用该结点求得环中结点数n,再用前后指针,邂逅点就是目标点。

6、两个链表的第一个公共结点

法一:尾结点和其中一个链表的头结点相连,就变成了上一个问题
法二:先通过两个指针求出两个链表的长度差,再用前后指针,邂逅点就是目标点。O(m+n)

7、链表升序排序(了解)

前后指针+快排思想

8、链表中倒数第k个结点

法一(方法好):前后指针,倒数第k个结点就是正着数第n-k+1个结点,前指针先走k-1步,再一起走。前指针到达最后一个结点时,后指针则到达了目标结点。
法二(方法不好):也可以先求总的结点数n,再让头结点直接走n-k步,到达n-k+1处的结点即可。
诚恳的建议:由于这题特别考验代码的鲁棒性,思考的时候,一定要多问自己“如果不什么什么,那么会什么什么”,这就能在一开始做到防御性编程,做其他题也应如此!
小段子:某interviewee很快地写出了代码,却收到了拒信,原因就是代码不够鲁棒性,有多个可以崩溃的点未考虑到:输入的是空指针、k>n、k=0
另外,Interviewer期待的解法是法一,因为法一只需要遍历一次链表,而法二需要遍历两次链表。

9、删除指定结点

法一:前中后指针,从头开始遍历,时间复杂度O(n)
法二:中后指针,若要删除2,则把2和3的val交换,2的next指向3的next,即4,再delete3。

10、合并两个升序的链表

法一:递归,两个链表的头指针+目标链表的头指针
法二:迭代,两个链表的头指针+目标链表的头指针
常考题,需要注意的问题:1.写代码前没想清除合并的过程导致中间断开了;2.不够鲁棒。
诚恳的建议:写代码前,要全面分析哪些情况下,可能会出现空指针,并想清楚如何处理。

二叉树

1、前序遍历,中序遍历,后序遍历

法一:递归实现(其实递归就是一种栈)
法二:栈+迭代

2、层次遍历

宽度优先搜索BFS,迭代,使用先进先出的队列queue或两端都可以进出的deque,要让队列有进有出。

3、求树的结点数

遍历。return 1+左子树的个数+右子树的个数

4、求树的叶子数

遍历。return 左子树的叶结点数+右子树的叶结点数

5、求二叉树第k层的结点个数

遍历。k作为递归函数的参数,每降低一层,k就要-1。
return KNodeCount(pRoot->left,k-1)+KNodeCount(pRoot->right,k-1);
13题(二叉树中和为某一值的路径)的思路和该题很像。

6、求树的深度

遍历。对根结点求深度,就是求其左右子树的深度中最大的那个深度+1

7、判断两颗二叉树是否结构相同

(不用考虑val是否相同。结构相同:两颗二叉树的两个根结点对应的的左子树和右子树结构相同。)
遍历。return 判断两棵树的左子树是否相同&&判断两棵树的右子树是否相同;
什么叫相同?两个对应的结点同时为空
什么叫不同?两个对应的结点中只有一个结点为空
那都不为空时呢?去递归呗。

8、求二叉树的镜像

遍历。对于根结点,交换其左右子树,左右子树各自去递归。

补充的问题:判断是不是对称的二叉树。方法:bool函数,前序遍历,对应的结构和对应的值都要相等,return里 左右子树继续去递归。

小窍门:该类问题很抽象,图形能使抽象的问题具体化、形象化,得到规律。比如:二叉树、链表、二维数组等问题都可以采用画图的方法来分析。空想很难能想明白题目中隐含的规律。

9、求两个结点的最低公共祖先结点

题目1:若这是一棵二叉查找树,那么就简单了:1.当根结点的值大于两个这结点的值,则继续在左子树中找;2.当根结点的值小于两个这结点的值,则继续在右子树中找;3.当根结点的值在这两个结点的值之间,则该根结点就是最低公共祖先结点。
题目2:若这不是一棵二叉树,只是普通的树,每个结点除了根结点外 都有指向父结点的指针:这不就是求两个链表的第一个公共结点嘛。
题目3:就是下方的第9题,若这是一颗二叉树(题目偏难),则遍历后,需有如下判断:

//对一个根结点来说,分别在左右子树中找到了目标结点,则该根结点就是所求结点。
if (left!=nullptr && right!=nullptr)
return pRoot;
//对一个根结点来说,只在左子树或右子树找到了目标结点,则返回找到的结点。
return left!=nullptr ? left : right;

10、求任意两结点距离

遍历。先找到两个结点的最低公共祖先结点,然后分别计算最低公共祖先结点(根结点)与它们的距离,最后相加即可。也就是两个函数,第二个函数用于求距离:遍历,先在左子树中找,if没找到的话,再在右子树中找,找到了则return res+1;最后都没找到就return -1。

11、找出二叉树中某个结点的所有祖先结点

遍历。bool递归函数。if(找出该结点的左子树中某个结点的所有祖先结点||找出该结点的右子树。。。),如果为if条件为true,则输出该结点。

12、判断二叉树是否是平衡二叉树(了解)

遍历。if(判断左子树是否是平衡二叉树&&判断右子树是否是平衡二叉树),再在这个if中,if(判断深度差left-right的绝对值是否小于1)。。。挺有挑战的一道题。

13、二叉树中和为某一值的路径

前序遍历,和expectNumber作为递归函数的一个参数,每降低一层,expectNumber就要减去刚才那个结点的值。
定义一个二维vector容器res和一个一维vector容器temp。每路过一个结点,就将该结点装进temp。若走到了叶节点,且该条路的和刚好等于expectNumber,则将这条路(temp记录的)装入res;若此时和不等于expectNumber,就回溯。
如何回溯?
在双重递归后加上temp.pop_back() 弹出最后那个元素,再装入下一个要遍历的元素,不就好了。

14、根据前序和中序重建二叉树

构建 左子树的前序中序 和 右子树的前序中序,再分左右子树递归。
小窍门:当我们发现大问题和小问题在本质上是一致时,便可用递归解决,所以二叉树的题基本都用递归。由于要遍历二叉树,所以基本都用双重递归。

15、二叉搜索树与双向链表

中序遍历。简单题。定义两个变量,一个变量用于记录头结点,一个变量用于改变指向。
小窍门:一定要先画图分析,通过分析得到思路后,再动手写代码,不要一开始就写,不然越写越懵。