一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 776|回复: 4
收起左侧

[Leetcode] 对于递归的迷惑

[复制链接] |试试Instant~ |关注本帖
我要当码农 发表于 2014-3-28 12:32:00 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
求助各位编程大牛, 我做leetcode的题“Restore IP addresseshttp://oj.leetcode.com/problems/restore-ip-addresses/, 对于递归的应用非常迷茫, 求助。
一下为我尝试理解的答案。
package algorithm.sort;

public class RestoreIPAddress {

        /**
         *  
         * Restore IP Addresses
         *  
         *  
         * Given a string containing only digits, restore it by returning all possible valid IP address combinations.
         
        For example:
        Given "25525511135",
         
        return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
         *
         */  
       
          
            public static void main(String args[]) {  
                System.out.println(restoreIpAddresses("25525511135"));  
            }  
          
            public static ArrayList<String> restoreIpAddresses(String s) {  
                ArrayList<String> al = new ArrayList<String>();  
                if(s.length() > 12){     // 及时过滤  
                    return al;  
                }  
                StringBuilder sb = new StringBuilder();  
                dfs(s, al, sb, 0);  
                return al;  
            }  
             
            public static boolean isValid(String s){  
                if(s.length()==0 || s.length()>3){  
                    return false;  
                }  
                int val = Integer.parseInt(s);  
                if(!String.valueOf(val).equals(s)){     // 防止解析成00.01.010.0类似的情况  
                    return false;  
                }  
                if(val<0 || val>255){  
                    return false;  
                }  
                return true;  
            }  
             
            public static void dfs(String s, ArrayList<String> al, StringBuilder sb, int level){  
                if(level == 3){     // 第3次特别判断,必须取剩下的全部字符串  
                    if(isValid(s)){  
                        sb.append(s);  
                        al.add(sb.toString());      // 最后一次不加.  
                        sb.delete(sb.length()-s.length(), sb.length()); // 撤销动作  
                        return;  
                    }  
                }  
                  
                for(int i=0; i<s.length()-1; i++){  
                    String substr = s.substring(0, i+1);  
                    if(isValid(substr)){  
                        sb.append(substr).append(".");      // 执行动作  
                        dfs(s.substring(i+1), al, sb, level+1);      
                        sb.delete(sb.length()-1-substr.length(), sb.length());  // 撤销动作  
                    }  
                }  
            }  
        }  
Linzertorte 发表于 2014-4-4 13:16:08 | 显示全部楼层
你这个代码太长了。不利于你理解算法的本质。
不知道楼主会不会python
我这题用python做过。
https://github.com/Linzertorte/L ... storeIPAddresses.py
回复 支持 反对

使用道具 举报

 楼主| 我要当码农 发表于 2014-4-8 13:33:34 | 显示全部楼层

万分感谢,我研究研究, 感谢感谢
回复 支持 反对

使用道具 举报

xyz110119120 发表于 2014-4-8 15:17:53 | 显示全部楼层
本帖最后由 xyz110119120 于 2014-4-8 15:22 编辑


没细看楼主的代码,我觉得至少最后一个循环,可以写成1-3的循环,而不是0到s.length()-1。

用笨方法写了个代码,如下:


复制代码

回复 支持 反对

使用道具 举报

xyz110119120 发表于 2014-4-8 15:34:26 | 显示全部楼层

搞了好几次,代码也没黏进去。可能改的次数太多了,上面那个帖子已经不能编辑了。代码如下:


public class Solution {
        public static void main(String args[]) {
               
                int[] len = new int[4];
               
                String ipStr = "25525511135";
               
                int lenIpStr = ipStr.length();
               
                for (len[0]=1; len[0]<=3; len[0]++) {
                        for (len[1]=1; len[1]<=3; len[1]++) {
                                for (len[2]=1; len[2]<=3; len[2]++) {
                                        for (len[3]=1; len[3]<=3; len[3]++) {
                                                if (len[0] + len[1] + len[2] + len[3] == lenIpStr) {
                                                        int start = 0;
                                                        int end = 0;
                                                        int i;
                                                        String[] ip = new String[4];
                                                        for (i=0; i<4; i++) {
                                                                end += len[i];
                                                                ip[i] = ipStr.substring(start, end);
                                                                if (! isValid(ip[i])) {break;}
                                                                start = end;
                                                        }
                                                if (i==4) {
                                                        System.out.println("[" + ip[0] + "." + ip[1] + "." + ip[2] + "." + ip[3] + "]" );
                                                }
                                                }
                                        }
                                }
                        }
                }

        }
       
       
    public static boolean isValid(String s){  
        int val = Integer.parseInt(s);  
        if(!String.valueOf(val).equals(s)){     // 防止解析成00.01.010.0类似的情况  
            return false;  
        }  
        if(val<0 || val>255){  
            return false;  
        }  
        return true;  
    }  
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表