驻马店 网站建设,文书写作网站,北京中小企业建站价格,柳州人社app下载今天是第24天刷leetcode#xff0c;立个flag#xff0c;打卡60天。
算法挑战链接 93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
第一想法
题目理解#xff1a;将一串数字字符串变成正确的ip格式的字符串。
这类题目是切分字符串#xff0c;ip一…今天是第24天刷leetcode立个flag打卡60天。
算法挑战链接 93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
第一想法
题目理解将一串数字字符串变成正确的ip格式的字符串。
这类题目是切分字符串ip一共有四组所以是切分三次。
切分字符串的方法第一想到的就是回溯算法。那么使用回溯算法我们也可以和递归那样分三步走
第一步确定入参和返回值
void backtracking3(String s, ListString 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 ListString restoreIpAddresses(String s) {ListString result new ArrayList();if (s.length() 12) return result;backtracking3(s, result);return result;}void backtracking3(String s, ListString 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
今日收获 做题的时候应该需要看一下是否需要前置性做校验。
