LeetCode 93 复原IP地址题目链接93.复原IP地址文档讲解代码随想录视频讲解复原IP地址思路与感想这道题拿到的时候感觉确实跟分割回文串差不多然后我尝试自己写。写了十几分钟代码算是写完了但是bug一堆主要出现在每次的IP片段在不断累积但实际上每次进入for循环我都要根据startIdnex和i的关系生成一个待验证的IP片段第二个问题就是for循环边界条件要加一个startIndex i 3来保证每个IP片段长度不超过3尽管这个条件我在isValid函数中有过判断但这么做似乎也有必要其次就是我的截止条件不但要最终path里面的点有四个添入result点去掉末尾的点还要保证startIndex已经遍历到尾部即使用了所有数字。后面看卡哥的思路确实大体上相差无几但卡哥在处理分割操作的时候实在原字符串上进行的确实比较方便而且由于只加了三个点的原因终止条件时添加前就是要把第三个点后面的IP片段做一个isValid判断。不过由于在原地操作isValid函数主体也比我的方法复杂一点。总之题目做下来虽然做过类似的分割题目但是最后的代码也不是自己独立完成的有点失落好在相比第一次做分割回文串对分割操作毫无思路现在也知道用StringBuilder进行分割效仿写出个百分之八九十进步还是挺大。收获1.再次熟悉分割操作class Solution { ListString result new ArrayList(); public ListString restoreIpAddresses(String s) { backtracking(s,0,new StringBuilder(),0); return result; } public void backtracking(String s, int startIndex, StringBuilder path, int segmentCount) { if (segmentCount 4) { // 点为四个的时候就说明到叶子节点了 if (startIndex s.length()) { // 保证path里面包含了所有s里面的数字 result.add(path.substring(0, path.length() - 1)); // 去掉末尾的 . } return; } for (int i startIndex; i s.length() i startIndex 3; i) { // i startIndex 3是为了保证一段子IP长度小于4 String segment s.substring(startIndex, i 1); // 每次都重新根据startIndex和i的位置生成一个新的局域segment if (check(segment)) { // 如果segment符合条件就划分添加到path中 int lenBefore path.length(); // 记录添加前的长度方便后续回溯 path.append(segment).append(.); // 加入path中 backtracking(s, i 1, path, segmentCount 1); // 进入下一层递归 .的数量加一 path.setLength(lenBefore); // 恢复path长度 } } } public boolean check(String k) { if ((k.length() 1 k.charAt(0) 0)|| Integer.parseInt(k.toString()) 255) { // 前驱不为0且大小在0-255间合法 return false; } return true; } }LeetCode 78 子集题目链接78.子集文档讲解代码随想录视频讲解子集思路与感想这道题我先是照着回溯模板和画的树结构图写但因为图画的不全的缘故导致我没有发现这道题和以前回溯题的不同点看了卡哥的提示才明白这道题是在每个叶子节点都要收获结果可惜纵然明白了这个提示也没想到要把添加结果的条件放在终止条件前面而是在for循环里面调了半天顺序一直跑不对。由此可见我对树的每个节点对应的都是每层递归这点还不太清晰。而且也是因为图没画完的缘故没有发现我错误代码跑出来的结果跟正确答案之间的差别就是叶子节点的结果被我漏掉了而这正是因为我把添加条件放在了for循环内。收获1.每个节点收获结果时添加条件怎么写// 回溯法 class Solution { ListListInteger result new ArrayListListInteger(); ListInteger path new ArrayList(); public ListListInteger subsets(int[] nums) { backtracking(nums,0); return result; } public void backtracking(int[] nums, int startIndex) { result.add(new ArrayList(path)); // 在每一个节点即每次进入一层递归都可以收获结果 if (startIndex nums.length) { // 截止条件当startIndex大于等于nums数组长度时即可以取得数字为空时结束不过这个截止条件也可以省略因为如果这个条件一旦满足了那后面for循环将会因无法满足i nums.length条件而不执行。 return; } for (int i startIndex; i nums.length; i) { path.add(nums[i]); backtracking(nums,i 1); path.removeLast(); } } }LeetCode 90 子集Ⅱ题目链接90.子集Ⅱ文档讲解代码随想录视频讲解子集Ⅱ思路与感想这道题确实如同卡哥所说没什么新奇的地方就是组合总和Ⅱ的去重加上子集问题的知识。由于对于这两题印象都比较深刻所以代码整体写下来没有一点犹豫两三分钟就写完了。只不过去重分支里面写成了break导致重复数字后面的有效数字都被我去除了。我当时是把剪枝操作和去重操作搞混了所以后面改了下才通过。看卡哥视频发现卡哥在讲去重的时候说如果用startIndex和i的关系进行判断树层还是树枝的话这种方法并不通用在后续解队列相关题目就行不通了。原本我想着掌握这一招就够了因为比较简洁听卡哥一说就老老实实去文档讲解看看这个used数组怎么创建了。收获1.重温树层去重逻辑和子集添加元素逻辑2.used数组去重法// 回溯法 class Solution { ListInteger path new ArrayList(); ListListInteger result new ArrayList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); // 排列顺序 backtracking(nums,0); return result; } public void backtracking(int[] nums, int startIndex) { result.add(new ArrayList(path)); // 每进入一层新的递归对应每个节点都要进行添加结果的操作 if (startIndex nums.length) { // 终止条件其实可以省略 return; } for (int i startIndex; i nums.length; i) { if (i startIndex nums[i] nums[i - 1]) { // nums前后元素相同的前提下保证是树层i startIndex进行树层去重 continue; } path.add(nums[i]); backtracking(nums,i 1); path.removeLast(); } } }复原IP地址有点难剩余两道题都挺简单的不愧是分割题目即便做了一次也无法复现出来还是得多做才行花了大概四个小时轻松做完这周把spring也可以完结了八股也在稳步推进加油加油明年暑假实习我来啦