个人网站开发 怎么赚钱,广点通广告投放平台,怎么在主机上的建设网站,h5怎么制作的目录 一、力扣93.复原IP地址1.1 题目1.2 思路1.3 代码1.4 总结 二、力扣78.子集2.1 题目2.2 思路2.3 代码2.4 总结 三、力扣90.子集二3.1 题目3.2 思路3.3 代码3.4 总结 一、力扣93.复原IP地址
#xff08;比较困难#xff0c;做起来很吃力#xff09;
1.1 题目 1.2 思路 … 目录 一、力扣93.复原IP地址1.1 题目1.2 思路1.3 代码1.4 总结 二、力扣78.子集2.1 题目2.2 思路2.3 代码2.4 总结 三、力扣90.子集二3.1 题目3.2 思路3.3 代码3.4 总结 一、力扣93.复原IP地址
比较困难做起来很吃力
1.1 题目 1.2 思路
同样是分割问题不过本题需要在字符串上直接进行操作由于String是不可修改的所以需要借助StringBuilder来处理字符串的增减及拼接操作 递归终止条件设置pointCount来记录点的数量当ip地址中已加入三个点时终止然后记得再判断最后一段的有效性 回溯pointCount的减减以及删掉刚刚加入到字符串里的点
1.3 代码
class Solution {public ListString res new ArrayList();public int pointCount 0;//ip地址中点的数量public ListString restoreIpAddresses(String s) {//java处理字符串用StringBuilderStringBuilder str new StringBuilder(s);backTracking(str,0);return res;}public void backTracking(StringBuilder str,int startIndex){//递归终止条件if(pointCount 3){//还剩最后一段的合法性未判断if(isVaild(str,startIndex,str.length()-1)){res.add(str.toString());}return;}//递归回溯for(int i startIndex;i str.length();i){if(isVaild(str,startIndex,i)){//合法那么加点切割str.insert(i1,.);pointCount;backTracking(str,i2);str.deleteCharAt(i1);pointCount--;}else{break;}}}//判断字符串str[left,right]左闭右闭是否满足ip段要求public boolean isVaild(StringBuilder str,int left,int right){if(left right){return false;}//不能含有前导0if(str.charAt(left) 0 left ! right){return false;}//介于0-255之间int num 0;for(int i left;i right ;i){if(str.charAt(i) 0 || str.charAt(i) 9){return false;}num (num * 10) (str.charAt(i)-0);if(num 255){return false;}}return true;}}1.4 总结
StringBuilder使用方法https://blog.csdn.net/qq_50617271/article/details/112686826 判断ip段是否合法时的方法isVaild()中的循环 s[i],表示字符串中的一位S【i】-0. 把字符串转化成数字。 num*10,是下一个循环的时候上一位数字要左移。假设s【255】, 循环三次的结果就是 2-25-255.
二、力扣78.子集
2.1 题目 2.2 思路
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点 自己的想法和组合问题类似不同的地方是树结构的每个结点的数据都要加入到结果集中即path当中每加入一个元素就需要将path加入到res结果集里。
2.3 代码
class Solution {public ListListInteger res new ArrayList();public ListInteger path new ArrayList();public ListListInteger subsets(int[] nums) {res.add(new ArrayList(path));//添加空集backTracking(nums,0);return res;}public void backTracking(int[] nums,int startIndex){//递归终止条件if(startIndex nums.length){return;}for(int i startIndex; i nums.length;i){path.add(nums[i]);res.add(new ArrayList(path));backTracking(nums,i1);path.remove(path.size()-1);}}
}2.4 总结
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点
三、力扣90.子集二
3.1 题目 3.2 思路
在上一题子集问题的基础上多了个条件可能包含重复元素那么就需要先排序然后按照树的结构横向去重即兄弟之间去重。
3.3 代码
class Solution {public ListListInteger res new ArrayList();public ListInteger path new ArrayList();boolean[] used;//记录数据元素是否使用过用来去重public ListListInteger subsetsWithDup(int[] nums) {used new boolean[nums.length];for(int i 0;inums.length;i){used[i] false;}//先向结果集中加入空集res.add(new ArrayList(path));//对原数组排序Arrays.sort(nums);backTracking(nums,0);return res;}//递归回溯public void backTracking(int[] nums,int startIndex){//递归终止条件if(startIndex nums.length){return;}for(int i startIndex;inums.length;i){//兄弟去重if(i!0 nums[i] nums[i-1] used[i-1] false){continue;}path.add(nums[i]);res.add(new ArrayList(path));used[i] true;backTracking(nums,i1);path.remove(path.size()-1);used[i] false;}}
}3.4 总结
横向兄弟去重注意是used[i-1] false;即前一个相同的元素没有被用也就是如果用当前位置元素的话汇合上一次for循环i-1的组合重复所有要continue避免重复即横向兄弟去重。 //兄弟去重if(i!0 nums[i] nums[i-1] used[i-1] false){continue;}
