leetcode 第192算法比赛

零、背景

上周的比赛没有参加，这周继续。

这周的题都是基础题，第二道 n log(n)竟然超时，最后一题在加一减一上翻车了。

不过还好，四道题都做出来了，下面来看看这四道题吧。

一、重新排列数组

题意：给一个长度为 2n 的数组，将数组前后看成长度为 n 的数组，前后交叉返回新的数组。

例如：输入是 [x1,x2,...,xn,y1,y2,...,yn]。
输出是 [x1,y1,x2,y2,...,xn,yn]。

思路：一层循环搞定。

二、数组中的 k 个最强值

题意：给一个数组，找到中位数，然后找到与中位数差值最大的前 K 个数字。
如果存在差值相等的，优先值较大的那个数字。

思路：一看数据范围，之后 10^5，我直接使用暴力方法来做了。

第一步：排序，计算出中位数。
第二步：计算出所有的差值，使用vector<pair<差值，值>> 来储存。
第三步：排序，取 TOP K的答案。

总复杂度O(n log(n))，结果超时了，不敢想象。
当然，现在想想，应该是内存上申请释放超时了，应该提前resize 或者 reserve 一下应该就不会超时了。
PS：赛后验证了下，确实reserve之后就过了。

那我们能不能不另外开辟一个vector<pair<差值，值>>呢？
也可以。

由于数组已经排序了，分析一下数组，就会发现，答案是从左右向中位数靠拢的。

所以，第二个思路就是双指针的方法。

使用两个游标指向两个边界，比较大小，谁是答案了，谁就向中间靠拢即可。

三、设计浏览器历史记录

题意：实现浏览器的历史记录功能。

功能1：初始化页面。
功能2：后退几步
功能3：前进几步
功能4：访问页面，此时假设页面后退过，则后面的 URL 都需要清空。

思路：很简单的题目，关键在于理解功能4的含义是什么。

leetcode 的原题是先介绍功能4，再介绍前进和后退，这就导致理解错题意了。
不过大家都用过浏览器的前进后退，所以还是可以猜到功能4 的真实含义。

所以，维护一个游标，按照四个功能来模拟即可。

四、给房子涂色 III

题意：给 n 个房子，有些房子已经涂色了。现在需要给没涂色的房子都涂上色。
假设都涂色之后，如果相邻的房子是相同颜色，则算一个区域，问能否使房子恰好是 target 个区域。
如果可以，求最小代价。

思路：最基本的动态规划题。

定义状态f(n,m,t) 为前n个房子，最后一个房子涂为m颜色，恰好形成t的区域的最小代价。
那么输出的答案 就是枚举f(n, 1~m, t)，找到最小值。

那怎么计算出当前状态呢？
可以看到，当前最后一个位置的颜色固定的，我们只需要枚举倒数第二个位置的颜色即可。
颜色相同，区域不变，颜色不同，区域减少一个，最终去最小值。

注意事项：对于有些房子已经涂色，编号是从 1 开始的，注意减一转换。

五、最后

这次比赛依旧是基础题，拼手速和拼细节的时候到了。

对于动态规划，我习惯使用递归实现，这样就会有一堆边界与出口要判断。
以后我会尝试使用递推实现，这样就不会存在各种边界问题了。

思考题：你这次比赛做出了几道题呢?

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code