GOOGLE ONSITE一道最近高频DP

伤的彻底 发表于 2017-2-27 02:12
用sliding window写了一下，大家看看对不对
public static void testReward() {
                String str = "LLLAooo ...

你贴出来的code，用你自己的输入，算出来是0

jedihy 发表于 2017-2-27 08:38
你贴出来的code，用你自己的输入，算出来是0

不是应该是0么？因为3次late了不行

伤的彻底 发表于 2017-2-27 11:50
不是应该是0么？因为3次late了不行

不好意思，我以为你是做follow up。
第一问很简单，扫一边计一下数就可以了。

您好！
本帖隐藏的内容需要积分高于 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

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

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

2nd question..

n = 2

LL
LO
LA
OL
OA
OO
AL
AO

8 is result?

or you mean given

LLLAO....

and n

return number of substring of length n such that you get reward?

伤的彻底 发表于 2017-2-27 13:40
我是做的follow up啊。。。
String str = "LLLAoooooo";
                int n = 10;

follow up的输入只有n的。

ryuichist 发表于 2017-2-14 09:10
感觉就是个sliding window题目，非要用DP的话我估计要三维DP

我第一反应也是sliding window.

其实可以把当前情况分成6种
1. 当前字符包含A，最后两位都不是L
2. 当前字符包含A，最后一位是L
3. 当前字符包含A，最后两位都是L
4.当前字符不包含A，最后两位不是L
5.当前字符不包含A，最后一位是L
6.当前字符不包含A，最后两位都是L
针对以上6种当前情况，分别加 O，A，L，来求出下一个状态的6种情况

我的简单思路，欢迎讨论。