Wepay OA面经及讨论

无量塔 发表于 2017-9-3 07:46
可以根据给出来的index找一个最小的上界，最终答案只会小于等于这个上界。跑循环的时候，计算出来的power ...

明白了，多谢。。。字数字数

jy02535954 发表于 2017-9-3 07:24
思路就是super ugly number 那题优化
一个PQ, 建一个数据结构  O(1)空间 O(nlogn).  具体代码我拿到电面 ...

谢谢！持续关注！

llzy1178 发表于 2017-9-3 08:31
明白了，多谢。。。字数字数

求解释下这个上界具体是什么？多谢！

无量塔 发表于 2017-9-3 07:46
可以根据给出来的index找一个最小的上界，最终答案只会小于等于这个上界。跑循环的时候，计算出来的power ...

求解释下这个上界具体是什么？多谢！

cassie_huang 发表于 2017-9-3 07:55
我还在想是不是可以利用某种数学性质类似用binary search 的方法搜第k个，就是不用从1开始一个个搜到k，结 ...

可以请教下 往PQ里添加数的时候是怎么添加的吗？
是用两层循环，自己确定一个最大root和最大指数的范围吗？如果是的话是怎么确定的呢？
看到帖子里讨论的AC方案好像都是O(nlogn)，如果要这个时间复杂度是不是说明往PQ里就只添加了n个数呢，那么怎么确定这n个数呢？我们知道小root的高次幂和大root的低次幂之间的大小关系并不能确定啊，怎么能在添加的时候保证加进去的就是最小的n个数之中的数呢？

Trie 发表于 2017-9-4 09:27
可以请教下 往PQ里添加数的时候是怎么添加的吗？
是用两层循环，自己确定一个最大root和最大指数的范围 ...

首先我的priorityqueue里存的是int[2]，表示一个(root, power)，初始时里边只有一个(2,2), 然后循环外围护一个upperbound,初始值是2.每次迭代拿到队首cur = (root0, power0), 同时增加(root0, power0+1)，如果root0 == max的时候，还要往priorityqueue新增一个(root0 + 1, 2), 同时max++.

总之max的作用相当于你们找upperbound，但是这个值是动态变化的，好处是不用定义fixed的capacity.

changming927 发表于 2017-9-3 13:00
求解释下这个上界具体是什么？多谢！

好像是 (index+2)^2，不知为何

刚刚做过了，感谢各位的提醒

刚收到还没做，楼主方便给题目的具体描述吗？

无量塔 发表于 2017-9-3 07:46
可以根据给出来的index找一个最小的上界，最终答案只会小于等于这个上界。跑循环的时候，计算出来的power ...

请问你是最后两个case跑过了吗