Restore IP Addresses:LeetCode

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/

这道题的解法非常接近于NP问题,也是采用递归的解法。基本思路就是取出一个合法的数字,作为IP地址的一项,然后递归处理剩下的项。可以想象出一颗树,每个结点有三个可能的分支(因为范围是0-255,所以可以由一位两位或者三位组成)。并且这里树的层数不会超过四层,因为IP地址由四段组成,到了之后我们就没必要再递归下去,可以结束了。这里除了上述的结束条件外,另一个就是字符串读完了。可以看出这棵树的规模是固定的,不会像平常的NP问题那样,时间复杂度取决于输入的规模,是指数量级的,所以这道题并不是NP问题,因为他的分支是四段,有限制。代码如下:

public ArrayList<String> restoreIpAddresses(String s) {
    ArrayList<String> res = new ArrayList<String>();
    if(s==null || s.length()==0)
        return res;
    helper(s,0,1,"",res);
    return res;
}
private void helper(String s, int index, int segment, String item, ArrayList<String> res)
{
    if(index>=s.length())
        return;
    if(segment == 4)
    {
        String str = s.substring(index);
        if(isValid(str))
        {
            res.add(item+"."+str);
        }
        return;
    }
    for(int i=1;i<4&&(i+index<=s.length());i++)
    {
        String str = s.substring(index, index+i);
        if(isValid(str))
        {
            if(segment==1)
                helper(s,index+i,segment+1,str,res);
            else
                helper(s,index+i,segment+1,item+"."+str,res);
        }
    }
}
private boolean isValid(String str)
{
    if(str==null || str.length()>3)
        return false;
    int num = Integer.parseInt(str);
    if(str.charAt(0)=='0' && str.length()>1)
        return false;
    if(num>=0 && num<=255)
        return true;
    return false;
}

实现中需要一个判断数字是否为合法ip地址的一项的函数,首先要在0-255之间,其次前面字符不能是0。剩下的就是NP问题的套路了,递归中套一个for循环,不熟悉的朋友可以看看N-Queens哈。

返回栏目页:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

作者:csdn博客 Code_Ganker

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索递归
, string
, arraylist
, return
, oj
, leetcode
, res
, leetcode 注册
, oj问题
解法
restore ip addresses、restore、semi restore、restore defaults、semirestore9,以便于您获取更多的相关知识。

时间: 2024-09-20 23:35:46

Restore IP Addresses:LeetCode的相关文章

[LeetCode]93.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) 思路 基本思路就是取出一

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) C++实现代码: #includ

SQL Server如何限制IP登陆:登陆触发器的运用

一.背景 在MySQL的mysql.User表保存了登陆用户的权限信息,Host和User字段则是关于登陆IP的限制.但是在SQL Server没有这样一个表,那SQL Server有什么办法可以实现类似的安全控制的功能呢? SQL Server 包括三种常规类型的触发器:DML触发器.DDL触发器和登录触发器.DML触发器是比较常使用的,它通常在表或视图中修改数据(INSERT.UPDATE和DELETE 等)为了保证业务数据的完整性和一致性,可以对事务进行回滚等操作:如果你对DDL触发器感兴

Simplify Path:LeetCode

原题链接: http://oj.leetcode.com/problems/simplify-path/ 这道题目是Linux内核中比较常见的一个操作,就是对一个输入的文件路径进行简化.思路比较明确,就是维护一个栈,对于每一个块(以'/'作为分界)进行分析,如果遇到'../'则表示要上一层,那么就是进行出栈操作,如果遇到'./'则是停留当前,直接跳过,其他文件路径则直接进栈即可.最后根据栈中的内容转换成路径即可(这里是把栈转成数组,然后依次添加).时间上不会超过两次扫描(一次是进栈得到简化路径,

4Sum:LeetCode

这道题要求跟3Sum差不多,只是需求扩展到四个的数字的和了.我们还是可以按照3Sum中的解法,只是在外面套一层循环,相当于求n次3Sum.我们知道3Sum的时间复杂度是O(n^2),所以如果这样解的总时间复杂度是O(n^3).代码如下: public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { ArrayList<ArrayList<Integer>> res = new Ar

IP语音:嵌入式系统新应用

IP语音(VoiceoverIP,VoIP)是嵌入式系统的一个新兴应用.许多人看到过将计算机变成电话的应用,但是很少有人看到手机使用网络连接进行语音会话.这类手机与老式电话机的不同之处在于,它们里面有嵌入式操作系统.数字电话具有模拟数字转换器和处理数字信号的支撑电子单元.这类系统使用专用分组交换机(PrivateBranchExchange,PBX)为呼叫提供路由,与老式的模拟电话使用PBX的方式非常相似,采用数字数据只不过使它们的效率更高.IP电话使用IP栈.交换机和路由器代替了模拟交换技术与

基站回传IP化:承载网的新挑战

在电信业务和网络IP化转型的大趋势下,移动运营商的IP化进程也在逐步加速.在电信转型所涉及的众多领域里,移动承载网络的IP化是非常重要的内容之一. 移动承载网络IP化的主要目标是建设一个承载下一代移动业务的.端到端基于IP技术的承载网,基于该IP承载网可运营下一代的.基于IP的移动业务.随着新的IP承载网及其承载的下一代基于IP的移动业务的逐步成熟和规模部署,现有的基于TDM技术的传输网络和其上运行的2G数字移动业务将逐步被替代.从这个意义上说,承载网络及其上运行的业务的IP化程度是电信转型程度

leetcode难度及面试频率

转载自:LeetCode Question Difficulty Distribution               1 Two Sum 2 5 array sort         set Two Pointers 2 Add Two Numbers 3 4 linked list Two Pointers           Math 3 Longest Substring Without Repeating Characters 3 2 string Two Pointers      

LeetCode总结【转】

转自:http://blog.csdn.net/lanxu_yy/article/details/17848219 版权声明:本文为博主原创文章,未经博主允许不得转载. 最近完成了www.leetcode.com的online judge中151道算法题目.除各个题目有特殊巧妙的解法以外,大部分题目都是经典的算法或者数据结构,因此做了如下小结,具体的解题思路可以搜索我的博客:LeetCode题解 题目 算法 数据结构 注意事项 Clone Graph BFS 哈希表 Word Ladder II