实习与工作|算法

PayPal实习生笔试

凝神长老 · 4月1日 · 2019年 · · · 788次已读

本文写于 2019年04月01日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


有点难。

简单模拟就好了。

一开始以为是聚类。

后来知道是并查集。

甚至不需要路径压缩等技巧,裸的并查集,直接开长度为 N 的数组,每次要合并的时候遍历,修改需要合并的所有值为 p 的改为 y 就行了。

输出格式感觉是专门为 Python 定制的啊,很鄙视。

输入:

并查集:

Point 是一个类。

输出:

这道题我觉得有点难。

一开始以为是贪心或者什么,后来想想是不是线段树,但是显然线段树求区间最值、区间和,没法维护每一段的状态。

考试结束以后问 zerol,他说不可能是线段树这么难的,肯定是简单算法。

一开始他给出的是差分维护,就是遇到左端点 +1,遇到右端点 -1,找最大区间。

后来看到样例 2,就感叹我抽题的运气不好。

第 2 个样例的输出是

 1 2
 2 3
 3 4
 4 5

也就是弹幕最多的时间是 4 段,每段都是 1,不能合并的。

而且题目是开区间,很诡异。

林的建议是,加一个 .5 区间,搞成左开右闭或者左闭右开,这样就把开区间的问题解决了,可以差分了。

但是第 2 个样例输出 1 5 还是分 4 段,还需要考虑。

最后一题是 DP。

大概的提示和扔鸡蛋测试最高每个鸡蛋能扔多高是一样的。

题目是说给你 K 架飞机,测试最大拉伸高度。

样例 1 是 1 架飞机,1000 米,那就必须测试 1000 次了,因为飞机损坏了就没有了。

样例 2 是 15 架飞机,1000 米,由于飞机足够,用二分。

其实这两个特殊状态出去已经有一些部分分了。

关键的部分是 DP。

就是 ​$f(h, k) = min_{0 < i \leqslant h } { max{f(i,k-1), f(n-i-1,k)}} + 1​$

0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论