leetcode 第 283 场算法比赛

零、背景

本来我有机会进去前 50 名的，结果因为我脑子短路，看错时间了。

10:30 的时候，我还在楼下买早餐。
10:35 的时候，我还在群里聊深圳的疫情地图问题。
10:40 的时候，我还在锻炼身体。

最后意识到比赛开始的时候，已经 10:45 了。

面对这次的问题，我要反思，当然原因与比赛无关，我就不公开说明了吧。

一、Excel 表中某个范围内的单元格

题意：给一个 execl 表格的两个坐标，求坐标形成矩阵里面的所有坐标，从小到大输出。

思路：按照题意，遍历矩阵得到所有满足要求的坐标即可。

小技巧：先循环字母，再循环数字，得到的顺序就是题意要求的顺序。

二、向数组中追加 K 个整数

题意：给一个数字集合，求 K 个不存在集合里的最小数字，输出他们之和。

数据范围：集合大小为 10^5，集合里的值和 K 为 10^9。

思路：先对集合排序，然后从小到大依次找出与集合没有交集的区间。
累计得到的数字与区间内的数字总个数如果还在 K 之内，则区间内的数字直接求和。
如果加上区间内的数字，个数大于 K 了，那只取前面的若干个，凑够 K 个。

小技巧：区间和是连续数字之和，首尾相加乘以个数除二即可。
小技巧：最开始的区间从1开始，最后一个区间可以理解为无穷大。

三、根据描述创建二叉树

题意：给一个二叉树边的关系，即父节点、子节点、左边还是右边。
求构造出这个二叉树。

思路：通过 map 储存每个节点的内存，并构造出二叉树。
使用另外一个 map 储存每个子节点的父节点。
然后随便找一个节点，循环找到根节点，输出即可。

四、替换数组中的非互质数

题意：给一个数字序列，如果任意相邻两个数字非互质，则合并为最小公倍数。
求不断这样操作，最终无法操作时的序列。

思路：显然可以证明，操作顺序不影响答案。

所以维护一个栈，从前到后不断判断是否可以合并。
如果可以合并，则出栈合并，并循环判断栈中的是否可以继续合并。

复杂度：O(n log(n))

五、最后

这次比赛比较简单，第二题和第四题都可以当做面试题。

对了，这次比赛总的来说，第三题和第一题非常简单，第二题算是最难的，第四题难度适中吧。

加油，算法人。

《完》

-EOF-

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