5118网站的功能广州seo网站
今天是第24天刷leetcode,立个flag,打卡60天。
算法挑战链接
93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
第一想法
题目理解:将一串数字字符串变成正确的ip格式的字符串。
这类题目是切分字符串,ip一共有四组,所以是切分三次。
切分字符串的方法第一想到的就是回溯算法。那么使用回溯算法我们也可以和递归那样分三步走
第一步:确定入参和返回值
void backtracking3(String s, List<String> result);
回溯算法的返回值一般都是void
入参不确定可以先做后面的,使用的时候发现没有就可以确定为入参了
第二步:确定终止条件
if (array.length == 4) {//判断是否是一个正缺的ipif (isIp(array[3])) {result.add(s);}return;}很明显的终止条件,字符串被切割成四份,且每一份都在0-255范围内
第三步:在当前的操作
String tmp = array[array.length - 1];for (int i = 0; i < tmp.length() - 1; i++) {String lastString = tmp.substring(i + 1);String preString = tmp.substring(0, i + 1);String newString = combineString(array, preString, lastString);backtracking3(newString, result);}
找到最后一份,不断的切分,比如111, 会根据1.11、11.1 这样来切分
在回溯算法中是可以考虑剪枝的。
for (int i = 0; i < array.length - 1; i++) {if (! isIp(array[i])) return;}
如果前面的数字不符合ip的规范,那么后面就没有必要在进行递归了
因此完成的代码如下:
class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();if (s.length() > 12) return result;backtracking3(s, result);return result;}void backtracking3(String s, List<String> result) {String[] array = s.split("\\.");for (int i = 0; i < array.length - 1; i++) {if (! isIp(array[i])) return;}if (array.length == 4) {//判断是否是一个正缺的ipif (isIp(array[3])) {result.add(s);}return;}String tmp = array[array.length - 1];for (int i = 0; i < tmp.length() - 1; i++) {String lastString = tmp.substring(i + 1);String preString = tmp.substring(0, i + 1);String newString = combineString(array, preString, lastString);backtracking3(newString, result);}}private static boolean isIp(String s) {if (s.startsWith("0") && s.length() > 1) return false;long currentNum = Long.parseLong(s);return currentNum >= 0 && currentNum <= 255;}private String combineString(String[] array, String preString, String lastString) {StringBuilder sb = new StringBuilder();for (int i = 0; i < array.length - 1; i++) {sb.append(array[i]).append(".");}sb.append(preString).append(".").append(lastString);return sb.toString();}
}
实现过程中遇到哪些困难
实现过程中遇到的困难有
- 错误判断 0开头的也算符合,如032
- 错误判断 0不符合Ip规则,如 0.0.0.0
- 在进行字符串转换数字的时候,没有考虑到较大的数,使用了Integer.parseInt方法,报错了。
- 没有对字符串做过滤,导致 long.parseLong方法报错, 如999999999999999999
今日收获
做题的时候应该需要看一下是否需要前置性做校验。