📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 6066| 回复: 23
跳转到指定楼层
上一主题 下一主题
收起左侧

[动态规划] 问一道谷歌的面试题 - Rythme pattern

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
就是这个Rythme pattern的问题 N行诗的Rythme组合
n=1时,只用输出{"A"} 题目是说因为A =B  =C......
n=2时,结果是{"AA", "AB"}
n =3时,结果是{"AAA","AAB","ABA","ABB","ABC"} (因为AAB和AAC一样 只需要输出AAB。)
我自己用backtracking 找到了 n = 4的结果:
AAAA
AAAB
AABA
AABB
AABC
ABAA
ABAB
ABAC
ABBA
ABBB
ABBC
ABCA
ABCB
ABCC
ABCD

我想问的是:如果不用backtracking 给定了n,如果求当N=n时,pattern的总数?(n <= 26)


补充内容 (2019-2-1 11:22):
给大家点赞!谢谢大家的回答!

评分

参与人数 6大米 +20 收起 理由
suwen_1983 + 3 给你点个赞!
tobebeyond + 5 很有用的信息!
mrno5zzz + 3 感觉要是没见过当场想不好想出来
pandami + 3 给你点个赞!
wtcupup + 5 给你点个赞!

查看全部评分


上一篇:请问一下airbnb电话和onsite时候的coding是要在电脑上编译运行程序吗?
下一篇:在职刷题, 分享一下找到的博客

本帖被以下淘专辑推荐:

推荐
stellari 2019-2-3 02:59:59 | 只看该作者
全局:
可以这样考虑:假设序列总长为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 ...

评分

参与人数 4大米 +8 收起 理由
wangweiming800 + 1 很有用的信息!
majestyhao + 1 给你点个赞!
ma1doo + 3 给你点个赞!
ttforsythe + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
stellari 2019-2-3 05:16:19 | 只看该作者
全局:
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这种情况了。
回复

使用道具 举报

推荐
14417335 2019-2-1 11:18:37 | 只看该作者
全局:
后面再学习一下bodeplot的帖子,

我的思路是这样:
dp【长度】【最后一个字母】【见过的最大字母】。这样就有这样的转移关系:
dp[长度][A][C] 可以通过增加一个A, B, C变为 相应的 dp[长度+1][A][C], dp[长度+1][B][C], dp[长度+1][C][C]
同时,也因为可以加D变成dp[长度+1][D][D]
最后把所有n的可能的数目全部加起来就返回。

  1. public int getPatternCount(int n) {
  2.     int[][][] dp = new int[n + 1][26][26];
  3.     dp[1][0][0] = 1; // 'A'
  4.     for (int len = 1; len != n; len++) {
  5.       for (int j = 0; j != 26; j++) {
  6.         for (int i = 0; i <= j; i++) {
  7.           for (int k = 0; k <= j; k++)
  8.             dp[len + 1][k][j] += dp[len][i][j];
  9.           if (j + 1 != 26)
  10.             dp[len + 1][j + 1][j + 1] += dp[len][i][j];
  11.         }
  12.       }
  13.     }
  14.     int res = 0;
  15.     for (int i = 0; i != 26; i++)
  16.       for (int j = 0; j != 26; j++)
  17.         res += dp[n][i][j];
  18.     return res;
  19.   }
复制代码
回复

使用道具 举报

🔗
 楼主| 杨超越 2019-2-1 09:05:21 | 只看该作者
全局:
我自认为是和刷题网940很像,但是那个地方求重复的和我们这里不一样。。。所以一直很困扰。
回复

使用道具 举报

🔗
SQLite 2019-2-1 09:38:14 | 只看该作者
全局:
原题在哪?没看到
回复

使用道具 举报

全局:
所以要求一个数字还是所有结果的array
回复

使用道具 举报

🔗
 楼主| 杨超越 2019-2-1 10:05:01 | 只看该作者
全局:
pandami 发表于 2019-2-1 10:00
所以要求一个数字还是所有结果的array

一个数字 总数。
如果是array的话就直接backtracking
回复

使用道具 举报

全局:
应该可以dp
回复

使用道具 举报

🔗
bodeplot 2019-2-1 11:04:55 | 只看该作者
全局:
本质上是问有多少种不同的办法把N行partition成不同的set。因为答案本身也很大,所以题目一般会要求给出"答案modulo X",where X is an arbitrary number < MAX_INT。

这个问题已经有比较透彻的研究了:

https://en.wikipedia.org/wiki/Bell_number

这里面也提到了Rhyme Scheme,并且提供了两种计算方法:

1. 可以用"property"下面的"Summation Formula"计算,用时O(N^2)。这种做法比较容易想出来,但是如果那些binomial coefficients都太大,不能存到一个数字里的话,就比较难以实现。如果能求"binomial coefficient modulo X"的话,就可以用modulo的公式求出"答案modulo X"。但是"binomial coefficient modulo X"并不是那么好求的,需要相当的数学功底才能想出求法。

2. 可以用wiki里面的bell triangle来求。如果能想出来这种解法的话,实现起来是非常容易的,只要存"triangle entry modulo X"就可以了。但是这种解法并不好想。Interpretation在这里:

https://en.wikipedia.org/wiki/Bell_triangle

如果从来没见过,并且能在40分钟之内想出来的话,只能说明这个人真的很聪明。当然,这种解法的好处就是非常容易写。所以即使你花了35分钟去想它,5分钟之内也能写完。

补充内容 (2019-2-1 11:07):
第一种做法的O(N^2) runtime是用一个O(N)的DP array去存储结果。第二种做法也是O(N^2) runtime, 空间复杂度也可以优化到O(N), 因为计算过程中只需要Triangle的上一行。

补充内容 (2019-2-1 11:12):
突然想到binomial coefficient也可以用三角形去求。只要在三角形里存modulo X的结果就行了。这样第一种解法也容易实现了。在循环到n的时候先搭建第n行的binomial三角形,然后用这一行去求第n行的bell三角形

补充内容 (2019-2-1 11:13):
时间复杂度O(N^2), 空间复杂度O(N)。如果没有见过的话,这应该是最有可能在45分钟之内想出来的解法了吧。Binomial triangle见这里: https://en.wikipedia.org/wiki/Binomial_coefficient

补充内容 (2019-2-1 11:18):
上面打错了。用第一种方法+binomial triangle的话就不用bell triangle了。应该是先搭建第n行的binomial triangle, 再用这一行去求第N+1个bell number。

评分

参与人数 3大米 +7 收起 理由
ttforsythe + 3 给你点个赞!
乳酸君cyc + 1 赞一个
Airtnp + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 杨超越 2019-2-1 11:12:02 | 只看该作者
全局:
bodeplot 发表于 2019-2-1 11:04
本质上是问有多少种不同的办法把N行partition成不同的set。因为答案本身也很大,所以题目一般会要求给出"答 ...

哈哈哈!给你点个赞!
回复

使用道具 举报

🔗
bodeplot 2019-2-1 11:17:05 | 只看该作者
全局:
杨超越 发表于 2019-2-1 11:12
哈哈哈!给你点个赞!

谢啦,我突然想到binomial coefficient也可以用triangle去求,这样binomial coefficient modulo X就不是那么难求了。并且用summation formula求第N个bell number的时候只需要用第N-1行的binomial triangle,所以这个算法也是O(N^2) time, O(N)space的。

这应该是最有可能在45分钟之内想出来的解法了吧。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表