本文主要是介绍leetcode每日一题复盘(10.30~11.5)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 93 复原ip地址
这一题和之前的分割回文串有异曲同工之妙,都是给一组数据让你判断分割成几组小数据,代码主要分成三部分,用来判断的函数,回溯函数,主函数;最好是在原数据上面进行操作,我一开始就是新开了一个字符串做起来反而困难
首先说判断函数,这个根据题目我们可以很容易就写出代码来,需要注意的是判断是否大于255时,我们要用num来记录整个字符串对应整数的大小,因此需要用num=10*num进行进位
其次是回溯函数,回溯函数我们都知道主体是backtracking包含for,for再包含backtracking,除此之外还有一个终止递归的条件,这里我们引进一个变量来记录逗号的数量,当逗号等于三的时候我们就可以判断第四段ip地址,以此选择是否加入结果集中
这里我们讲一下抽象的概念方便理解,工作指针i可以看作我们划的那条线,i前面的可以看作这一次需要判断的数据,如果符合要求则继续递归,不符合要求则进行横向遍历,以此保证每一段ip地址都是合法的,i后面的则是我们下一次需要遍历的数据,即startindex=i+1;
感觉理清楚了思路还是比较好写的,难就难在你判断函数代码怎么写好,能不能想到先处理前三段再处理第四段,能不能想到直接在原数据上面操作,这些就是需要我们思考的地方,做题量和思考缺一不可
leetcode 90 子集2
这又是一种新的题型了,感觉做回溯最重要的是分辨出是那种题型,现在已经涉及到组合,分割,子集三种类型了,组合是在数据中取一个数,剩下的数作为下一次的遍历的数据,整个树枝当作一组放入结果;分割和组合差不多,先分割一个/多个数据出去,判断这个数据,剩下的数据作为下一次遍历的数据;而子集是将每一次的判断的数据都放入结果集中,这是和上面两种不同的地方,因此每一次回溯
backtracking都有一次pushback操作
将每一个树支当作以该元素开头的子集就好容易理解了,例如123,取1就是以1开头的子集
允许结果重复and不允许结果重复
允许重复即不用去重了,因为数据里会有重复的数,在遍历的时候会有重复结果出现,例如1444,第一个4就已经包含了后面几个4的情况,允许重复的话就不用管直接遍历整个数组/字符串即可
如果不允许结果重复,即需要比较前一个和当前数据是否相同,相同则跳过continue,相当于进行了剪枝操作(需要先进行排序操作)
leetcode 491 递增子序列
这一题和上一题子集看起来差不多，直接套模板，然后就错了😂，专题刷题就是容易死背模板，然后缺少自己的思考
这一题的要求是找到所有递增子序列，长度大于1，看起来和上一题要求差不多，但是做起来的时候有很大的差别，主要有两点
首先是要求递增，而子集那道题是不要求递增的，排序之后相邻去重即可，本题给出的数据不一定是递增的，因此无法相邻去重也就用不了nums[i]＝＝nums[i-1]去判断了;可以排序再相邻去重吗?答案当然是不可以的，你把数据都改变了相当于把题改了答案也都不一样了
其次是去重方式，上面说到了无法使用相邻去重，那么如何进行判断呢(path路径上上一个节点的下标和当前下标不一定相邻，例如416，46下标不相邻)，那就需要用到uset记录每一层中使用了的数据，就可以避免在同一层中重复(例如4717，同一层中先选择了第一个7，第二个7就可以跳过了，避免出现两次47)，这样也就实现了隔项去重了
为什么uset不是记录同一树枝上面的值呢?因为数据允许数据重复，即4477是容许的
理解去重方式不同是解决本题的关键，相邻去重的方式只适合顺序数据
这篇关于leetcode每日一题复盘(10.30~11.5)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
