SpaceX
这几天科技圈的最大震撼，是 SpaceX 的第五次试飞，以及首次验证"筷子夹火箭"技术。
这是人类在太空探索技术领域的重要里程碑。
标记着人类对航天领域中的「模块化」以及「火箭复用」技术达到了空前高度。
文字大家可能没有概念，我找来了视频，大家可以一睹为快：
视频
看完视频，可能有不少对航空领域不了解的同学，还是未能 Get 到当中的震撼之处。
我列举一下对比数据，你就明白了。
在 SpaceX 成名前，几乎所有的火箭发射，都是需要专门定制的。
箭体结构、推进系统（发动机、燃料仓）、稳定系统（尾翼、推力矢量控制器）、制导系统&导航系统、分离系统、着陆系统等等。
上述还只是列举了火箭工程里很小很小很小的一部分。
由于大多数东西都是专门定制，因此火箭发射工程都面临周期长，成本高的问题。
更重要的是，大多数材料都没法回收再利用。
更更重要的是，运载量还极其有限，通常只有 10~50 吨。
这两点就导致了常规火箭的单位运力成本极其高昂。
那 SpaceX 这次成功回收的箭体的"星舰"什么水平呢？
完全复用 + 保守估计 200 吨的运载能力。
这和以前航空的那一套相比，已经不能说是"降维打击"，完全就是两个世界。
更离谱的是，SpaceX 这家企业，虽然研究的太空探索技术，但用的是互联网"快速迭代"的那一套，仍然在快速发展。
上一次我们聊到 SpaceX 的火箭试飞，是 2024-03-15，当时是第三次试飞。试飞的主要目的，是验证星舰能否达到环绕速度。当时虽然没有成功回收火箭，但也足以载入史册了。
将其形容为日新月异都过于保守了，很难想象，未来会发展成怎么样。
集体登月，太空移民，或许真不是「有生之年」系列，对此你怎么看？
...
回归主题。
来一道经典算法题。
题目描述
平台：LeetCode
题号：781
森林中，每个兔子都有颜色。
其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。
我们将这些回答放在 answers 数组里。
返回森林中兔子的最少数量。
示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10]
输出: 11
输入: answers = []
输出: 0
说明:
-
answers的长度最大为 -
answers[i]是在 范围内的整数。
基本分析
首先，兔子它不会说谎 (｀・ω・´)，因此我们可以得出以下结论：
-
「同一颜色的兔子回答的数值必然是一样的」 -
「但回答同样数值的，不一定就是同颜色兔子」
举个🌰，假如有 3 只白兔，每只白兔的回答必然都是 2（对应结论 1）；但假如有兔子回答了数值 2，可能只是三只白兔，也可能是三只白兔和三只灰兔同时进行了回答（对应结论 2）。
「答案要我们求最少的兔子数量。」
不妨设有某种颜色的兔子 只，它们回答的答案数值为 ，那么 和 满足什么关系？
显然两者关系为 。
但如果是在 数组里，回答 的数量为 的话呢？这时候我们需要分情况讨论：
-
: 为达到「最少的兔子数量」，我们可以假定这 只兔子为同一颜色，这样能够满足题意，同时不会导致「额外」兔子数量增加（颜色数量最少）。 -
: 我们知道回答 的兔子应该有 只。这时候说明有数量相同的不同颜色的兔子进行了回答。为达到「最少的兔子数量」，我们应当将 分为若干种颜色，并尽可能让某一种颜色的兔子为 只，这样能够满足题意，同时不会导致「额外」兔子数量增加（颜色数量最少）。
「换句话说，我们应该让「同一颜色的兔子数量」尽量多，从而实现「总的兔子数量」最少。」
证明
我们来证明一下，为什么这样的贪心思路是对的：
基于上述分析，我们其实是在处理 数组中每一个 ，使得满足题意的前提下，数值 带来的影响（总的兔子数量，或者说总的颜色数量）最小。
首先 中的每个数都会导致我们总的兔子数量增加，「因此我们应该「让 的数字尽可能变少」，也就是我们需要去抵消掉 中的一些数字。」
对于 中的某个 而言（注意是某个 ，含义为一只兔子的回答），必然代表了有 只兔子，同时也代表了数值 最多在 数组中出现 次（与其颜色相同的兔子都进行了回答）。
这时候我们可以从数组中移走 个数值 （如果有的话）。
「当每次处理 的时候，我们都执行这样的抵消操作。最后得到的 数值数量必然最少（而固定），抵消完成后的 中的每个 对答案的影响也固定（增加 ），从而实现「总的兔子数量」最少。」
「相反，如果不执行这样的操作的话，得到的 数值数量必然会更多，「总的兔子数量」也必然会更多，也必然不会比这样做法更优。」
模拟
按照上述思路，我们可以先对 进行排序，然后根据遍历到某个 时，将其对答案的影响应用到 中（ans += cnt + 1），并将后面的 个 进行忽略。
Java 代码：
class Solution {
public int numRabbits(int[] answers) {
Arrays.sort(answers);
int n = answers.length, ans = 0;
for (int i = 0; i < n; i++) {
int cnt = answers[i];
ans += cnt + 1;
// 跳过「数值 cnt」后面的 cnt 个「数值 cnt」
int k = cnt;
while (k-- > 0 && i + 1 < n && answers[i] == answers[i + 1]) i++;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int numRabbits(vector<int>& answers) {
sort(answers.begin(), answers.end());
int n = answers.size(), ans = 0;
for (int i = 0; i < n; i++) {
int cnt = answers[i];
ans += cnt + 1;
// 跳过「数值 cnt」后面的 cnt 个「数值 cnt」
int k = cnt;
while (k-- > 0 && i + 1 < n && answers[i] == answers[i + 1]) i++;
}
return ans;
}
};
Python 代码：
class Solution:
def numRabbits(self, answers: List[int]) -> int:
answers.sort()
n, ans = len(answers), 0
i = 0
while i < n:
cnt = answers[i]
ans += cnt + 1
# 跳过「数值 cnt」后面的 cnt 个「数值 cnt」
k = cnt
while k > 0 and i + 1 < n and answers[i] == answers[i + 1]:
k -= 1
i += 1
i += 1
return ans
TypeScript 代码：
function numRabbits(answers: number[]): number {
answers.sort((a, b) => a - b);
let n = answers.length, ans = 0;
for (let i = 0; i < n; i++) {
const cnt = answers[i];
ans += cnt + 1;
// 跳过「数值 cnt」后面的 cnt 个「数值 cnt」
let k = cnt;
while (k-- > 0 && i + 1 < n && answers[i] === answers[i + 1]) i++;
}
return ans;
};
-
时间复杂度： -
空间复杂度：
统计分配
我们也可以先对所有出现过的数字进行统计，然后再对数值进行（颜色）分配。
Java 代码：
class Solution {
int N = 1009;
int[] counts = new int[N];
public int numRabbits(int[] answers) {
// counts[x] = cnt 代表在 answers 中数值 x 的数量为 cnt
for (int i : answers) counts[i]++;
int ans = counts[0];
for (int i = 1; i < N; i++) {
int per = i + 1, cnt = counts[i], k = cnt / per;
if (k * per < cnt) k++;
ans += k * per;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int numRabbits(vector<int>& answers) {
int N = 1009;
vector<int> counts(N, 0);
for (int i : answers) counts[i]++;
int ans = counts[0];
for (int i = 1; i < N; i++) {
int per = i + 1, cnt = counts[i], k = cnt / per;
if (k * per < cnt) k++;
ans += k * per;
}
return ans;
}
};
Python 代码：
class Solution:
def numRabbits(self, answers: List[int]) -> int:
N = 1009
counts = [0] * N
for i in answers:
counts[i] += 1
ans = counts[0]
for i in range(1, N):
per, cnt = i + 1, counts[i]
k = cnt // per
if k * per < cnt:
k += 1
ans += k * per
return ans
TypeScript 代码：
function numRabbits(answers: number[]): number {
const N = 1009;
const counts = new Array(N).fill(0);
for (const i of answers) counts[i]++;
let ans: number = counts[0];
for (let i: number = 1; i < N; i++) {
let per = i + 1, cnt = counts[i], k = Math.floor(cnt / per);
if (k * per < cnt) k++;
ans += k * per;
}
return ans;
};
-
时间复杂度： -
空间复杂度：
拓展
保持题目现有的条件不变，假定颜色相同的兔子至少有一只发声，问题改为「问兔子颜色数量可能有多少种」，又该如何求解呢？
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
