虚拟机 Propel OA

泡芙小姐的金鱼 发表于 2018-8-18 02:42
请问楼主投的是propel 2018吗， 收到了OA不知道对不对，new grad不应该是2019了吗？

投的应该是Propel2019吧，收到的OA是写着2018的。应该没什么问题的

最后一题我的想法是二维 dp（可以优化到O(k) space）。dp[i][j] 表示以 i 结尾的允许 k 个 odd 的 subarray 数量。dp[i][j] = (A[i] is odd ? dp[i-1][j-1] + 1 : dp[i-1][j] + 1)。结果是把 dp[0...n-1][k] 加起来

coolth 发表于 2018-8-18 09:55
最后一题我的想法是二维 dp（可以优化到O(k) space）。dp[j] 表示以 i 结尾的允许 k 个 odd 的 subarray 数 ...

但是怎么解决distinct的问题呢？

LZ他这个distinct是不是就比如：
[1, 2, 1, 2]    m = 1
这两个[1, 2]就算做一个？
如果是这样的话，感觉是找不到除了搜索以外的办法。
如果不是，就可以O(N)做

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

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

楼主能不能解释下遇到odd右移start是什么操作...怎么保证subarray里的odd数量不超过k呢？谢谢...

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

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

请问楼主最后这题，用例里面是 [4, 6, 3, 5, 8], k = 1, 为什么最后结果里面都没有4啊，是我理解有误了么

KenZhuJMHK 发表于 2018-8-19 22:47
可能漏了几个字。遇到end指向的是个odd且count=k的时候就把start向右移直到移过了一个odd数，count减一个 ...

非常感谢。

KenZhuJMHK 发表于 2018-8-19 19:00
对是这个意思，所以我用了HashSet. 即使没有distinct的要求我也不确定是不是可以O(N),每步去把subarray取 ...

这个题如果没有distinct的话，建一个prefix数组，O(kN)就好了

https://www.geeksforgeeks.org/number-subarrays-m-odd-numbers/