丹阳网站建设方案,手机自己制作表白网站,如何做网站教程,yiqicms主站调用一级目录wordpress博客的文章?复原IP地址
题目详细#xff1a;LeetCode.93
这道题与上一道练习题分割回文字符串十分详细#xff0c;一样是涉及到分割字符串、判断字符串、递归与回溯的问题#xff0c;所以这道题要解决的难点在于#xff1a;
如何分割IP地址字符串如何判断分割的IP地址是否合法递归的…复原IP地址
题目详细LeetCode.93
这道题与上一道练习题分割回文字符串十分详细一样是涉及到分割字符串、判断字符串、递归与回溯的问题所以这道题要解决的难点在于
如何分割IP地址字符串如何判断分割的IP地址是否合法递归的结束条件要如何设置
首先解决“如何判断分割的IP地址是否合法”我们要知道一个合格的IP的地址的要求在这道题中的要求比较简单只要满足
IP地址中号段可以为0但不存在以0开头的号段IP地址长度为4个字节每一个号段的长度为1个字节即其大小空间为28 256每一个号段用十进制表示的范围为0255
其次是“如何分割IP地址字符串”这里的分割思路于分割回文字符串非常相似
在分割的过程中对每一次分割的号段字符串都进行合法性验证 如果当前号段合法在其后续插入分割符 ‘.’ 然后进入递归继续分割下一个号段如果当前号段不合法说明在当前位置进行分割的话已经是一个不合法的IP地址了所以无需继续分割直接break跳出当前循环。
最后是“递归的结束条件要如何设置”观察IP地址的特点可知
一个IP地址最多存在3个分割符 ‘.’
那么我们就可以递归参数中设置一个变量来记录分割符的数量如果数量3时即说明该IP地址分割完毕。
不过需要注意我们在之前的分割的过程中是先判断字段合法之后再添加分割符所以当分割符数量3之后还需要对最后的号段进行合法性验证以此来判断待添加的IP地址是否真的合法无论是否合法都要return因为这是递归的结束条件。
Java解法递归回溯
class Solution {ListString ans new ArrayList();public boolean isVaild(String s, int begin, int end){if (begin end || (end - begin) 3) {return false;}// 0开头的数字不合法if (s.charAt(begin) 0 begin ! end - 1) { return false;}int num 0;// 遇到非数字字符不合法for (int i begin; i end; i) {if (s.charAt(i) 9 || s.charAt(i) 0) { return false;}num num * 10 (s.charAt(i) - 0);// 如果大于255了不合法if (num 255) { return false;}}return true;}public void backtracking(StringBuffer sb, int startIndex, int pointNums){if(pointNums 3){if(isVaild(sb.toString(), startIndex, sb.length()))ans.add(sb.toString());return;}for(int i startIndex; i sb.length(); i){if(isVaild(sb.toString(), startIndex, i 1)){sb.insert(i 1, .);pointNums;backtracking(sb, i 2, pointNums);sb.deleteCharAt(i 1);pointNums--;}else continue;}}public ListString restoreIpAddresses(String s) {if(!(s.length() 12 || s.length() 4)){backtracking(new StringBuffer(s), 0, 0);}return this.ans;}
}子集
题目详细LeetCode.78
经过前面那些一知半解的练习之后到了这道题我终于领悟到了如何去打开回溯的解题思路当遇到回溯问题时我们立刻将问题转化都树形结构开始画图必须画图来理解除非你空间想象力真的很好我一开始凭空想了很久但很容易乱决定画图之后发现一切都十分明辽了 画得非常草稿化从前面回溯的理论基础和回溯解题模版可知
回溯问题其实就是一个收集树形结构节点结果或路径结果的问题循环的次数决定了树的宽度相当于对树进行同层访问递归的层数就是循环的嵌套层数相当于对树进行深度访问递归的结束条件就是回溯的条件相当于访问到树的叶子节点
回到这道题我们将问题转换为树形结构后对应的就可以发现
一个数字也可以是一个子集所以在每次循环中只取一个数字可以定一个变量 start 来标识当前应该取哪个下标的数字要求不能包含重复的子集所以在进入递归时要将当前的数字包括其之前的数字都分割出去这里我们利用下标变量 start 来控制从数字开始访问每访问一个节点其路径上的节点集合就是一个结果所以要在循环和遍历过程中就将结果加入结果集当nums数组为空时即下标到达数组边界 start nums.length 时就是递归的结束条件即回溯的条件
Java解法递归回溯
class Solution {ListListInteger ans new ArrayList();DequeInteger path new ArrayDeque();public void backTrack(int[] nums, int start){if(nums.length start){return;}for(int i start; i nums.length; i){path.offer(nums[i]);ans.add(new ArrayListInteger(path));backTrack(nums, i 1);path.removeLast();}}public ListListInteger subsets(int[] nums) {ans.add(new ArrayListInteger());this.backTrack(nums, 0);return this.ans;}
}子集II
题目详细LeetCode.90
这道题与上一题的区别在于整数数组nums可能包含重复的元素依旧是要求返回不重复的子集集合。
那么其实就是在上一题的基础上在树形结构上进行剪枝达到在循环和递归过程中进行去重的目的这样类似的题目在之前也有做过【Day27】第七章回溯算法39. 组合总和40.组合总和II
是首先画图辅助理解 通过之前的练习我知道在递归结束时再进行去重操作中在这一题同样会出现超出时间限制的情况所以在这里就不重蹈覆辙了所以难点就时如何在循环和递归的过程中就对结果进行去重。
通过画图我们可以发现去重操作或者说如何去判断是否会出现重复的结果都是在树的同一层中进行处理的
在循环过程中当我们依次访问数组中的元素时如果前一个元素与当前元素相等那么我们再对当前元素进行递归操作的话就有可能出现与前一个元素同样的子集为什么说是有可能呢而不是一定呢因为可能还存在着如图中 [1, 2, 2] 这样带有重复元素的子集所以为了避免丢失了部分子集我们需要提前对数组进行排序使其相同大小的数字都是连续的同时也说明了去重操作需要在树的宽度访问中进行而不是在树的深度访问中进行也就是在进入递归前就进行去重判断在这一道题中我们可以利用一个布尔数组used来辅助去重 当 nums[i] nums[i - 1] used[i] true 时说明虽然前一个数字已被访问但是还未被回溯进一步说明在树形结构中当前路径还未到达叶子节点在路径上还可能存在其他子集结果需要继续递归到下一层当 nums[i] nums[i - 1] used[i] false 时说明虽然前一个数字与当前数字相同但是由于递归是深度优先遍历所以前一个数字之所以是 used[i - 1] false 是因为它已经被回溯了其所有路径上的子集都已添加进结果集如果再对当前数字继续递归的话则会出现与前一个数字重复的子集所以不需要在对当前数字进行递归直接进入下一层循环
Java解法递归回溯哈希
class Solution {ListListInteger ans new ArrayList();DequeInteger path new ArrayDeque();public void backTrack(int[] nums, boolean[] used, int startIndex){if(nums.length startIndex){return;}for(int i startIndex; i nums.length; i){if(i 0 nums[i] nums[i - 1] !used[i - 1]){continue;}path.offer(nums[i]);used[i] !used[i];ans.add(new ArrayListInteger(path));backTrack(nums, used, i 1);path.removeLast();used[i] !used[i];}}public ListListInteger subsetsWithDup(int[] nums) {boolean[] used new boolean[nums.length];Arrays.sort(nums);this.ans.add(new ArrayListInteger());this.backTrack(nums, used, 0);return this.ans;}
}第一次接触到回溯这两天做题总是停留在一知半解的地步懵懵懂懂的本来想要囫囵吞枣得过且过算了没想到最后两道练习题我突然醒悟遇见回溯题就应该先将其转换为树形结构通过画图来辅助理解整个循环、递归与回溯的过程这入门的过程是如此的艰难但是思路打开之后一切都变得那么的通透了真叫人
初极狭才通人步行数十步豁然开朗。
