说道谷歌的 onsite 题目letter 选择

n 个位置,即 1,2,…,n

从左往右开始往里面放letter,letter的选择规则是,要么从已经出现过的letter里选,要么就是一个新的letter

位置1: 只能是A
位置2: A 或 B
位置3: 如果你在位置2选了A,那么选择是A或B。如果你在位置2选了B,那么你可以选 A,B或C。
以此类推。

求n个位置,有多少种不同的String

1 Like

如果是C后面跟什么

这不是非常基础的矩阵优化的动态规划么

如果是C,说明A,B,C已经出现过了,那么你有四个选择,多了一个D

dp该怎么解?

可以认为字母数字上限是个常数,比如26。但解题时候这个是个input

最基本的解法是:
dp[i][j] 代表 前 i 个位置一共用了 j 种字母。
dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]
如果就 26 个字母的话,那么可以用矩阵优化
复杂度可以做到 26 * 26 * 26 * log(n)

1 Like

目测是对的,你说的矩阵优化是指把二维矩阵降成一维吗?

还是二维,但是能用矩阵乘法快速幂降低n的计算复杂度

不是为了优化空间?
是优化runtime对吗?

对的,用空间换时间。

谷歌letter 选择题 微信群上的聊天记录如下,请查收。

————— 2019-01-29 —————

king~蛙 00:07

老师 是不是dp[i] = dp[i-1]*(i-1) (i 1) 啊?

Shawn Dong 00:07

不是吧。。

X 00:08

让人猜吗,给方程不解释一下?

X 00:08

面试这样不行

X 00:08

你默认人家是你肚子里的蛔虫吗

X 00:08

i是什么,神仙知道

king~蛙 00:08

king~蛙 00:08

草稿打的有点乱

X 00:09

天书看不懂

king~蛙 00:09

[捂脸]

X 00:11

你面试的时候如果没法解释清楚

X 00:11

即使对了

X 00:11

也过不了

Shawn Dong 00:11

是最多有26个字母么

Shawn Dong 00:12

还是有无限多个字母?

X 00:12

可以认为字母上线是个常数,比如26。但解题时候这个是给input

Shawn Dong 00:12

oyashiroshama 00:12

dp[4]的值不对吧。。

Shawn Dong 00:12

那 n 能做 1e18 的

X 00:13

dp对不对自己就能测吧

X 00:13

n可以很大

Shawn Dong 00:13

Shawn Dong 00:13

n 能做 1e18 的

X 00:14

1e18有什么特殊含义吗

Shawn Dong 00:14

long 的最大值

X 00:14

[机智]

Shawn Dong 00:14

当然如果有足够多的可以做2^1000 级别的

king~蛙 00:14

我觉得 就是 当前选择的时候 有n-1种可能是选择之前已经出现过的 那就乘以上一个level的dp值 然后新出现的字母 又可以有n种新的可能

X 00:15

别用n了吧

X 00:15

很困惑

X 00:15

换成k啊啥的

X 00:15

n这里说了是n个位置

king~蛙 00:15

X 00:16

发现这位同学给人一种表达不清的印象

Shawn Dong 00:16

dp[i][j] 代表 前 i 个位置一共用了 j 种字母。
dp[i][j] = (dp[i - 1][j] dp[i - 1][j - 1]) * j
如果就 26 个字母的话,那么可以用矩阵优化
复杂度可以做到 262626*log(n)

X 00:16

面试很负面的

X 00:17

这个递推可以解释一下吗?看上去是得用二维dp

Shawn Dong 00:17

dp[i][j] 代表 前 i 个位置一共用了 j 种字母

Shawn Dong 00:18

要么前 i - 1 的位置已经一共用了 j 种

Shawn Dong 00:18

要么 i - 1 的位置用了 j - 1 种

Shawn Dong 00:18

。。。抱歉写错了 2333

Shawn Dong 00:18

dp[i][j] = dp[i - 1][j] * j dp[i - 1][j - 1]

Shawn Dong 00:19

如果用了 j 种想转移到 dp[i][j] 的那么随便取一个

Shawn Dong 00:19

如果用了 j - 1 种想转移到 j 的只能是新的哪一个

X 00:20

目测是对的

Shawn Dong 00:20

所以复杂度要么是 26 * n 要么是 26^3*log(n)

king~蛙 00:20

好厉害

X 00:21

这思路应该是正解

X 00:21

然后就是写代码了

X 00:21

[机智]

Shawn Dong 00:22

我写个26^3*log(n)得把

X 00:22

[表情]

Shawn Dong 00:22

确定是 26 个字母哈

X 00:22

X 00:22

其实下一问就是26个字母

X 00:22

相当于followup

Shawn Dong 00:24

答案能对某个数取Mod 么。。。

Shawn Dong 00:24

否则可能存不下。。

X 00:24

你是怕太大?

Shawn Dong 00:24

是啊

X 00:24

这又不是leetcode

Shawn Dong 00:24

这是爆炸式增长的

Shawn Dong 00:24

哦好的

X 00:25

测n也不需要很大数

Shawn Dong 00:25

那26^3*log(n)的就没用了 TT 难受

X 00:25

你那个矩阵优化太高级了吧

Shawn Dong 00:26

T——T

Shawn Dong 00:26

好吧

X 00:26

但是写程序用的着这种数学吗?毕竟乘法开销大吧

Shawn Dong 00:26

看你怎么想了

Shawn Dong 00:26

如果n 真的很大

Shawn Dong 00:26

那么的确要用这个优化就是了

Shawn Dong 00:26

比如 n 是 1e9 级别的

Shawn Dong 00:27

你不能写个 26*n 的吧

X 00:27

我好像不太见到面试会这么操作。不过这么做的,想到这个的,我肯定给strong了

Shawn Dong 00:27

那我还是写个26n最省空间的吧

X 00:27

一般面试到这步就可以啦

X 00:28

不是搞竞赛

X 00:28

能答到这步,把代码写出来,估计也没几个人

X 00:29

后面的优化我怕你把面试官讲晕,因为面试官未必听得懂

Shawn Dong 00:29

lol

X 00:29

事实确实是这样[捂脸]

X 00:29

我上课一般强调表达思路清晰

X 00:29

这是最重要的

X 00:29

搞的很高深在面试中其实可能会反效果

X 00:30

毕竟面试官也是凡人

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int dp[2][27] , n;
int main(){
    cin >> n;
    memset(dp , 0 , sizeof(dp));
    dp[0][1] = 1;
    int last = 0;
    for (int i = 1 , u = 0 , v = 1 ; i < n ; i ++ , swap(u , v)){
        memset(dp[v] , 0 , sizeof(dp[v]));
        for (int j = 1 ; j <= 26 ; ++j) if (dp[u][j]){
            dp[v][j] += j * dp[u][j];
            if (j < 26) dp[v][j + 1] += dp[u][j];
        }
        last = v;
    }
    int ans = 0;
    for (int i = 1 ; i <= 26 ; ++i)
        ans += dp[last][i];
    cout << ans << endl;
    return 0;
}
2 Likes

这个好像不对吧,还得加上dp[i-1][j-2]+dp[i-1][j-3]+…

@Shawn_Dong 是对的,你再理解理解

我拿ABCD试了一下,dp[4][3]会漏dp[3][1]这个解,也就是AAA

是么?我得再看看

我想了想,我可能理解错他这里dp的含义了。他这里dp[4][3]应该是指由3种不同字母组成的4位letter,也就是必须包括ABC。那样是对的。最后结果应该返回dp[n][1]+…+dp[n][26]

嗯是这个意思

可以加你微信嗎?最近刷題,想要請教一些方法

有问题在论坛发帖问好了,不用私信,也不欢迎私信询问。我不是做私人辅导的。