Snapchat挂经

tiancaihxx 发表于 2016-9-6 23:57
请问第三题圆心是都在一条线（x）上，还是在一个平面上（x，y）？

二维的。。。。。。。。

第一轮是leetcode 321的其中一部分

lzzhang07 发表于 2016-8-23 00:46
楼主这个number removal怎么做到O(length + n)的？我觉得需要每次找min，用heap的话应该是O(length*lg(n)) ...

http://www.geeksforgeeks.org/build-lowest-number-by-removing-n-digits-from-a-given-number/

思路很清晰。

求问第四题的follow up要怎么做

rasperrypie 发表于 2016-8-23 01:17
用贪心，从左往右扫，遇到左边的数比右边小时，remove左边大的数。
e.g.， 57294，删掉3个数
扫到5，这 ...

单从描述我觉得这个解法有问题……应该是从前 n+1个数中取最小，然后在之后的数中递归调用这部分逻辑，当然要注意把n调整

pawprinter 发表于 2016-10-1 11:08
单从描述我觉得这个解法有问题……应该是从前 n+1个数中取最小，然后在之后的数中递归调用这部分逻辑，当 ...

你再想想吧。。。。。。。。这确实是正确的解法。我不太理解你的解法

rasperrypie 发表于 2016-10-1 21:39
你再想想吧。。。。。。。。这确实是正确的解法。我不太理解你的解法

你再想想吧。。要去掉n个digit，那么前面n+1个digit里至少剩下一个。。。那自然是取最小的那个

pawprinter 发表于 2016-10-1 21:57
你再想想吧。。要去掉n个digit，那么前面n+1个digit里至少剩下一个。。。那自然是取最小的那个

你是这个意思吗？如果从341578里remove 3个数，那么341里最小是1，所以取1，345里最小是3，取3，457里最小是4，取24，578里最小是5，取5？

rasperrypie 发表于 2016-10-1 22:13
你是这个意思吗？如果从341578里remove 3个数，那么341里最小是1，所以取1，345里最小是3，取3，457里最 ...

remove 3个数，那么前4个数里面最小的是1，remove了两个 还需要remove 1个，57里面最小的是5，取5，78里面最小的是7，取7，剩下一个8，还需要remove 1个，那就remove掉8，最后答案157，懂了？

pawprinter 发表于 2016-10-2 03:00
remove 3个数，那么前4个数里面最小的是1，remove了两个 还需要remove 1个，57里面最小的是5，取5，78里 ...

嗯嗯，我理解你的意思了，是这个解法？
http://www.geeksforgeeks.org/bui ... rom-a-given-number/

其实这个解法跟我的解法本质上一样。

你的做法：每次找最小的一个数，取最小数，然后递归是只考虑这个最小数后面的数 ＝ 删掉所有这个最小数前面的数。这个做法的复杂度跟怎么找这个最小数有关。最坏的情况是递增序列，12345，每次你都会取第一个数，所以。如果是n个数删m个，用heap是O((n-m)logm) or O(nlogm)。如果是每次扫m个数找最小数，就是O((n-m)*m) or O(n*m)。如果是贪心最坏是O(n)