网站建设的注意事项,网络营销的理论和特点有哪些,网页设计规划,手机上网站用建设工具随想录日记part23 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.19 主要内容#xff1a;回溯算法在代码学习中尤其重要#xff0c;所以今天继续加深对其的理解#xff1a;1#xff1a;复原IP地址 #xff1b;2.子集 #xff1b;3.子集II
93.复原IP地…随想录日记part23 t i m e time time 2024.03.19 主要内容回溯算法在代码学习中尤其重要所以今天继续加深对其的理解1复原IP地址 2.子集 3.子集II
93.复原IP地址78.子集90.子集II Topic1复原IP地址
题目 有效 IP 地址正好由四个整数每个整数位于 0 0 0 到 255 255 255 之间组成且不能含有前导 0 0 0整数之间用 ‘.’ 分隔。例如 0.1.2.201 0.1.2.201 0.1.2.201 和 192.168.1.1 192.168.1.1 192.168.1.1 是 有效 IP 地址但是 0.011.255.245 、 192.168.1.312 0.011.255.245、192.168.1.312 0.011.255.245、192.168.1.312 和 192.168 1.1 192.1681.1 192.1681.1 是 无效 I P IP IP 地址。 给定一个只包含数字的字符串 s s s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s s s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 输入 s 25525511135 s 25525511135 s25525511135 输出 [ 255.255.11.135 , 255.255.111.35 ] [255.255.11.135,255.255.111.35] [255.255.11.135,255.255.111.35]
思路 切割问题切割问题就可以使用回溯搜索法把所有可能性搜出来 按照回溯模板我们进行回溯三部曲 递归三部曲 1.回溯函数模板返回值以及参数 在这里要定义一个全局变量 r e s u l t result result用来存放符合条件结果的集合。回溯函数里需要一个参数为 i n t int int 型变量 s t a r t I n d e x startIndex startIndex来表示切割字符的起始索引同时还需要一个 i n t int int 类型的变量 n u m P o i n t numPoint numPoint 来记录切割点数。 所以整体代码如下 ListString result new LinkedList();// 保存最后结果的数组void reback(String s, int startIndex, int numPoint)2.回溯函数终止条件 本题明确要求只会分成 4 4 4 段所以不能用切割线切到最后作为终止条件而是分割的段数作为终止条件。 n u m P o i n t numPoint numPoint 表示逗点数量 n u m P o i n t numPoint numPoint 为 3 3 3 说明字符串分成了 4 4 4 段了。然后验证一下第四段是否合法如果合法就加入到结果集里 代码如下 if (numPoint 3) {if (isVaid(s, startIndex, s.length() - 1))result.add(s);elsereturn;}3.回溯搜索的遍历过程 在 f o r ( i n t i s t a r t I n d e x ; i s . s i z e ( ) ; i ) for\ (int\ i startIndex; i s.size(); i) for (int istartIndex;is.size();i)循环中 [ s t a r t I n d e x , i ] [startIndex, i] [startIndex,i] 这个区间就是截取的子串需要判断这个子串是否合法。如果合法就在字符串后面加上符号 . . . 表示已经分割。 如果不合法就结束本层循环如图中剪掉的分支 然后就是递归和回溯的过程 递归调用时下一层递归的 s t a r t I n d e x startIndex startIndex 要从 i 2 i2 i2开始因为需要在字符串中加入了分隔符 . . . 同时记录分割符的数量 n u m P o i n t numPoint numPoint 要 1 1 1。 回溯的时候就将刚刚加入的分隔符. 删掉就可以了 n u m P o i n t numPoint numPoint也要 − 1 -1 −1。 实现代码如下 for (int i startIndex; i s.length(); i) {if (isVaid(s, startIndex, i)) {s s.substring(0, i 1) . s.substring(i 1);numPoint;reback(s, i 2, numPoint);numPoint--;// 回溯s s.substring(0, i 1) s.substring(i 2);// 回溯} else {break;// 这里注意思考为啥不用return或者continue}完整的代码如下 class Solution {ListString result new LinkedList();// 保存最后结果的数组public ListString restoreIpAddresses(String s) {if (s.length() 12)return result;reback(s, 0, 0);return result;}private void reback(String s, int startIndex, int numPoint) {if (numPoint 3) {if (isVaid(s, startIndex, s.length() - 1))result.add(s);elsereturn;}for (int i startIndex; i s.length(); i) {if (isVaid(s, startIndex, i)) {s s.substring(0, i 1) . s.substring(i 1);numPoint;reback(s, i 2, numPoint);numPoint--;// 回溯s s.substring(0, i 1) s.substring(i 2);// 回溯} else {break;// 这里注意思考为啥不用return或者continue}}}private Boolean isVaid(String s, int begin, int end) {// 判断字符是否合法if (end begin)return false;if (s.charAt(begin) 0 begin ! end)return false;int count 0;// 计算器for (int i begin; i end; i) {if (s.charAt(i) 0 || s.charAt(i) 9)return false;count count * 10 s.charAt(i) - 0;}if (count 255)return false;elsereturn true;}
}时间复杂度: O ( 3 4 ) O(3^4) O(34)IP地址最多包含4个数字每个数字最多有3种可能的分割方式则搜索树的最大深度为4每个节点最多有3个子节点。 空间复杂度: O ( n ) O(n) O(n) Topic2子集
题目 给你一个整数数组 n u m s nums nums 数组中的元素互不相同 。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。 输入 n u m s [ 1 , 2 , 3 ] nums [1,2,3] nums[1,2,3] 输出 [ [ ] , [ 1 ] , [ 2 ] , [ 1 , 2 ] , [ 3 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 1 , 2 , 3 ] ] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
思路 如果把子集问题、组合问题、分割问题都抽象为一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点以示例中 n u m s [ 1 , 2 , 3 ] nums [1,2,3] nums[1,2,3] 为例把求子集抽象为树型结构如下 从图中红线部分可以看出遍历这个树的时候把所有节点都记录下来就是要求的子集集合。 按照回溯模板我们进行回溯三部曲 递归三部曲 1.回溯函数模板返回值以及参数 在这里要定义两个全局变量 p a t h path path用来存放符合条件单一结果 r e s u l t result result用来存放符合条件结果的集合。回溯函数里需要一个参数为 i n t int int 型变量 s t a r t I n d e x startIndex startIndex。 所以整体代码如下 ListListInteger resultnew ArrayList();
LinkedListInteger pathnew LinkedList();
void reback(int[] nums,int startIndex)2.回溯函数终止条件 就是 s t a r t I n d e x startIndex startIndex 已经大于数组的长度了就终止了因为没有元素可取了代码如下: 代码如下 if(startIndexnums.length) {return; }3.回溯搜索的遍历过程 求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。 实现代码如下 for(int istartIndex;inums.length;i){path.add(nums[i]);reback(nums,i1);path.removeLast();}完整的代码如下 class Solution {ListListInteger resultnew ArrayList();//记录最后的结果ListInteger pathnew LinkedList();public ListListInteger subsets(int[] nums) {reback(nums,0);return result;}private void reback(int[] nums,int startIndex){result.add(new ArrayList(path));if(startIndexnums.length) {return; }for(int istartIndex;inums.length;i){path.add(nums[i]);reback(nums,i1);path.removeLast();}}
}时间复杂度: O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n) 空间复杂度: O ( n ) O(n) O(n) Topic3子集II
题目 给你一个整数数组 n u m s nums nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。解集不能包含重复的子集。返回的解集中子集可以按任意顺序排列。 输入 n u m s [ 1 , 2 , 2 ] nums [1,2,2] nums[1,2,2] 输出 [ [ ] , [ 1 ] , [ 1 , 2 ] , [ 1 , 2 , 2 ] , [ 2 ] , [ 2 , 2 ] ] [[],[1],[1,2],[1,2,2],[2],[2,2]] [[],[1],[1,2],[1,2,2],[2],[2,2]]
思路 这个就是上面的方法加上了去重操作去重的两种方法和之前如出一辙下面直接给出两种代码
1.使用used数组的
class Solution {ListListInteger resultnew ArrayList();LinkedListInteger pathnew LinkedList();boolean[] used;public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);usednew boolean[nums.length];reback(nums,0);return result;}private void reback(int[] nums,int startIndex){result.add(new ArrayList(path));if(startIndexnums.length) {return; }for(int istartIndex;inums.length;i){if(i0 nums[i]nums[i-1] !used[i-1]){continue;}path.add(nums[i]);used[i]true;reback(nums,i1);path.removeLast();used[i]false;}}
}2.不使用used数组的
class Solution {ListListInteger resultnew ArrayList();LinkedListInteger pathnew LinkedList();public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);reback(nums,0);return result;}private void reback(int[] nums,int startIndex){result.add(new ArrayList(path));if(startIndexnums.length) {return; }for(int istartIndex;inums.length;i){if(istartIndex nums[i]nums[i-1]){continue;}path.add(nums[i]);reback(nums,i1);path.removeLast();}}
}时间复杂度: O ( n ∗ 2 n ) O(n * 2^n) O(n∗2n) 空间复杂度: O ( n ) O(n) O(n)
