狗家新鲜五轮昂塞

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

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

第二轮，考虑flip 0的收益是1，flip 1的收益是-1，问题转化为【求一个element是1或者-1的array的max subarray sum】，直接slide window就可以了。等价于leetcode 53。（一个小区别是这里可以选择empty subarray）

我觉得第二题可以当成 刷题网的雾散来做
遍历数组， 遇见0， sum就+1， 遇见1 sum就减1， 有个数max时刻track sum的最大值。 如果sum<0, then set sum = 0.

ee19920302 发表于 2020-11-24 05:06
我觉得第二题可以当成 刷题网的雾散来做
遍历数组， 遇见0， sum就+1， 遇见1 sum就减1， 有个数max时刻t ...

同意。+1

ee19920302 发表于 2020-11-24 05:06
我觉得第二题可以当成 刷题网的雾散来做
遍历数组， 遇见0， sum就+1， 遇见1 sum就减1， 有个数max时刻t ...

您好楼主，请问“有个数max时刻track sum的最大值” 是指？ 谢谢~

xs1738 发表于 2020-12-5 04:09
您好楼主，请问“有个数max时刻track sum的最大值” 是指？ 谢谢~

懂了, 需要三个变量，start, end, sum

input: 1,  1, 0, 0, 1, 0, 0, 1
sum: -1, -1, 1, 2, 1, 2, 3, 2

ee19920302 发表于 2020-11-24 05:06
我觉得第二题可以当成 刷题网的雾散来做
遍历数组， 遇见0， sum就+1， 遇见1 sum就减1， 有个数max时刻t ...

请问Follow Up 2D Array如何解？谢谢~

AlbertZhong 发表于 2020-11-19 17:06
第三题应该是LC 318。。。确实必须要有O(n^2)，唯一的优化可能就是用bit mask来辅助

但给出的solution时间复杂度为O(N^2 + L), L为所有words的总长度。我不确定，是否满足需求

dylen 发表于 2020-11-20 03:10
第一题lz水平有限，还是理解不到位，举的例子有错，重新写一下。
[1, ‘abc’], [2, ‘54321’],[1, ‘abc ...

感谢楼主的分享，请问这里的goal是什么？求出最大可行的max_size_per_source， 然后至少每个source有保留一份内容？谢谢~

dylen 发表于 2020-11-20 03:10
第一题lz水平有限，还是理解不到位，举的例子有错，重新写一下。
[1, ‘abc’], [2, ‘54321’],[1, ‘abc ...

还是没理解第一题什么意思。如果给定
[1‘abc’][2‘54321’][1‘abcdef’][1‘re’]
max_size_over_aall = 10

最后不应该是
1: abc, abcdef(discard), re  -> max_size = 5
2: 54321 -> max_size = 5

max_size_per_source = max(5, 5) = 5

这么理解有错误么？为什么需要prefixsum？