G家 店面

刚刚结束的G家电面，分享个面经，求昂赛

第一题
给一个只含有0和

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

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

过蛮简单的，面试官循循善诱，比较nice。

luka77 发表于 2017-10-26 09:52
是的， k + 1个counter就可以了。用数组就可以了。利口上有讲解，搜索 O(n) time and O(k) space Very Ea ...

找题目 Max Consecutive Ones II 的解答，里面有我说的这个讲解

原题好吗。。。还加的tag
思把屋 思把起

k + 1 个 counter.  counter[i] 表示翻转 i 个0得到的最大长度。 每一次遇到 1 就所有的 counter 加 1. 遇到 0 的话， counter[k] 已经不能再翻转了，更新一下最大结果.  counter[k-1] 还可以翻转一次，所以有  counter[k] =  counter[k-1] + 1,  同理。

详细的可以看这个答案。
https://discuss.leetcode.com/topic/108398/o-n-time-and-o-k-space-very-easy-solution-for-any-k-flips-and-stream-input

能分享下变种3大概是什么思路吗 觉得是dp但是没有推出来。。

jiongjiongyoush 发表于 2017-10-25 08:57
原题好吗。。。还加的tag
思把屋 思把起

刷题刷的少，刚才去lc跑了一下，发现有个小bug。。。可是面试官说look good
不知道会不会挂= =

梨花花111 发表于 2017-10-25 08:32
能分享下变种3大概是什么思路吗 觉得是dp但是没有推出来。。

没那么复杂，就用个数组记录每个0前面的长度就行了

lidongze91 发表于 2017-10-25 09:37
刷题刷的少，刚才去lc跑了一下，发现有个小bug。。。可是面试官说look good
不知道会不会挂= =

Bless!
很多觉得标tag的题都没见过，我也是第一次看到这道题被考

lidongze91 发表于 2017-10-25 09:37
没那么复杂，就用个数组记录每个0前面的长度就行了

用queue好一点吧，每次就offer一个poll一个就行了

hzyfree 发表于 2017-10-25 12:48
用queue好一点吧，每次就offer一个poll一个就行了

能具体讲讲思路吗？

bless 楼主 ， 第三题 用sliding window or queue 记录最近k个zero的vindex，我当场也想不出来

mchzh 发表于 2017-10-25 13:10
能具体讲讲思路吗？

我想的是k+1个counter，每个都记录连续的1的个数,用一个sum记录总长，当queue.size()>k+1的时候poll一个出来，sum减掉poll出来的值。sliding window也可以，用一个counter记录0的的个数，count>k的时候缩window。