Restore IP Addresses -- LeetCode
2024-08-26 04:52:14
原题链接: 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。
最新文章
- 百度地图SDK
- likely &;&; unlikely in GCC
- ASP.NET操作ORACLE数据库之模糊查询
- ilbc编解码
- 【转载】ANSYS有限元分析中的单位问题
- 使用Jil序列化JSON提升Asp.net web api 性能
- sirius的python学习笔记(1)
- Windows Server 2008 网站访问PHP响应慢的解决方法
- 讯飞语音SDK Android平台使用
- 如何:对 Web 窗体使用路由
- MVC超链接
- Windows下一个AndroidStudio 正在使用Git(AndroidStudio工程GitHub关联)
- 2017寒假零基础学习Python系列之函数之 返回多个值
- [20190417]隐含参数_SPIN_COUNT.txt
- 蒟阵P3390 【模板】矩阵快速幂
- 【转】python3解析库lxml
- Centos配置tomcat服务并且开机自启动
- oracle 连接字符串的问题
- springboot 中事件监听模型的一种实现
- XlsToOra
热门文章
- 【找规律】Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined) B. Code For 1
- 【点分治】bzoj1468 Tree
- Problem N: 猴子吃桃
- nginx 实现 ajax 跨域请求
- 针对标签中设置 disabled=";true";,$(";#id";).serialize()获取不到value的解决方法
- ";0"; 并不一定是 假 (false)
- C#文本之XML
- 转:RESTful架构详解
- docker实战——Docker本地私有镜像仓库Harbor搭建及配置
- Docker默认存储路径修改