google onsite

xiana406 发表于 2019/12/25 16:53:45
请假下楼主，第二题的follow up是一个一个endWord的bfs，最后确定YES or NO吗？另外第三轮的第二个...

第二题follow up用并查集做 第三题follow up 1确实是dp

帅帅的哭豆包儿 发表于 2019/12/27 14:08:56
请问楼主可以详细说说第三轮的follow up2的解法吗？我想不出来。

这个只是聊了解法没有coding 大概意思就是dp加一维表示得分

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

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

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

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

PillowTalk 发表于 2019-12-24 01:36
用dp 类似于paint house

lz能不能写一下状态转移方程 已加米

spirit_room 发表于 2019-12-27 07:05
请问第三题的话，如果abccc应该是2分吧？

转移方程：

同意，应该在这个基础上再判断一下元音和非原音就好了。

楼主现在备胎转正了吗

请问楼主面的哪个level?

第三题应该可以优化空间
第一问：

1. # isVowel: 最后一个不是元音的个数
   
2. # notVowel: 最后一个是元音的个数
   
3. 
   
4. isVowel, notVowel = 21, 5
   
5. for i in range(1, length):
   
6.     isVowel, notVowel = (isVowel + notVowel) * 21, isVowel * 5 + notVowel * 4
   
7. # answer: isVowel + notVowel

复制代码

第二问：

1. # isVowel: 最后一个不是元音的个数
   
2. # notVowel: 最后一个是元音的个数
   
3. # numOfLenWithLastScore[length]: 上一轮得分中不同length的个数
   
4. 
   
5. numOfLenWithLastScore = [0] * length
   
6. for i in range(k + 1):
   
7.     isVowel, notVowel = 21, 5
   
8.     for j in range(1, length):
   
9.         if i == 0:
   
10.             isVowel, notVowel = (isVowel + notVowel) * 21, isVowel * 5 + notVowel * 4
    
11.         else:
    
12.             isVowel, notVowel = (isVowel + notVowel) * 21, isVowel * 5 + notVowel * 4 + numOfLenWithLastScore[j - 1]
    
13.         numOfLenWithLastScore[j] = isVowel + notVowel
    
14. 
    
15. # answer: numOfLenWithLastScore[-1]

复制代码

楼主能解释下第二题follow up怎么用并查集做吗？多谢啦