刚学会个刷漆不贴masking tape的招 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

刚学会个刷漆不贴masking tape的招

刚学会个刷漆不贴masking tape的招# Living

b*r2012-04-14 07:04

1 楼

Given a file contains a list of ip address, but the dot in the ip adress
is missing. How to restore these ip address. The restored ip address means
all possible valid ip address. Should be a super set of original ip adresses.
版上没人说答案到底是什么啊？

r*a2012-04-14 07:04

2 楼

换了根window header，contractor补完dry wall拍屁股走了，领导补漆
问贴tape不，人家说不用。过一会儿就看人家扭着屁股大写意一样刷漆
刷好了，巨潇洒地吐一口气，跟我说：
你去拿纸把frame上的漆都擦掉
-_-b

d*x2012-04-14 07:04

3 楼

dp嘛
开头去掉一个0-255之间的数字之后就变成了规模为3的子问题。
注意状态记录应该很容易的

adresses.

【在 b********r 的大作中提到】

: Given a file contains a list of ip address, but the dot in the ip adress
: is missing. How to restore these ip address. The restored ip address means
: all possible valid ip address. Should be a super set of original ip adresses.
: 版上没人说答案到底是什么啊？

H*72012-04-14 07:04

4 楼

快点是可能的

b*r2012-04-14 07:04

5 楼

可不可以说的详细点，最好能给个伪码。

【在 d**********x 的大作中提到】

: dp嘛
: 开头去掉一个0-255之间的数字之后就变成了规模为3的子问题。
: 注意状态记录应该很容易的
:
: adresses.

t*z2012-04-14 07:04

6 楼

我刷厨房的时候一开始不懂就这么弄得。。。不过必须很快，不然就很费力气

C*U2012-04-14 07:04

7 楼

为什么是dp?
能解释一下么？
我觉得backtack或者recursive比较自然

【在 d**********x 的大作中提到】

: dp嘛
: 开头去掉一个0-255之间的数字之后就变成了规模为3的子问题。
: 注意状态记录应该很容易的
:
: adresses.

b*r2012-04-14 07:04

8 楼

有没有高人能贴段伪码上来

z*e2012-04-14 07:04

9 楼

Java Code: Not tested yet
find(String s, int si, int partNo, Stack stk, List list)
{
int len = s.length();
if(si>=len)return;
if(partNo==4){
if(siString ip = s.substring(si);
if(isValidIP(ip)){
stk.push(ip);
list.add(changeToIP(stk);
stk.pop();
}
}
}
else{
for(int i=1;i<4;i++){
if(si+1<=len){
String ss = s.substring(s,si+i);
if(i<3 || isValidIP(ss)){
stk.push(ss);
find(s,si+i,partNo+1, stk,list);
stk.pop();
}
}//end for if(si+1<=len)
}//end for for loop
}//end for else
}

b*r2012-04-14 07:04

10 楼

牛B！谢了！

【在 z****e 的大作中提到】

: Java Code: Not tested yet
: find(String s, int si, int partNo, Stack stk, List list)
: {
: int len = s.length();
: if(si>=len)return;
: if(partNo==4){
: if(si: String ip = s.substring(si);
: if(isValidIP(ip)){
: stk.push(ip);

i*e2012-04-14 07:04

11 楼

好题，刚加入 OJ.
"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"].
这题其实就是著名的 word segmentation 的简化版，不会超过 3^4 = 81 种组合，不
用 dp 直接暴力搜索就行。

d*x2012-04-14 07:04

12 楼

就是recursive
然后记录状态，应该会比单纯的回溯好一点。

【在 C***U 的大作中提到】

: 为什么是dp?
: 能解释一下么？
: 我觉得backtack或者recursive比较自然

w*x2012-04-14 07:04

13 楼

possible
别加了, 做不完了....

【在 i**********e 的大作中提到】

: 好题，刚加入 OJ.
: "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"].
: 这题其实就是著名的 word segmentation 的简化版，不会超过 3^4 = 81 种组合，不
: 用 dp 直接暴力搜索就行。

d*x2012-04-14 07:04

14 楼

差不多就行了，做那么多干啥。。

【在 w****x 的大作中提到】

:
: possible
: 别加了, 做不完了....