b********r
发帖数: 26 | 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.
版上没人说答案到底是什么啊？ |
d**********x
发帖数: 4083 | 2 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.
: 版上没人说答案到底是什么啊？
|
b********r
发帖数: 26 | 3 可不可以说的详细点，最好能给个伪码。
【在 d**********x 的大作中提到】
: dp嘛
: 开头去掉一个0-255之间的数字之后就变成了规模为3的子问题。
: 注意状态记录应该很容易的
:
: adresses.
|
C***U
发帖数: 2406 | 4 为什么是dp?
能解释一下么？
我觉得backtack或者recursive比较自然
【在 d**********x 的大作中提到】
: dp嘛
: 开头去掉一个0-255之间的数字之后就变成了规模为3的子问题。
: 注意状态记录应该很容易的
:
: adresses.
|
b********r
发帖数: 26 | |
z****e
发帖数: 9 | 6 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);
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********r
发帖数: 26 | 7 牛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**********e
发帖数: 1145 | 8 好题，刚加入 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**********x
发帖数: 4083 | 9 就是recursive
然后记录状态，应该会比单纯的回溯好一点。
【在 C***U 的大作中提到】
: 为什么是dp?
: 能解释一下么？
: 我觉得backtack或者recursive比较自然
|
w****x
发帖数: 2483 | 10
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**********x
发帖数: 4083 | 11 差不多就行了，做那么多干啥。。
【在 w****x 的大作中提到】
:
: possible
: 别加了, 做不完了....
|
m*****n
发帖数: 204 | 12 严格地说，recursion + 中间结果记录应该叫memoization.
Bottom-up non-recursive的做法才叫dynamic programming.
【在 d**********x 的大作中提到】
: 就是recursive
: 然后记录状态，应该会比单纯的回溯好一点。
|
g****y
发帖数: 240 | 13 为啥不会超过3^4中组合？感觉应该是11^3中组合？
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 直接暴力搜索就行。
|
t****t
发帖数: 6806 | 14 IP地址每一段可能有一位, 两位, 或三位.
当然你可以放小数点, 但是那也是C(11, 3), 不是11^3.
就算是11^3也没多少.
【在 g****y 的大作中提到】
: 为啥不会超过3^4中组合？感觉应该是11^3中组合？
:
: possible
|
h********6
发帖数: 285 | 15 C(10,3)对于IP的实际问题来说多了，每段最多只能3位数字，C（10，3）里很多情况不
满足这个限制。
【在 t****t 的大作中提到】
: IP地址每一段可能有一位, 两位, 或三位.
: 当然你可以放小数点, 但是那也是C(11, 3), 不是11^3.
: 就算是11^3也没多少.
|
d**********x
发帖数: 4083 | 16 多严格？
算法导论介绍dp的时候就说了两种都是。
【在 m*****n 的大作中提到】
: 严格地说，recursion + 中间结果记录应该叫memoization.
: Bottom-up non-recursive的做法才叫dynamic programming.
|
