7.7复原IP地址(LC93-M)
2023-12-29 16:37:58
算法:
根据题意
有效的 IP 地址 :
(1)由四个整数构成
(2)每个整数位于 0 到 255 之间
(3)每个整数不能含有前导 0,如011、021等,但是可以有单独的一个“0”
(4)整数之间用 '.' 分隔。
其实本质上就是分割问题,把一串数字分成四部分,每部分要满足条件(2)和(3),这四个部分用字符'.'串起来,所以还是用回溯
画树:
回溯三部曲:
1.确定函数返回值和参数
返回值:void
参数:
String s(题目自带)
int startindex:记录下一层递归分割的起始位置。
Int?pointNum;记录添加“.”的数量(要加3个)
2. 确认终止条件,收集合法的数字段:
本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。
pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。
3.单层递归逻辑:
for循环:
//收集结果
for (int i = startIndex; i < s.length(); i++)
[startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.
表示已经分割。
如果不合法就结束本层循环
//递归
同时记录分割符的数量pointNum 要 +1
backtracking(s, i+2, pointNum)
i+2,可以看下图:
i=3时,下一层递归的startindex=5
//回溯
pointNum要-1
将刚刚加入的分隔符.
?删掉
判断子串是否合法
主要考虑到如下三点:
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
判断时遵循“左闭右闭”
先判错
注意:
1.这里的全局变量没有path了
因为result就是一个一维数组,数组由字符串构成
什么时候需要path?
result为二维数组时,比如
正确代码:
class Solution {
//全局变量result
List<String> result = new LinkedList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length()>12) return result;
baktracking (s, 0, 0);
return result;
}
void baktracking (String s, int startindex, int pointNum){
//确定终止条件,收集结果
if (pointNum == 3) {
//判断第三个"."之后的第四段字段是否合法(前三段在单层递归逻辑中判断是否合法)
//若合法,则将该合法字符s加入reslt
//索引从0开始
if (isvalid (s, startindex, s.length()-1)){
result.add(s);
}
return;}
//单层递归逻辑
for (int i= startindex; i< s.length(); i++){
//判断是否合法,合法就加"."
if (isvalid (s, startindex, i)) {
//因为string不可变,所以要重新赋值给一个新的string
s = s.substring(0, i+1)+"."+s.substring(i+1);
//substring左闭右开,所以两个都是i+1
pointNum++;
//递归
baktracking (s, i+2, pointNum);
//回溯
pointNum--;
//因为string不可变,所以要重新赋值给一个新的string
s = s.substring(0, i+1)+s.substring(i+2);
//第二个substring从i+2开始,因为前面有个“.”
}
else break;
}
}
//判断字符串是否合法,左闭右闭
//先判错
//1.每位是正整数,在0-9(题目说s 仅由数字组成)
//2.每个整数位于 0 到 255 之间
//3.不能含有前导 0
boolean isvalid (String s, int start, int end) {
//if (s.length()>12) return false;这里不能写这句话,因为S里面可能有“.”,确实不止12
if (start > end) return false;
int num = 0;
for (int i= start; i<=end ;i++){
if (s.charAt(i) < '0' || s.charAt(i) > '9') return false;
num = num*10+ (s.charAt(i)-'0');
if (num > 255) return false;
}
if (s.charAt(start) == '0' && start != end) return false;
return true;
}
}
优化:
由于string不能直接改,每次都要赋值个新的s,比较占空间;可以使用stringBuilder
优化后的正确代码:
class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backTracking(sb, 0, 0);
return result;
}
private void backTracking(StringBuilder s, int startIndex, int dotCount){
if(dotCount == 3){
if(isValid(s, startIndex, s.length() - 1)){
result.add(s.toString());
}
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isValid(s, startIndex, i)){
s.insert(i + 1, '.');
backTracking(s, i + 2, dotCount + 1);
s.deleteCharAt(i + 1);
}else{
break;
}
}
}
//[start, end]
private boolean isValid(StringBuilder 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++){
int digit = s.charAt(i) - '0';
num = num * 10 + digit;
if(num > 255)
return false;
}
return true;
}
}
时间空间复杂度:
文章来源:https://blog.csdn.net/m0_50696252/article/details/135288918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!