Google onsite 01/05

Iterator那道题怎么把原数据插回去?

lcl3356897 发表于 2016-1-21 02:32
嗯。。。我当时也这么说的，但是这个算是个Greedy，没法证明这个的正确性

不过答案不重要，思考过程最 ...

请问这个matchup是什么样的思路？能否展开说说，谢谢

lrn0304 发表于 2016-1-22 00:55
Iterator那道题怎么把原数据插回去?

唔。。。

我的想法是对于每个Iterator，用一个int保存之前next出去了多少个数字，然后找到第一个比当前大的
比如现在结果返回了 1,4,5,2 那么就变成了
i1 3           2个
i2 4           1个
i3 6           1个
所以我们应该对i1调用previous，并且把这个int减去1

arokyzxc 发表于 2016-1-22 01:27
请问这个matchup是什么样的思路？能否展开说说，谢谢

我当时的思路是尽可能匹配到两个人和average的差值的一样的，比如有个人多掏了10刀，另一个人少掏了10刀。这样的话，理想状态下，最后的transaction的次数就是 n / 2， n是多少个掏钱不是avg的人(不管是多掏了还是少掏了)    但是这样没办法保证正确性

lcl3356897 发表于 2016-1-22 05:49
唔。。。

我的想法是对于每个Iterator，用一个int保存之前next出去了多少个数字，然后找到第一个比当 ...

那previous不是zigzag iterator的方法吗, 怎么变成 i1的方法了? 而且就算这个计数器-1了, 已经 next() 出去的数字也回不到 i1里面去了呀? 我想问的就是最后这个, 嗯嗯求讲解谢谢~

lrn0304 发表于 2016-1-22 05:58
那previous不是zigzag iterator的方法吗, 怎么变成 i1的方法了? 而且就算这个计数器-1了, 已经 next() 出 ...

啊，小姐姐说的意思是，每个Iterator都有一个previous()的方法，能把next()出去的数字弄回去

然后让我实现这个Zigzag Iterator的previous()

lcl3356897 发表于 2016-1-21 02:33
谢啦谢啦

我是new grad, 好像都是四轮吧

我的是5轮，不知道为什么。。不开心~~

comicrudy 发表于 2016-1-22 07:52
我的是5轮，不知道为什么。。不开心~~

我是4轮，，所以你是new grad么？

这么大的题量，这么难，能写得完吗，好烧脑啊

comicrudy 发表于 2016-1-22 07:52
我的是5轮，不知道为什么。。不开心~~

唔。。。new grad应该是4轮吧，你可以找HR问问

palpate

补充内容 (2016-1-22 14:21):
我想发的是  patpat...