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


0 0 投票数
评分

Zerol 跟我分享了几题面试题,我记录一下,都是直接说答案了,分析过程从简。


有一个数组,每一个元素都是一个整数,现在要你寻找一个 $i$ 和 $j$ 满足,$i < j$ 且 $a_i < a_j$ 并使得 $a_j – a_i$ 最大。

如果 $j$ 固定了,那么就是其实是从它之前的元素中找到一个最小的。

最小值显然容易维护,而且对于所有的 $j$,都只要维护一个最小值就可以了。

维护一个最小值,扫一遍,对于每一个 $j$,都计算它和最小值的差值,如果遇到更小的值则更新最小值。

开胃菜结束。

上题换成并使得 $a_j – a_i$ 最小。

$O(n^2)$ 的显然可以。

方法一:

如果给定一个 $i$,就是从它右边的元素中,找一个大于它的,但是和它最接近的。

如果把 $a_i$ 右边的元素全部排序,那么找到第一个大于 $a_i$ 的元素,将他们最差即可。

假设我已经有了 $a_i$ 右边的所有元素从小到大排列(事实上,重复元素可以舍去,因为只关心差值,那么对于重复的元素是没有必要区分的),那么直接用类似二分的方法就可以找到需要的元素。

对于任意的 $i$,重复上面的过程。

如果每次都是从列表中取出 $a_i$ 右边的元素再排序,太慢了。

注意到如果扫的顺序是固定的,那么一开始显然 Set 为空,随着扫描的进行,对于某一个元素,我可以从 Set 中找到第一个大于它的元素,作差记录,然后把这个元素放入到 Set 中,对于下一个元素,继续从 Set 中(此时 Set 中元素的个数可能多了一个,也可能由于去重以后不变)找到第一个大于它的元素,作差记录、比较、留最小的差,然后把这个元素放入到 Set 中……

C++ 可以用 upper_bound() 或者 lower_bound(),取决于从哪里扫,都是一样的。

Java 中可以用 TreeSet,肯定是一棵类似红黑树的结构,而由于 TreeSet 没法用 Collection.binarySearch(),但是幸运的是(其实我也是今天才知道)可以用 ts.higher()、ts.ceiling()、ts.lower()、ts.floor(),至于 heigher 和 ceiling 有什么区别、lower 和 floor 有什么区别,看为文档,至于为什么叫 higher 不叫 upper,我不知道。

方法二:

分治。

用归并排序,做逆序对的思想。

分治以后,数组就是有序的。

同时我记录下是来自于左边一半还是右边一半。

然后扫一遍,如果当前元素来自于左边,就始终更新成最后出现的那个左边元素的值,如果来自于右边,就与维护的那个最后的左边相减。

方法三:

排序,从小到大,但是保留原来的下标。

只需要考虑新数组中相邻两数的差即可。

遍历数组,如果相邻两数的原下标满足 $i < j$,那么作差。


有一个全部是 0 或者 1 组成的序列,你可以任选一段区间进行变换操作,变换指的是把所有的 0 变成 1 同时把所有的 1 变成 0。

例如,0 0 1 1 0 1,可以选择变更 1 1 0 1 为 0 0 1 0,也可以选择变更 1 1 为 0 0,这两种做法都是会使得 0 的个数最大。

输入任意一个区间的起始和结束,使得对该区间变换后,0 个数最大。

我的第一思路是,遇到 0 就加 1,遇到 1 就减 1。

例如对于上面的样例:

0   0   1   1   0   1   0   1   1
-1  -2  -1  0   -1  0   -1  0   1

然后注意到

0   0   1   1   0   1   0   1   1
-1  -2  -1  0   -1  0   -1  0   1
        1   2   1   2   1   2   3

所以可以找到区间。

然而要证明,我不会。

但是当我写下上面 2 行的时候,zerol 突然意识到——哦,我知道为什么让我证明正确性的时候那么复杂了,其实只要把 0 看成 1,把 1 看成 -1,然后计算前缀和,维护一次差分,就变成了刚才那个问题,就是找到一个 $a_i$ 和 $a_j$ 使得差值最大,就是令区间中 1 的个数和 0 的个数的差值最大,是一样的。

好的,那就完成证明了。


最大子段和。


0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论