Google VO

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

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

第三题dp怎么做啊？

wuyufei2002 发表于 2021-5-25 05:21
第一题O(N)解：用一个单调增的stack，每来一个数找它在stack里的位置，找到后stack的size就是返回的结果， ...

要是没有treemap库函数，是不是还得自己写一个？那好难啊

第一题可以用Binary Index Tree吧

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

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

第三题 dp
dp[i][j] -> 对前i个字符，使用j个string a，最多能覆盖的char b的数量

dp[i][j] = max(dp[i - 1][j], dp[i - M][j - 1] + (countB[i] - countB[i - M]))
i < M时，dp[i][j] = countB[i]

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

第三题 如果是用纯A的字符串来替代，能不能吧所有B的substring找出来 放在一个heap里 然后就按长度去greedy的盖

SimonLevy 发表于 2021-5-26 12:06
第三题 dp
dp[j] -> 对前i个字符，使用j个string a，最多能覆盖的char b的数量

大大能不能详细写一下这个方法，我按照您的思路写出来结果不是1, max会保留最大的b count数，烦劳大大指点