q***y
发帖数: 236 | 1 最近版上面经很少啊。我来贡献一个。
华裔面试官，上来拉家常，聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编
码后的数字字符串，问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有
提出毛病。然后问了时空复杂度。
第二天收到拒信。本来想好好面，挺想去的。可能是我写的太慢，只能move on了。紧
张的状态下比平时练得时候慢很多。 |
j********e
发帖数: 1192 | 2 多少种解码方法？什么意思？
【在 q***y 的大作中提到】
: 最近版上面经很少啊。我来贡献一个。
: 华裔面试官，上来拉家常，聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编
: 码后的数字字符串，问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有
: 提出毛病。然后问了时空复杂度。
: 第二天收到拒信。本来想好好面，挺想去的。可能是我写的太慢，只能move on了。紧
: 张的状态下比平时练得时候慢很多。
|
p*****2
发帖数: 21240 | |
i**********e
发帖数: 1145 | 4 你这个由提供一个字典吗？
如果没有字典的话，那么 "123" 不就有 26*25*24 种解法么。
【在 q***y 的大作中提到】
: 最近版上面经很少啊。我来贡献一个。
: 华裔面试官，上来拉家常，聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编
: 码后的数字字符串，问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有
: 提出毛病。然后问了时空复杂度。
: 第二天收到拒信。本来想好好面，挺想去的。可能是我写的太慢，只能move on了。紧
: 张的状态下比平时练得时候慢很多。
|
q***y
发帖数: 236 | 5 比如 11 有解码两种方法： aa 或者 k， 10 只能解码成 j。
【在 j********e 的大作中提到】
: 多少种解码方法？什么意思？
|
q***y
发帖数: 236 | 6 字母a到z与数字1到26 一一对应.
【在 i**********e 的大作中提到】
: 你这个由提供一个字典吗？
: 如果没有字典的话，那么 "123" 不就有 26*25*24 种解法么。
|
i**********e
发帖数: 1145 | 7 哦，这个由二爷解释 dp解法吧。
这个要考虑 一个 special case 就是 01 ， 0出现在其他digit前面的时候。 |
p*****2
发帖数: 21240 | 8
LZ提到已经用DP解了，所以我想知道他到底怎么解的。也看为什么会被fail掉。
【在 i**********e 的大作中提到】
: 哦，这个由二爷解释 dp解法吧。
: 这个要考虑 一个 special case 就是 01 ， 0出现在其他digit前面的时候。
|
i**********e
发帖数: 1145 | |
p*****2
发帖数: 21240 | 10
嗯。感觉如果dfs和dp都做对了，没理由被具呀。
【在 i**********e 的大作中提到】
: 恩。我觉得不是速度问题。
|
|
|
q***y
发帖数: 236 | 11 不清楚，贴出code大家分析吧。注释部分是后来加的。
unsigned int num_valid_decodings(char const* n_string) {
if (!n_string) return 0;
int n = strlen(n_string);
if (n==1) {
if(n_string[0]=='0') return 0; // not valid
else return 1;
}
vector num(n, 0);
char *p = (char *) n_string;
if (p[0] == '0') return 0; // not valid
else num[0] = 1;
if (p[0]=='1' ) num[1]=2;
else if (p[0]=='2' && p[1]<='6') num[1]=2;
else num[1] = 1;
for (int i=2; i
if (p[i]!='0') num[i]+=num[i-1];
if (p[i-1]=='1' || p[i-1]=='2'&&p[i]<='6') num[i] += num[i-2];
}
return num[n-1];
}
【在 p*****2 的大作中提到】
:
: 嗯。感觉如果dfs和dp都做对了，没理由被具呀。
|
i**********e
发帖数: 1145 | |
s*******a
发帖数: 8827 | |
q***y
发帖数: 236 | 14 起始条件有点问题，改了一下。
unsigned int num_valid_decodings(char const* n_string) {
if (!n_string) return 0;
int n = strlen(n_string);
if (n==1) {
if(n_string[0]=='0') return 0; // not valid
else return 1;
}
vector num(n, 0);
char *p = (char *) n_string;
if (p[0] == '0') return 0; // not valid
else num[0] = 1;
if (p[1]!='0') num[1]+=num[0];
if (p[0]=='1' || p[0]=='2' && p[1]<='6') num[1]++;
for (int i=2; i
if (p[i]!='0') num[i]+=num[i-1];
if (p[i-1]=='1' || p[i-1]=='2'&&p[i]<='6') num[i] += num[i-2];
}
return num[n-1];
}
【在 i**********e 的大作中提到】
: "10" 你的返回 2，应该返回 1 才对吧
|
i**********e
发帖数: 1145 | 15 写了一个 递归+cache，这题还可以再优化。
int cache[512];
int solve(const string &num, int idx) {
if (cache[idx] != -1) return cache[idx];
if (idx == num.length()) return 1;
if (num[idx] == '0') return 0;
if (idx == num.length()-1) return 1;
int count = solve(num, idx+1);
if (num[idx] == '1' || (num[idx] == '2' && num[idx+1] <= '6'))
count += solve(num, idx+2);
cache[idx] = count;
return count;
}
int solve(const string &num) {
for (int i = 0; i < 512; i++)
cache[i] = -1;
if (num.length() == 0)
return 0;
return solve(num, 0);
} |
q***y
发帖数: 236 | 16 空间可以优化到O(1)。只需记录前两位的个数就可以了。我觉得对全1,2字串，就是斐
波那契数。
【在 i**********e 的大作中提到】
: 写了一个 递归+cache，这题还可以再优化。
: int cache[512];
: int solve(const string &num, int idx) {
: if (cache[idx] != -1) return cache[idx];
:
: if (idx == num.length()) return 1;
: if (num[idx] == '0') return 0;
: if (idx == num.length()-1) return 1;
:
: int count = solve(num, idx+1);
|
d****o
发帖数: 1055 | 17 int decode(vector in, int begin, int end){
if(begin>end) return 1;
if(begin==end&&in[begin]==0) return 0;
if(begin==end) return 1;
int cur = in[begin]*10+in[begin+1];
if(cur>=0&&cur<=9){
return 0;
}else if(cur==10||cur==20){
return begin+2<=end?decode(in,begin+2,end):1;
}else if((cur>=11&&cur<=19)||(cur>=21&&cur<=26)){
return decode(in,begin+1,end)+decode(in,begin+2,end);
}else{
return decode(in,begin+1,end);
}
}
int decodeWrapper(vector in){
for(int i=0;i
assert(in[i]>=0&&in[i]<=9);
}
return decode(in,0,in.size()-1);
}
【在 q***y 的大作中提到】
: 最近版上面经很少啊。我来贡献一个。
: 华裔面试官，上来拉家常，聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编
: 码后的数字字符串，问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有
: 提出毛病。然后问了时空复杂度。
: 第二天收到拒信。本来想好好面，挺想去的。可能是我写的太慢，只能move on了。紧
: 张的状态下比平时练得时候慢很多。
|
S*******e
发帖数: 379 | 18 倒数第5行
if (p[i]!='0') num[i]+=num[i-1];
如果p[i]=='0'怎么办？
我觉得应该把condition去掉
【在 q***y 的大作中提到】
: 起始条件有点问题，改了一下。
: unsigned int num_valid_decodings(char const* n_string) {
: if (!n_string) return 0;
: int n = strlen(n_string);
: if (n==1) {
: if(n_string[0]=='0') return 0; // not valid
: else return 1;
: }
: vector num(n, 0);
: char *p = (char *) n_string;
|
S*******e
发帖数: 379 | 19 另外，函数的signature是你自己写的吗？
不是应该const char *吗？
【在 q***y 的大作中提到】
: 起始条件有点问题，改了一下。
: unsigned int num_valid_decodings(char const* n_string) {
: if (!n_string) return 0;
: int n = strlen(n_string);
: if (n==1) {
: if(n_string[0]=='0') return 0; // not valid
: else return 1;
: }
: vector num(n, 0);
: char *p = (char *) n_string;
|
q***y
发帖数: 236 | 20 p[i]==0 说明 i-1 is not a valid parsing position。
【在 S*******e 的大作中提到】
: 倒数第5行
: if (p[i]!='0') num[i]+=num[i-1];
: 如果p[i]=='0'怎么办？
: 我觉得应该把condition去掉
|
|
|
q***y
发帖数: 236 | 21 函数参数是面试官写的，我也觉得很奇怪。
【在 S*******e 的大作中提到】
: 另外，函数的signature是你自己写的吗？
: 不是应该const char *吗？
|
p*****2
发帖数: 21240 | |
S*******e
发帖数: 379 | 23 哦，明白了，没注意字符的值是从1开始
看着好像没错啊
【在 q***y 的大作中提到】
: p[i]==0 说明 i-1 is not a valid parsing position。
|
q***y
发帖数: 236 | 24 起始条件有点问题，这个比较tricky。但逻辑我觉得是对的。面试官也没说不对。
【在 S*******e 的大作中提到】
: 哦，明白了，没注意字符的值是从1开始
: 看着好像没错啊
|
l*********8
发帖数: 4642 | 25 inline bool valid(char c,char v) {return c=='1'||(c=='2'&&v<='6');}
inline bool valid(char c) {return c!='0';}
int decodingNum(const string & s)
{
char c1('0');
int n0(1), n1(1), n(1);
for (int i=0; i0; ++i) {
n = n0*valid(c1,s[i]) + n1*valid(s[i]);
n0 = n1; n1 = n;
c1 = s[i];
}
return n;
} |
i**********e
发帖数: 1145 | 26 有些面试官是这样的。故意不指出来，但偷偷给你扣分了。
你给的bottom-up dp解法，要比top-down难且tricky。哪怕初始条件有些错，我觉得没
理由拒你。而且你要是面试中提到优化到常数空间解法已经几乎perfect了。
【在 q***y 的大作中提到】
: 起始条件有点问题，这个比较tricky。但逻辑我觉得是对的。面试官也没说不对。
|
q***y
发帖数: 236 | 27 面试官看我写完，就work了一遍logic，然后就是问复杂度。我都没机会检查初始条件
。不去想原因了，贡献题目给大家。
【在 i**********e 的大作中提到】
: 有些面试官是这样的。故意不指出来，但偷偷给你扣分了。
: 你给的bottom-up dp解法，要比top-down难且tricky。哪怕初始条件有些错，我觉得没
: 理由拒你。而且你要是面试中提到优化到常数空间解法已经几乎perfect了。
|
i**********e
发帖数: 1145 | 28 恩，赞 move on，感谢你的分享。
【在 q***y 的大作中提到】
: 面试官看我写完，就work了一遍logic，然后就是问复杂度。我都没机会检查初始条件
: 。不去想原因了，贡献题目给大家。
|
w****x
发帖数: 2483 | |
l*********8
发帖数: 4642 | 30 谢谢分享！
【在 q***y 的大作中提到】
: 面试官看我写完，就work了一遍logic，然后就是问复杂度。我都没机会检查初始条件
: 。不去想原因了，贡献题目给大家。
|
|
|
q***y
发帖数: 236 | 31 难受了好几天啊。我一直自责写的慢，表现的也不够confident。
【在 i**********e 的大作中提到】
: 恩，赞 move on，感谢你的分享。
|
q***y
发帖数: 236 | 32 参照glassdoor上的面经，我面试前狂练分层打印二叉树，反转链表，大数相乘这样的
题。
【在 w****x 的大作中提到】
: 店面就上这样的题啊！
|
i**********e
发帖数: 1145 | 33 pat pat，dp 在面试来说是比较少出现的题，一般来说给出 recursion+cache 已经很
好了。top-down 的那个思维不容易，需要多做练习磨练和时间积累。
【在 q***y 的大作中提到】
: 难受了好几天啊。我一直自责写的慢，表现的也不够confident。
|
E*******0
发帖数: 465 | 34 我也来说说我的DP思路。
用一个表格T(i)表示输入str[i to n]所有可能解码。
//T(n)=1;
if (i==n && str[i]>0) return 1;
//T(n-1)=1 or 2
if (i==n-1 && 0
if (i==n-1 && str[n-1]str[n]>26) return 1;
if (str[i]==1 && str[i-1]>0) || (str[i]==2 && <0str[i-1]<=6)
//0<"str[i]str[i-1]"<=26
T[i]=T[i-1]+T[i-2];
else
T[i]=T[i-1]; |
E*******0
发帖数: 465 | 35 time computation complexity is n;
space is also n. |
p*****2
发帖数: 21240 | 36 我写了一个练练
def count(str):
if not (str and len(str)):
return 0
l=len(str)
dp=[1]*2
if str[-1]=='0':
dp[1]=0
for i in xrange(2,l+1):
if str[-i]=='0':
dp[i%2]=0
else:
c=dp[(i+1)%2]
if str[l-i:l-i+2]<="26":
c+=dp[i%2]
dp[i%2]=c
return dp[l%2] |
i**********e
发帖数: 1145 | 37 你是打算把本版的所有题都用python写一遍吗 :D
这个定义两个变量就可以了吧，要学会 KISS :)
【在 p*****2 的大作中提到】
: 我写了一个练练
: def count(str):
: if not (str and len(str)):
: return 0
:
: l=len(str)
: dp=[1]*2
: if str[-1]=='0':
: dp[1]=0
:
|
Z*****Z
发帖数: 723 | 38 为什么没人赞美这个？ Orz 注意队形。。
【在 l*********8 的大作中提到】
: inline bool valid(char c,char v) {return c=='1'||(c=='2'&&v<='6');}
: inline bool valid(char c) {return c!='0';}
: int decodingNum(const string & s)
: {
: char c1('0');
: int n0(1), n1(1), n(1);
: for (int i=0; i0; ++i) {
: n = n0*valid(c1,s[i]) + n1*valid(s[i]);
: n0 = n1; n1 = n;
: c1 = s[i];
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 40
准备再练一个星期。你说的这个什么意思呀？
这个定义两个变量就可以了吧，要学会 KISS :)
【在 i**********e 的大作中提到】
: 你是打算把本版的所有题都用python写一遍吗 :D
: 这个定义两个变量就可以了吧，要学会 KISS :)
|
|
|
q***y
发帖数: 236 | 41 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
【在 p*****2 的大作中提到】
: LZ这速度还可以吧，怎么会慢呢？
|
p*****2
发帖数: 21240 | 42
这题没那么快吧？估计20分钟能做对就算快的了。
【在 q***y 的大作中提到】
: 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
|
i**********e
发帖数: 1145 | 43 你夸张了。
这题5-10分钟做出来是 topcoder 世界排名前10或者前100的级别。
【在 q***y 的大作中提到】
: 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
|
B*******1
发帖数: 2454 | 44 nod, facebook这破玩意，我现在一天上5分钟都觉得多阿，没意思。
【在 i**********e 的大作中提到】
: 你夸张了。
: 这题5-10分钟做出来是 topcoder 世界排名前10或者前100的级别。
|
w****x
发帖数: 2483 | 45 int _inner_ways(const char* pStr)
{
if (*pStr == 0)
return 1;
if (*pStr <= '0' || *pStr > '9')
return 0;
int n = _inner_ways(pStr+1);
if ((*pStr == '1' && *(pStr + 1) >= '0' && *(pStr + 1) <= '9')
|| (*pStr == '2' && *(pStr + 1) >= '0' && *(pStr + 1) <= '6'))
n += _inner_ways(pStr+2);
return n;
}
int GetWays(const char* pStr)
{
if (NULL == pStr || *pStr == 0)
return 0;
return _inner_ways(pStr);
}
int GetWaysDP(const char* pStr)
{
if (NULL == pStr || *pStr == 0)
return 0;
int nLen = strlen(pStr);
int* pDP = new int[nLen+1];
pDP[nLen] = 1; // 1 not 0
if (pStr[nLen-1] > '0' && pStr[nLen-1] <= '9')
pDP[nLen-1] = 1;
else pDP[nLen-1] = 0;
for (int i = nLen-2; i >= 0; i--)
{
int nTmp = 0;
if (pStr[i] > '0' && pStr[i] <= '9')
nTmp += pDP[i+1];
if ((pStr[i] == '1' && pStr[i+1] >= '0' && pStr[i+1] <= '9') ||
(pStr[i] == '2' && pStr[i+1] >= '0' && pStr[i+1] <= '6'))
nTmp += pDP[i+2];
pDP[i] = nTmp;
}
int nRet = pDP[0];
delete[] pDP;
return nRet;
}
20分钟白板,然后发现各种少了分号引号的情况,敲进IDE又发现一个bug, 最后发现DP空
间复杂度可以是O(1). |
w****x
发帖数: 2483 | 46
兔爷招牌式牛擦的DFS + cache
【在 i**********e 的大作中提到】
: 写了一个 递归+cache，这题还可以再优化。
: int cache[512];
: int solve(const string &num, int idx) {
: if (cache[idx] != -1) return cache[idx];
:
: if (idx == num.length()) return 1;
: if (num[idx] == '0') return 0;
: if (idx == num.length()-1) return 1;
:
: int count = solve(num, idx+1);
|
p*****2
发帖数: 21240 | 47
现在越来越习惯bottom up了。感觉思维能handle了。反而不想用dfs了。
【在 w****x 的大作中提到】
:
: 兔爷招牌式牛擦的DFS + cache
|
i**********e
发帖数: 1145 | 48 刚把这题加进 OJ "Decode Ways"，有兴趣可以测试代码。 |
w****x
发帖数: 2483 | 49
这题很直接所以bottom up也习惯, 我的感觉是这种题找"重复点", 就是递归重复计算
的那个point就是DP要记录的地方.
【在 p*****2 的大作中提到】
:
: 现在越来越习惯bottom up了。感觉思维能handle了。反而不想用dfs了。
|
p*****2
发帖数: 21240 | 50
是呀。不过我碰到这题的时候dp还没这么好，recurion解决的。
【在 w****x 的大作中提到】
:
: 这题很直接所以bottom up也习惯, 我的感觉是这种题找"重复点", 就是递归重复计算
: 的那个point就是DP要记录的地方.
|
|
|
l*********8
发帖数: 4642 | 51 赞！
【在 i**********e 的大作中提到】
: 刚把这题加进 OJ "Decode Ways"，有兴趣可以测试代码。
|
l*********8
发帖数: 4642 | 52 谢谢：）
我在leetcode上测了一下， 需要加一句：
if (s.size() == 0) return 0;
【在 Z*****Z 的大作中提到】
: 为什么没人赞美这个？ Orz 注意队形。。
|
B*******1
发帖数: 2454 | 53 你的code的确牛，学习了。
但是我肯定写不出来，改了一下思路，在string前面pack了一个10，再计算，绕过很多
一开始的初始条件
int decodeString(const string &s)
{
if (s.size() == 0) return 0;
string str2 = "10" + s;
const char *str = str2.c_str();
int a = 1, b = 1, c;
str += 2;
while (*str) {
c = 0;
if (*(str-1) == '1' || (*(str-1) == '2' && *str <= '6'))
c += a;
if (*str != '0')
c += b;
a = b;
b = c;
str++;
}
return c;
}
【在 l*********8 的大作中提到】
: 谢谢：）
: 我在leetcode上测了一下， 需要加一句：
: if (s.size() == 0) return 0;
|
S*****B
发帖数: 404 | 54 public int check(String s) {
if (s.length() == 0)
return 0;
int n = s.length();
if (n == 1) {
if (s.charAt(0) == '0')
return 0; // not valid
else
return 1;
}
int[] num = new int[n];
if (s.charAt(0) == '0')
return 0; // not valid
else
num[0] = 1;
if (s.charAt(1) != '0')
num[1] += num[0];
if (s.charAt(0) == '1' || (s.charAt(0) == '2' && s.charAt(1) <= '6'))
num[1]++;
for (int i = 2; i < n; i++) {
if (s.charAt(i) == '0') {
if (s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') {
return 0;
}
}
if (s.charAt(i) != '0')
num[i] += num[i - 1];
if (s.charAt(i - 1) == '1'
|| (s.charAt(i - 1) == '2' && s.charAt(i) <= '6'))
num[i] += num[i - 2];
}
return num[n - 1];
}
JAVA leetcode pass了已经
Run Status: Accepted!
Program Runtime: 480 milli secs
Progress: 255/255 test cases passed. |
s******k
发帖数: 3716 | 55 一年没上过５分钟的飘过
【在 B*******1 的大作中提到】
: nod, facebook这破玩意，我现在一天上5分钟都觉得多阿，没意思。
|
s******k
发帖数: 3716 | 56 手快不需要５分钟
int getNumDecode(const char *str)
{
char temp[3]; temp[1] = temp[2] = '\0';
if(strlen(str) == 0) return 1;
int num = 0;
temp[0] = str[0];
if(mymap[temp)>0) // we have 1 digit decode a letter
num += getNumDecode(str+1);
if(strlen(str)==1) return num;
temp[1] = str[1];
if(mymap[temp]>0) // we have 2 digits decode a letter
num += str+2;
return num;
}
【在 i**********e 的大作中提到】
: 你夸张了。
: 这题5-10分钟做出来是 topcoder 世界排名前10或者前100的级别。
|
l*********8
发帖数: 4642 | 57 what is mymap?
【在 s******k 的大作中提到】
: 手快不需要５分钟
: int getNumDecode(const char *str)
: {
: char temp[3]; temp[1] = temp[2] = '\0';
: if(strlen(str) == 0) return 1;
: int num = 0;
: temp[0] = str[0];
: if(mymap[temp)>0) // we have 1 digit decode a letter
: num += getNumDecode(str+1);
: if(strlen(str)==1) return num;
|
s******k
发帖数: 3716 | 58 就是把那些合适的数字串加进去：“１”，“２”，。。。“２６”
【在 l*********8 的大作中提到】
: what is mymap?
|
l*********8
发帖数: 4642 | 59 it's a hashmap?
Can you write code to initialize the map?
【在 s******k 的大作中提到】
: 就是把那些合适的数字串加进去：“１”，“２”，。。。“２６”
|
