谷狗新鲜VO

第一题楼主用的是dp吗，还是greedy，面试官怎么说呢？

匿名者 发表于 2021-4-23 23:44
你是有五年以上经验吗

我是ng其实。。

xiana406 发表于 2021-04-24 10:19:16
我是ng其实。。

那真的运气不太好😂

匿名者 发表于 2021-4-25 02:37
那真的运气不太好😂

不止是不好，我听面经都说不面，学长也告诉我不面。然后我被面了哎。

xiana406 发表于 2021-04-25 00:28:24
不止是不好，我听面经都说不面，学长也告诉我不面。然后我被面了哎。

可以试试找recruiter argue一下 说不定可以忽略这一轮的feedback

感谢分享，3-4想了好久 感觉可以用segment tree，每个节点存当前range在摩尔投票后剩下的元素和数量。比如当前的range元素是1,2,1,1,2 根据摩尔投票每次取不一样的元素，那么剩下的元素是1 数量也是1。再比如 1，1，1，1，2，那么就存(1, 3)。那么预处理是NlogN 每次query是logN的复杂度

尝试写了一下
https://leetcode.com/playground/YgEanUmy

cbmbbz 发表于 2021-4-24 14:26
第一题楼主用的是dp吗，还是greedy，面试官怎么说呢？

第一题（义务吴伞），应该用dp吧。Greedy只是一种特殊的dp。Greedy每一步的最优解一定包含上一步的最优解，但是本题不行。

比如10
Greedy：10 -> 5 -> 4 -> 2 -> 1
dp：10 -> 9 -> 3 -> 1

2Hurric 发表于 2021-4-27 00:02
感谢分享，3-4想了好久 感觉可以用segment tree，每个节点存当前range在摩尔投票后剩下的元素和数量。比如 ...

感谢分享，但是我觉得你update 每个tree的方法是错的，比如这个test case： nums = [1,2,1,3]
st = SegmentTree(nums)
print(st.queryRange(0, 3))
你的output 是 3.
因为的segment tree 在处理[1,2]的时候，element = 2, count = 0,  处理[1,3]的时候， element = 3， count = 0，然后合在一起处理[1,2,1,3]的时候， element = 3， count = 0

qianh1225 发表于 2021-4-28 08:21
感谢分享，但是我觉得你update 每个tree的方法是错的，比如这个test case： nums = [1,2,1,3]
st = Segm ...

感谢指出来😂  我好像漏了没有majority element的case，[1,2,1,3]的例子理论上应该是没有返回值。我改了一下最后return的返回条件，感觉现在应该没啥问题了

2Hurric 发表于 2021-4-28 09:14
感谢指出来😂  我好像漏了没有majority element的case，[1,2,1,3]的例子理论上应该是没有返回值。 ...

你的程序还是不对， 试试， [1,2,3]。你得增加一步验证得出来的值是确定是majority number。