代码随想录算法训练营第28天 | 93.复原IP地址、78.子集、90.子集II
- 自己看到题目的第一想法
- 看完代码随想录之后的想法
- 自己实现过程中遇到哪些困难
- 今日收获,记录一下自己的学习时长
链接: 93.复原IP地址
链接: 78.子集
链接: 90.子集II
自己看到题目的第一想法
93.复原IP地址:画好树形图之后分析三部曲怎么写,但是感觉还不是很清晰,怎样加点?感觉似乎有点像切割问题,在切割的地方增加点,回想起之前切割回文串题目,使用startIndex作为切割线,但是具体实现我还是比较模糊。
78.子集:切割问题。[ ]预定,但是和之前的不一样,对于每个节点,要有不再做任何深入的操作,也就是它的叶子节点的选取要有一个是空的选择,除此之外的起始点选择应该是i+1。
90.子集II:树层去重,使用use数组记录各个元素选择情况,并且每个节点都加入result。
看完代码随想录之后的想法
93.复原IP地址:切割使用startIndex,[startIndex,i]作为切割的子串,for循环的过程就类似于一个叶子节点发散各个分支的过程。此题需要再增加对于子串合法性的判断,细节需要注意。
java对字符串的操作之获取子串:
String substring()方法:实现截取字符串,利用字符串的下标索引来截取(字符串的下标是从0开始的,在字符串中空格占用一个索引位置)
1.substring(int beginIndex):截取从指定索引位置开始到字符串结尾的子串
2.substring(int beginIndex, int endIndex):从beginIndex开始,到endIndex结束(不包括endIndex)
String str = "abcde";
String substr1 = str.substring(2);//substr1为"cde"
String substr2 = str.substring(2,4);//substr2为"cd"
charAt():
返回字符串索引处的字符
78.子集:发现题解做的比我想的要简单,我想的空操作其实可以理解为把所有节点都记录下来,就是要求的子集集合。
90.子集II:直接看代码。对于used数组的声明和使用:
boolean[ ] = used;
used = new boolean[nums.length];
自己实现过程中遇到哪些困难
93.复原IP地址:1.切割问题,如何表示切割线和子串 2.Java对于字符串的切割子串操作和取索引处字符的api 3.判断子串有效细节。总感觉这道题出的很好。
78.子集:自己写的时候对于把所有path加入result这一步没有很清晰位置,我放到了for循环里面,而且结果输出子集全是空集,我看答案把这一步放在回溯函数的第一步。
result.add(new ArrayList<>(path));//正确写法
result.add(path);//我写的,输出子集全是空
new ArrayList<>(path)创建了一个新的ArrayList对象,它的内容和path相同,但是是一个全新的对象。这样做确保了result中每个元素都是一个独立的对象,而不是引用了同一个path对象。
我这样写将会导致result中每个元素都是指向同一个path对象的引用。当后续修改path时,result中的所有元素都会受到影响,因为它们引用的是同一个对象。这也解释了为什么输出结果中所有子集都是空的,因为它们引用的是同一个path对象,而且在添加到result之后path对象内容为空。