郑州网站设计收费,全国劳务分包工程信息,烟台软件优化网站,课程网站如何建设方案大家好我是苏麟 , 今天带来几道回溯比较困难的题 . 回溯有很多比较难的问题#xff0c;这里我们看两个#xff0c;整体来说这两个只是处理略复杂#xff0c;还不是最难的问题 . 大纲 IP问题 IP问题
描述 :
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 …大家好我是苏麟 , 今天带来几道回溯比较困难的题 . 回溯有很多比较难的问题这里我们看两个整体来说这两个只是处理略复杂还不是最难的问题 . 大纲 IP问题 IP问题
描述 :
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
题目 :
LeetCode 93. 复原 IP 地址 :
复原IP地址 : 分析 :
该问题的思路与与前面的分割回文串基本一致也是切割问题。回溯的第一步就是使用枚举将所有可能性搜出来,找到一个符合要求的就先切下来后面的部分继续进行枚举和切割如果到了最后发现不符合要求则开始回溯。
本题的难度明显比上一题要大主要是判断是否合法的要求更高了比如第一个元素我们可以截取2、25255、2552很显然到了2552之后就不合法了此时就要回溯。后面也一样假如我们第一层截取的是2第二层就从”5525511135“中截取此时可以有555552显然552已经不合法了依次类推。画出图来就如下所示: 当然这里还要判断是0的情况等等在字符串转换成数字一章我们讲解了很多种要处理的情况为此我们可以写一个方法单独来执行相关的判断。
另外IP地址只有四段不是无限分割的因此本题只会明确的分成4段不能多也不能少。所以不能用切割线切到最后作为终止条件而是分割的段数到了4就必须终止。考虑到我们构造IP地址时还要手动给添加个小数点所以我们用变量pNum来表示小数点数量pNum为3说明字符串分成了4段了。
要手动添加一个小数点这要增加一个位置来存储所以下一层递归的start要从i2开始。其他的主要工作就是递归和回溯的过程了。这里的撤销部分要注意将刚刚加入的分隔符删掉并且pNum也要-1 .
解析 :
class Solution {ListString list new ArrayList();public ListString restoreIpAddresses(String s) {if(s.length() 4 || s.length() 12){return list;}dfs(s,0,0);return list;}public void dfs(String s,int start,int pNum){if(pNum 3){if(isValue(s,start,s.length() - 1)){list.add(s);}return;}for(int i start;i s.length();i){if(isValue(s,start,i)){s s.substring(0,i 1) . s.substring(i 1);pNum;dfs(s,i 2,pNum);pNum--;s s.substring(0,i 1) s.substring(i 2); }else{break;}}}//判断是否合法public boolean isValue(String s,int start,int end){if(start end){return false;}if(s.charAt(start) 0 start ! end){return false;}int num 0;for(int i start;i end;i){if(s.charAt(i) 9 || s.charAt(i) 0){return false;}num num * 10 (s.charAt(i) - 0);if(num 255){return false;}}return true;}
}这期就到这里 , 下期见!
