问一道谷歌的面试题 - Rythme pattern

能贴下backtracking的代码吗？我之前一直没写出来 谢谢 ！

bodeplot 发表于 2019/02/01 11:17:05


谢啦，我突然想到binomial coefficient也可以用triangle去求，这样binomial coefficient modulo X就不是那么难求了。并且用summation fo...

给我4-5个小时可能想出来

wtcupup 发表于 2019-2-1 15:51
能贴下backtracking的代码吗？我之前一直没写出来 谢谢 ！

您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-2-2 08:45):
不好意思 那个不知道为什么if(visited[i]) 贴上来就成了乱七八糟的了 你自己改一下就行。

补充内容 (2019-2-2 08:45):
不好意思 那个不知道为什么if(visited[i]) 贴上来就成了乱七八糟的了 你自己改一下就行。

wtcupup 发表于 2019-2-1 15:51
能贴下backtracking的代码吗？我之前一直没写出来 谢谢 ！

您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 300 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。。。好难 看了下bell number
脑子晕了 correctness和tuition  


补充内容 (2019-2-2 14:29):
刚看了下 终于感觉明白了

好难啊 没有sterling number 根本想不出
即使想到了sterling number 的规律
也很难想到Bell Number 是sterling的总和

在45分钟。。。

可以这样考虑：假设序列总长为L，而现在已经填充了其中前L-N个位置，那么有多少种方式能够填充剩下的N个位置？

通过观察可知，前L-N个位置中如果出现了R个unique的字母，那么第L-N+1位置上就有R+1个字母可供选择（比如，前5个字符是ABACA，出现了3个unique字母，那么第6个位置上可选的是ABCD这四个字母）。所以，剩下N个位置的填充方式数目和已经出现的unique字母数R相关，记做F(N, R)

如果在这N个位置中的第1位置使用的是已经出现过的R个字母之一，那么剩下的N-1个位置就共有F(N-1, R)种生成方法。因为我们新填充的这个位置并没有扩展unique字母的范围；而如果第1位置使用的是之前没出现的第R+1个字母，那么剩下的N-1个位置则有F(N-1, R+1)种生成方法。因此可得递推式：

F(N, R) = F(N-1, R) * R + F(N-1, R+1)

最后返回F(L, 0)即可

这个式子算出来的其实就是Bell Number: 1, 2, 5, 15, 52, 203 ...

stellari 发表于 2019-2-3 02:59
可以这样考虑：假设序列总长为L，而现在已经填充了其中前L-N个位置，那么有多少种方式能够填充剩下的N个位 ...

这种情况 放到字母的环境了 字母最多只有26个 会不会有影响

ma1doo 发表于 2019-2-3 04:59
这种情况 放到字母的环境了 字母最多只有26个 会不会有影响

在序列长度N > 26时会有影响，这种情况下可以将式子改成

F(N, R) = F(N-1, R) * R;
if (R < 26)  F(N, R)+= F(N-1, R+1)

如果已经使用过了26个unique字母，那么接下来就不用再考虑R+1这种情况了。

stellari 发表于 2019-2-3 02:59
可以这样考虑：假设序列总长为L，而现在已经填充了其中前L-N个位置，那么有多少种方式能够填充剩下的N个位 ...

这个不错！我那个虽然也能计算出bell number，但是复杂度还是你这个好。