原题链接: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哈。
分享到:
相关推荐
leetcode盒子嵌套 leetcode-text 92.Reverse Linked List II Runtime: 4 ms, faster than 67.04% of C online submissions for Reverse Linked List II. Memory Usage: 6.9 MB, less than 100.00% of C online ...
pivotal_greenplum_backup_restore-1.20.2-gp6-rhel-x86_64.gppkg
描述文件 只能下载 iOS 13.1 的beta版 需要13.0 的话 需要自己先升级mac 系统到10.15的beta版 再去这个地址下载手机相应的固件 https://developer.apple.com/download/#ios-restore-images-iphone-new 通过ituns ...
093:Restore IP Addresses 树的遍历问题也可以用这种思想来解释。只不过是特殊的递归而已。(只有两路,不用循环) 题型二:动态规划(要整理搜索和DP的区别,都可以用一个状态转移公式F(n)表示) 053:最大字串...
群晖restore工具
leetcode rust leetcode leetcode的代码 每一题至少会提供一种解法,如果有更优的会补上 分别用golang,rust实现。...restore-string创建的rust项目 └── src └── lib.rs #包含rust实现和test代码
restoreIPAddresses 复原IP地址 threeSum 三数之和 search 搜索旋转排序数组 1. 3. 9. 75. 209. 219. 167. 268. 344. 349. 454. 447. 695. 674. string 字符串 20. 150. linklist 链表 19. 24. 86. 92. 203. 206. ...
S3时间点还原这是s3-pit-restore的存储库,它是Amazon S3的时间点还原工具。 您可能需要此工具的典型情况是在S3存储桶上启用了版本控制,并且想要将某些或所有文件还原到某个时间点,本地文件系统,相同的S3存储桶或...
Firefox: : //addons.mozilla.org/addon/restore-closed-tabs/ Chrome浏览器: https : //chrome.google.com/webstore/detail/restore-closed-tabs/fgiohnfjhpibbbanlanpneaajbepldkg?hl = zh-CN 特征 显示...
linux-bash-script-to-backup-restore-tvheadend-server-configuration 可以运行此脚本来备份TVHeadend服务器配置(/home/hts/.hts/tvheadend)或从备份(/home/hts/.hts/tvheadend_backup.tar)还原它。 我认为它...
ip6tables-restore命令用来还原ip6tables表。 语法格式:ip6tables-restore [参数] 常用参数: -c 指定在还原iptables表时候,还原当前的数据包计数器和字节计数器的值 -t 指定要还原表的名称 参考实例...
Linux restore命令 ...restore [-cCvy][-b ][-D ][-f ][-s ] 或 restore [-chimvy][-b ][-f ][-s ] 或 restore [-crvy][-b ][-f ][-s ] 或 restore [-cRvy][-b ][-D ][-f ][-s ] 或 restore [chtvy][-b ][-D
Algorithm:restore-ip-addresses(递归) Review:redis sentinel conf Tip:redis查看主从同步是否完成 Share:学习总结 - docker的基本使用 第一周 Algorithm:reverse-linked-list-ii(链表) Review:linux编程...
Informix V12.10--Backup and Restore Guide-285
restore-symbol
语言:English 备份和加密所有cookie,并在需要时解密和还原它们。 有新机器还是想重新安装操作系统? 但是不想重新登录到您的所有帐户吗? 使用此扩展程序备份您所有的珍贵cookie,并在以后还原它们。...
Backup and Restore SDK BOSH版本用于两个不同的方面: 使发行版作者可以在其发行版中纳入数据库备份和还原功能(请参阅) 使操作员能够配置其使用外部Blob存储的部署,并通过(请参阅Blob存储) Slack : ://...
## cf_backup_restore-Cloudflare-用于在Cloudflare帐户/区域上备份/还原数据的工具cf_backup_restore是python工具,用于从Cloudflare帐户/区域导出和/或导入数据安装请先克隆存储库: git clone 安装Python并安装...
plymouth rpm pakage of myself file , and there is no value