大家好，我是苍何。
在 2024 年的今天，但凡是个编程相关的面试，就得先手撕个算法题，很多人直接拿着题目给 GPT，妙出答案。
一顿复制黏贴，再悄咪咪的手打一些有用没用的代码，以为可以糊弄住面试官，但实际情况是面试官一切都看在眼里。
然后笑而不语的直接给挂掉。
于是有人就在牛客上开始了爹味嘲讽。
有小伙伴说，面试手撕本来就是脑子有什么大病的体现工作中写代码是闭卷吗？
有人说，手撕算法根本没意义，工作大部分都在 CRUD 扭螺丝，用到算法的机会不多，现在有了 AI，实现起来更是分分钟的事。
当然也有人说：工作中我也没见到过高考的解析几何啊。
等于说，解析几何是数学的基础，算法是编程的基础。
看到有个有意思的评论：pdd 那个逆天系统，面试官脸在右边，题目出在左边，面试官出完题之后我去看题，面试官问我是不是双屏😅
哈哈哈哈。
这事吧，在没有很好的筛选标准之前，手撕算法，都是绕不过去的大山，大家还是平时多刷一些题。
面试的时候尽量不要作弊，写代码的时候一边写，一边给面试官说思路，即使最后没写出来，但解题的过程是在的，面试官也能理解。
现在面试软件什么腾讯会议啊，什么飞书啊，那都是做好了各种防作弊功能，面试官看的一清二楚。
相对而言，真诚最重要。
好啦，你怎么看待算法作弊这事？欢迎评论区讨论。
...
回归主题。
今天来一道简单的面试算法题，给枯燥的牛马生活加加油😂。
题目描述
平台：LeetCode
题号：502
题目名称：IPO
假设力扣（LeetCode）即将开始 IPO。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后能得到最大总资本的方式。
给你 n 个项目。对于每个项目 i，它都有一个纯利润 profits[i]，和启动项目需要的最小资本 capital[i]。
最初，你的资本为 w。当你完成一个项目时，你将获得纯利润，并将纯利润添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以 最大化最终资本，并输出最多可获得的最大资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
你的初始资本为 0，你可以从 0 号项目开始。
完成后，你的总资本变为 1。
此时你可以选择完成 1 号或 2 号项目。
由于完成项目 2 能够获得最大的资本，因此选择项目 2。
最终资本：
0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
提示：
1 <= k <= 10^50 <= w <= 10^9n == profits.lengthn == capital.length1 <= n <= 10^50 <= profits[i] <= 10^40 <= capital[i] <= 10^9
解题思路
本题的核心在于：
如何选择满足当前资本限制的项目。
在满足限制的项目中优先选择收益最大的项目。
步骤如下：
预处理：
将所有项目按启动所需的资本capital[i]升序排序。优先队列（最大堆）：
使用最大堆来动态选择当前可完成的项目中收益最大的项目。模拟选择：
遍历项目列表，将当前资本
w能够完成的项目加入最大堆。从堆中取出收益最大的项目并更新资本。
重复上述过程最多 k 次或直到没有可选择的项目为止。
时间复杂度：
项目排序的复杂度为 (O (n \log n))。
堆操作的复杂度为 (O (k \log n))。
整体时间复杂度为 (O (n \log n + k \log n))，可以应对题目要求的大规模输入。
代码实现
以下是 Java、C++ 和 Python 的实现，均包含详细注释：
Java 代码：
import java.util.PriorityQueue;
import java.util.Arrays;
public class IPO {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
// 将项目按资本需求从小到大排序
int n = profits.length;
int[][] projects = new int[n][2];
for (int i = 0; i < n; i++) {
projects[i][0] = capital[i];
projects[i][1] = profits[i];
}
Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));
// 最大堆：存储当前可完成项目的利润
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
int index = 0;
for (int i = 0; i < k; i++) {
// 将当前资本能启动的所有项目加入堆
while (index < n && projects[index][0] <= w) {
maxHeap.offer(projects[index][1]);
index++;
}
// 如果没有可选项目，直接退出
if (maxHeap.isEmpty()) {
break;
}
// 选择利润最大的项目
w += maxHeap.poll();
}
return w;
}
}
C++代码：
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class IPO {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n = profits.size();
vector<pair<int, int>> projects(n);
// 将项目按资本需求从小到大排序
for (int i = 0; i < n; i++) {
projects[i] = {capital[i], profits[i]};
}
sort(projects.begin(), projects.end());
// 最大堆：存储当前可完成项目的利润
priority_queue<int> maxHeap;
int index = 0;
for (int i = 0; i < k; i++) {
// 将当前资本能启动的所有项目加入堆
while (index < n && projects[index].first <= w) {
maxHeap.push(projects[index].second);
index++;
}
// 如果没有可选项目，直接退出
if (maxHeap.empty()) {
break;
}
// 选择利润最大的项目
w += maxHeap.top();
maxHeap.pop();
}
return w;
}
};
Python 代码：
import heapq
class IPO:
def findMaximizedCapital(self, k, w, profits, capital):
# 将项目按资本需求从小到大排序
projects = sorted(zip(capital, profits), key=lambda x: x[0])
# 最大堆：存储当前可完成项目的利润（Python默认最小堆，用负值模拟最大堆）
max_heap = []
index = 0
n = len(profits)
for _ in range(k):
# 将当前资本能启动的所有项目加入堆
while index < n and projects[index][0] <= w:
heapq.heappush(max_heap, -projects[index][1])
index += 1
# 如果没有可选项目，直接退出
if not max_heap:
break
# 选择利润最大的项目
w += -heapq.heappop(max_heap)
return w
复杂度分析
时间复杂度：
排序：(O (n \log n))
堆操作：最多 (O (k \log n))
总复杂度为 (O (n \log n + k \log n))。空间复杂度：
主要为堆的存储，复杂度为 (O (n))。
ending
你好呀，我是苍何。是一个每天都在给自家仙人掌讲哲学的执着青年，我活在世上，无非想要明白些道理，遇见些有趣的事。倘能如我所愿，我的一生就算成功。共勉 💪
点击关注下方账号，你将感受到一个朋克的灵魂，且每篇文章都有惊喜。
感谢大家一直以来的阅读、在看和转发，我会把流量主收益都用来发红包，大家可在公众号页面发送相关暗号关键词获取抽奖，每一篇文章会给到一个不同的暗号，对应的抽奖都是独立的，此篇暗号为【面试官】，在后台回复【面试官】，即可点击进去参与抽奖！抽奖内容、金额、个数等都无变化，在开奖前参与抽奖，操作均有效。
注意，后台（不是评论区，是后台）回复【面试官】即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。
就像大家之前回复【八股】一样。
