leetcode 周赛 486 - 二进制第K大

零、背景

这次比赛整体难度不大，不过不知道为什么我的 LCA 模板一直调不通过，浪费了不少时间。

A 题：递增判断
B 题：循环左移
C 题：LCA
D 题：贪心构造

最终排名：163 名
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions

一、Q1. 移除前缀使数组严格递增

题意：给一个数组，求一个最长的后缀数组，使得该数组是严格递增的。

思路：从后往前遍历，找到第一个不满足严格递增的位置，从该位置开始往前的元素都是需要删除的，后面的都已经满足严格递增。

二、Q2. 非负元素轮替

题意：给一个数组，要求对所有非负数循环左移 k 个位置。

思路：置换。

看原数组与答案数组，对于一个位置，如果是非负数，则它是从右边第 k 个非负元素移动过来的。

做法上，先提取出所有非负数，得到需要循环左移的临时数组。
对于原数组中第 i 个非负数，它是从右边数第 k 个非负数的位置移动过来，也就是从临时数组右边第 i + k（对长度取模）个位置移动过来。

三、Q3. 树上的勾股距离节点

题意：给一棵无向树，然后给出三个节点，问有多少个节点，使得该节点到这三个给定节点的距离，能够组成一组满足勾股定理关系的三元组。

思路：枚举 + LCA。

假设我们已经可以求任意两个节点之间的距离，那么就可以枚举所有节点，对每个节点分别求出它到这三个给定节点的距离，然后判断这三条距离中，是否存在一组满足勾股定理的组合。

那怎么求任意两个节点之间的距离呢？
可以先用 LCA 找到两个节点的最近公共祖先，然后通过它们各自到 LCA 的深度差之和来计算距离。

LCA 算法之前我在《OI 必学：LCA 倍增算法》里介绍过了，这里就不再重复了。

四、Q4. 二进制中恰好 k 个 1 的第 n 小整数

题意：给一个正整数 n 和 k，求所有二进制中恰好包含 k 个 1 的整数中，第 n 小的那个数。

思路：贪心构造。

这类“第 k 个”（第 k 小 / 第 k 大）的问题，一般都可以从高位到低位进行贪心构造。

从最高位开始，先假设这一位取 0，去统计在这种情况下，低位能组成的合法方案数 count。
如果 count >= n，则说明最高位取 0 就可以在这些方案中找到第 n 个答案。
否则，说明最高位必须取 1，此时需要在低位里去找恰好包含 k - 1 个 1 的第 n - count 小整数。

这里会涉及到“低位恰好包含 k 个 1 的方案数”这一子问题，可以直接使用组合数 C(len, k) 来计算（len 为可用的低位位数）。

注意事项：要小心各种边界条件里的加一减一问题。
小技巧：一开始就把每个变量的含义定义清楚，是 0-base 的还是 1-base 的，这样推导的时候就不容易混淆。

五、最后

这次比赛不难，不过我 LCA 模板出了点问题，最后换了一个模板才通过。

《完》

-EOF-

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