栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

[leetCode93 ]复原IP地址(回溯)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

[leetCode93 ]复原IP地址(回溯)

先看一看不用回溯的方法,其实回溯就是用来代替多重for循环的。
这道题由于背景是IP地址,那么限制最多就三轮for循环就可以了,所以不用回溯也可以写出来。
将字符串分为四个子串,然后判断每个子串符不符合要求就可以了,虽然很暴力,但是时间打败了95%,内存打败了76%,也算是还可以的一个方法了。

代码如下:

public List restoreIpAddresses(String s) {
        List ans = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) return ans;
        for (int i = 1; i <= s.length() && i <= 3; i++) {
        //切割第一个子串
            String s1 = s.substring(0, i);
            //判断第一个子串符不符合要求
            if (s1.length() > 1 && s1.charAt(0) == '0') continue;
            if (Integer.parseInt(s1)>255) continue;
            for (int j = i + 1; j <= s.length() && j <= i + 3; j++) {
            	//切割第二个子串并判断
                String s2 = s.substring(i, j);
                if (Integer.parseInt(s2)>255) continue;
                if (s2.length() > 1 && s2.charAt(0) == '0') continue;
                for (int k = j + 1; k <= s.length() && k <= j + 3; k++) {
                	//依次判断子串三、四符不符合要求
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k);
                    if (s3.length() > 1 && s3.charAt(0) == '0') continue;
                    if (s4.length() > 1 && s4.charAt(0) == '0') continue;
                    if (s4.length() > 3 || s4.length() < 1) continue;
                    if (Integer.parseInt(s3)>255||Integer.parseInt(s4)>255) continue;
                    StringBuilder sb = new StringBuilder();
                    sb.append(s1);
                    sb.append(".");
                    sb.append(s2);
                    sb.append(".");
                    sb.append(s3);
                    sb.append(".");
                    sb.append(s4);
                    ans.add(sb.toString());
                }
            }
        }
        return ans;
    }

递归的话,模版是分为三步 的:

  1. 确定参数(字符串s,下个子串的起始位置,当前子串个数)
  2. 确定终止条件(子串有四个并且字符串遍历结束)
  3. 确定循环逻辑

递归的代码如下:

class Solution {
    List ans = new ArrayList<>();
    StringBuilder sb=new StringBuilder();
    public List restoreIpAddresses(String s) {
        traceback(s,0,0);
        return ans;
    }

    public void traceback(String s,int start,int num){
        if (start==s.length()&&num==4){
            ans.add(sb.substring(0,sb.length()-1).toString());
            return;
        }
        if (num==4||start==s.length()) return;
        for (int i=start+1;i<=s.length()&&i-start<4;i++){
            String s1 = s.substring(start, i);
            if (!isValid(s1)) break;
            sb.append(s1+".");
            traceback(s,i,num+1);
            sb.delete(sb.length()-s1.length()-1,sb.length());
        }

    }
    public boolean isValid(String s){
        if (s.length()<1||s.length()>3||Integer.parseInt(s)>255) return false;
        if (s.length()>1&&s.charAt(0)=='0') return false;
        return true;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936406.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号