FB 電面

刷题网 流凌五 大概做法是count两个1中间有多少个0，写起来挺简单，但是思路还有有那么一点难想道

Madmax 发表于 2021-5-13 14:56
刷题网 流凌五 大概做法是count两个1中间有多少个0，写起来挺简单，但是思路还有有那么一点难想道

哇。。。竟然是個easy, 感謝指出題號

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

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

iterate array and greedily flip 0 to 1 at index i whenever you have arr[i-1]==0 and arr[i+1]==0 (corner cases: i==0, i==arr.length-1), return how many times you have flipped.

O(n) time O(1) space

我记得FB应该是不会考DP的

Madmax 发表于 2021-5-13 14:56
刷题网 流凌五 大概做法是count两个1中间有多少个0，写起来挺简单，但是思路还有有那么一点难想道

谢谢指教，学习了！

有点模糊啊，是不是要问面试官，如果0变成1了，那那个改变后的也算在adjacent的1里么。
比如1000001 => 1010101 这样就是2
还是说1000001 => 1011101 也是可以啊

houqingniao 发表于 2021-5-12 18:34
感觉greedy来解 更make sense

我也觉得直接GREEDY可解啊，卡在array两边的0你替他多添个0就直接用通式了

匿名者 发表于 2021-5-13 13:05
就這一題。。。當下想不出什麼好解法，只好試著暴力解，但滿醜的。但最後還是有點bug，應該是跪了
事後 ...

就一题的话以FB的尿性一般会要求最优解，双指针扫一遍数组...

hgon23 发表于 2021-5-14 12:02
就一题的话以FB的尿性一般会要求最优解，双指针扫一遍数组...

请问为什么还要双指针？直接greedy不行吗？O(N)