q***y 发帖数: 236 | 1 最近版上面经很少啊。我来贡献一个。
华裔面试官,上来拉家常,聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编
码后的数字字符串,问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有
提出毛病。然后问了时空复杂度。
第二天收到拒信。本来想好好面,挺想去的。可能是我写的太慢,只能move on了。紧
张的状态下比平时练得时候慢很多。 |
j********e 发帖数: 1192 | 2 多少种解码方法?什么意思?
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最近版上面经很少啊。我来贡献一个。 : 华裔面试官,上来拉家常,聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编 : 码后的数字字符串,问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有 : 提出毛病。然后问了时空复杂度。 : 第二天收到拒信。本来想好好面,挺想去的。可能是我写的太慢,只能move on了。紧 : 张的状态下比平时练得时候慢很多。
|
p*****2 发帖数: 21240 | |
i**********e 发帖数: 1145 | 4 你这个由提供一个字典吗?
如果没有字典的话,那么 "123" 不就有 26*25*24 种解法么。
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最近版上面经很少啊。我来贡献一个。 : 华裔面试官,上来拉家常,聊背景10分钟。题目是字母a-z编码为数字1-26。给一个编 : 码后的数字字符串,问有多少种解码方法。我写了暴力递归和DP两种解法。面试官没有 : 提出毛病。然后问了时空复杂度。 : 第二天收到拒信。本来想好好面,挺想去的。可能是我写的太慢,只能move on了。紧 : 张的状态下比平时练得时候慢很多。
|
q***y 发帖数: 236 | 5 比如 11 有解码两种方法: aa 或者 k, 10 只能解码成 j。
【在 j********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多少种解码方法?什么意思?
|
q***y 发帖数: 236 | 6 字母a到z与数字1到26 一一对应.
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个由提供一个字典吗? : 如果没有字典的话,那么 "123" 不就有 26*25*24 种解法么。
|
i**********e 发帖数: 1145 | 7 哦,这个由二爷解释 dp解法吧。
这个要考虑 一个 special case 就是 01 , 0出现在其他digit前面的时候。 |
p*****2 发帖数: 21240 | 8
LZ提到已经用DP解了,所以我想知道他到底怎么解的。也看为什么会被fail掉。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哦,这个由二爷解释 dp解法吧。 : 这个要考虑 一个 special case 就是 01 , 0出现在其他digit前面的时候。
|
i**********e 发帖数: 1145 | |
p*****2 发帖数: 21240 | 10
嗯。感觉如果dfs和dp都做对了,没理由被具呀。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩。我觉得不是速度问题。
|
|
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 嗯。感觉如果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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : "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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写了一个 递归+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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最近版上面经很少啊。我来贡献一个。 : 华裔面试官,上来拉家常,聊背景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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 起始条件有点问题,改了一下。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 起始条件有点问题,改了一下。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 倒数第5行 : if (p[i]!='0') num[i]+=num[i-1]; : 如果p[i]=='0'怎么办? : 我觉得应该把condition去掉
|
|
|
q***y 发帖数: 236 | 21 函数参数是面试官写的,我也觉得很奇怪。
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 另外,函数的signature是你自己写的吗? : 不是应该const char *吗?
|
p*****2 发帖数: 21240 | |
S*******e 发帖数: 379 | 23 哦,明白了,没注意字符的值是从1开始
看着好像没错啊
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : p[i]==0 说明 i-1 is not a valid parsing position。
|
q***y 发帖数: 236 | 24 起始条件有点问题,这个比较tricky。但逻辑我觉得是对的。面试官也没说不对。
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哦,明白了,没注意字符的值是从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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 起始条件有点问题,这个比较tricky。但逻辑我觉得是对的。面试官也没说不对。
|
q***y 发帖数: 236 | 27 面试官看我写完,就work了一遍logic,然后就是问复杂度。我都没机会检查初始条件
。不去想原因了,贡献题目给大家。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有些面试官是这样的。故意不指出来,但偷偷给你扣分了。 : 你给的bottom-up dp解法,要比top-down难且tricky。哪怕初始条件有些错,我觉得没 : 理由拒你。而且你要是面试中提到优化到常数空间解法已经几乎perfect了。
|
i**********e 发帖数: 1145 | 28 恩,赞 move on,感谢你的分享。
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试官看我写完,就work了一遍logic,然后就是问复杂度。我都没机会检查初始条件 : 。不去想原因了,贡献题目给大家。
|
w****x 发帖数: 2483 | |
l*********8 发帖数: 4642 | 30 谢谢分享!
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试官看我写完,就work了一遍logic,然后就是问复杂度。我都没机会检查初始条件 : 。不去想原因了,贡献题目给大家。
|
|
|
q***y 发帖数: 236 | 31 难受了好几天啊。我一直自责写的慢,表现的也不够confident。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,赞 move on,感谢你的分享。
|
q***y 发帖数: 236 | 32 参照glassdoor上的面经,我面试前狂练分层打印二叉树,反转链表,大数相乘这样的
题。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 店面就上这样的题啊!
|
i**********e 发帖数: 1145 | 33 pat pat,dp 在面试来说是比较少出现的题,一般来说给出 recursion+cache 已经很
好了。top-down 的那个思维不容易,需要多做练习磨练和时间积累。
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难受了好几天啊。我一直自责写的慢,表现的也不够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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我写了一个练练 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是打算把本版的所有题都用python写一遍吗 :D : 这个定义两个变量就可以了吧,要学会 KISS :)
|
|
|
q***y 发帖数: 236 | 41 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : LZ这速度还可以吧,怎么会慢呢?
|
p*****2 发帖数: 21240 | 42
这题没那么快吧?估计20分钟能做对就算快的了。
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
|
i**********e 发帖数: 1145 | 43 你夸张了。
这题5-10分钟做出来是 topcoder 世界排名前10或者前100的级别。
【在 q***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只答了一道题。可能面试官觉得这题5到10分钟应该做出来吧。
|
B*******1 发帖数: 2454 | 44 nod, facebook这破玩意,我现在一天上5分钟都觉得多阿,没意思。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你夸张了。 : 这题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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写了一个 递归+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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 兔爷招牌式牛擦的DFS + cache
|
i**********e 发帖数: 1145 | 48 刚把这题加进 OJ "Decode Ways",有兴趣可以测试代码。 |
w****x 发帖数: 2483 | 49
这题很直接所以bottom up也习惯, 我的感觉是这种题找"重复点", 就是递归重复计算
的那个point就是DP要记录的地方.
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 现在越来越习惯bottom up了。感觉思维能handle了。反而不想用dfs了。
|
p*****2 发帖数: 21240 | 50
是呀。不过我碰到这题的时候dp还没这么好,recurion解决的。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这题很直接所以bottom up也习惯, 我的感觉是这种题找"重复点", 就是递归重复计算 : 的那个point就是DP要记录的地方.
|
|
|
l*********8 发帖数: 4642 | 51 赞!
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚把这题加进 OJ "Decode Ways",有兴趣可以测试代码。
|
l*********8 发帖数: 4642 | 52 谢谢:)
我在leetcode上测了一下, 需要加一句:
if (s.size() == 0) return 0;
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么没人赞美这个? 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢:) : 我在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 一年没上过5分钟的飘过
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : nod, facebook这破玩意,我现在一天上5分钟都觉得多阿,没意思。
|
s******k 发帖数: 3716 | 56 手快不需要5分钟
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你夸张了。 : 这题5-10分钟做出来是 topcoder 世界排名前10或者前100的级别。
|
l*********8 发帖数: 4642 | 57 what is mymap?
【在 s******k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 手快不需要5分钟 : 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 就是把那些合适的数字串加进去:“1”,“2”,。。。“26”
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : what is mymap?
|
l*********8 发帖数: 4642 | 59 it's a hashmap?
Can you write code to initialize the map?
【在 s******k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是把那些合适的数字串加进去:“1”,“2”,。。。“26”
|