谷歌 newgrad 电面

YellowClothes · 2019-10-11 10:48:52

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

x

一个声音很温暖的国人小哥哥

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

小哥哥很nice，也没有为难我。祝好。

求米(●'◡'●)

vista003 · 2019-10-11 11:54:34

lz第一题我的理解是用两个变量x1, x2一个存so far第一列，一个存so far第二列的最大值，然后状态转移是x1,i = Math.max(x1,i-1 + arr[i], x2,i-1 + arr[i] - cost)，x2,i同理，是这个意思不？
如果理解错了请见谅~

ytx2013 · 2019-10-11 11:40:42

谢谢楼主分享！
第二题是不是问和小于某个值的最长连续子数组？数组都是非负数吗？还是都可以？

安吉拉鸡 · 2019-10-11 13:21:18

楼主第一题可以给个例子吗

jobhunting · 2019-10-11 13:28:21

谢谢分享谢谢分享

jobhunting · 2019-10-11 13:29:06

谢谢分享谢谢分享

dchampion24 · 2019-10-11 23:32:07

感觉第二题是经典的0-1 knapsack，dp可解

YellowClothes · 2019-10-11 23:44:44

ytx2013 发表于 2019-10-10 21:40
谢谢楼主分享！
第二题是不是问和小于某个值的最长连续子数组？数组都是非负数吗？还是都可以？

基本是的，没有负数和0，很友好的那种

YellowClothes · 2019-10-11 23:56:54

vista003 发表于 2019-10-10 21:54
lz第一题我的理解是用两个变量x1, x2一个存so far第一列，一个存so far第二列的最大值，然后状态转移是x1,i ...

Exactly (●'◡'●)

YellowClothes · 2019-10-12 00:04:14

dchampion24 发表于 2019-10-11 09:32
感觉第二题是经典的0-1 knapsack，dp可解

连续取，two pointer更快乐