在职一年Bloomberge电面

一个int array,一个数字m
对于所有subarray满足”subarr

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

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

之后和同学研究出了其他O(n)解法

two passes:
1) map odd number to 1 in new array, otherwise 0. calculate presum array
2) use counter to track presums, and accumulate the total number of subarray along the way

应该是比较简单的，猜有原题

subarray是连续的还是可以间断的？

justin 发表于 2017-8-24 03:43
subarray是连续的还是可以间断的？

连续的。所以我准备keep一个start和end的index来解，就是双指针移动window。但目前感觉不是很行得通。

现在发现的更正确的方法是先找出所有odd number的index，然后每m个一组形成subarray，之后因为你直到这个subarray前后下一个odd number的index，所以你也就知道这个subarray前后有几个even number。比如前面有3个后面有4个，那一共有（3+1）*（4+1）+1 = 21个subarray来自目前的m个odd number

竟然把bloomberg打成bloomberge了，黑暗之魂3玩多了(flamberge焰形大剑）

ywang170 发表于 2017-8-24 03:53
连续的。所以我准备keep一个start和end的index来解，就是双指针移动window。但目前感觉不是很行得通。

...

楼主为什么双指针维护一个window行不通啊？

大懒懒一休哥 发表于 2017-8-24 11:15
楼主为什么双指针维护一个window行不通啊？

我一开始也觉得肯定能解出来，但真做的时候发现会遗漏一些case，具体的忘了，但是具体就是当在某个位置的时候，不管移动start，还是移动end，都会略过一些case（你自己做的时候可以尝试一下这个例子2,4,1,6,8，寻找odd数量为1的subarray，问题可能就会浮现出来，因为241,41,16,168,416,4168....等等都是成立的，但是你移动start或者end都会顾此失彼，失去一些组合）
当然后来也没有再继续做了，可能还是有解法的吧

👍 谢谢分享

感觉可以用双指针，i 从第一个元素开始，j 向后遍历，找到包含m个奇数的最大区间，同时记录其中遇到的第一个奇数的位置 a 和最后一个奇数的位置 b。用 i ，j ，a， b 可以算出i， j 之间满足条件区间的个数。然后i 移动到 j 的下一位， j 继续向后遍历。