通知：代码随想录算法训练营 46期今天（9月11日）正式开营，目前可以报名！
上周四（9月5日 ）晚上卡码网举办了三十三期周赛（滴滴23年笔试真题）。
滴滴这次算法题，一个是 贪心+二分，一个是贪心+图论（广搜）。
算法是基础算法，但题目有点难度。
23年各大厂笔试题，大家可以在卡码网（https://kamacoder.com/contest.php）去练习：
题目的评论区有各个语言的版本，也有很多录友分享的解题思路，都很不错。
以下为阿里云23年笔试算法题，解题报告：（其他语言版本，可以看题目链接评论区）
照明灯安装
题目链接：https://kamacoder.com/problempage.php?pid=1244
思路分析
这道题是一个典型的二分题。
我们需要在有限的安装位置上放置k个照明灯，并使得任意两个照明灯之间的最小距离尽可能大。思路如下：
目标：我们需要使得最近的两个照明灯之间的最小距离尽可能大。
显然，如果最小距离越大，照明灯的覆盖效果越好。
问题可以转换为：给定一个最小的距离d，问是否能在这些位置上放置k个照明灯。
二分查找：
我们可以对最小距离d进行二分搜索。
设d的范围是从1到最大可能的距离，即x[n-1] - x[0]，也就是最左和最右两个点之间的距离。
对于每一个可能的d，我们检查是否可以满足“最近的两个灯之间至少相距d”的要求。
如果可以放置k个灯，我们就尝试增大d；如果不能放置k个灯，则需要缩小d。
如何验证某个d是否可行？
从第一个位置开始安装灯，安装下一个灯的位置必须满足距离上次安装灯的位置至少为d。
我们遍历所有可能的位置，尽可能多地安装灯。如果最终安装的灯数量大于等于k，则说明这个d是可行的。
二分终止条件：
当二分的左右边界相遇时，当前的最小距离即为我们求解的答案。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 检查是否能在给定的距离min_dist的情况下放置k个灯
bool canPlaceLamps(const vector<int>& positions, int n, int k, int min_dist) {
int count = 1; // 已经放置的灯的数量，先放置第一个灯
int last_pos = positions[0]; // 上一个放灯的位置
for (int i = 1; i < n; i++) {
if (positions[i] - last_pos >= min_dist) {
count++;
last_pos = positions[i];
}
if (count >= k) {
return true;
}
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> positions(n);
for (int i = 0; i < n; i++) {
cin >> positions[i];
}
// 对安装位置排序
sort(positions.begin(), positions.end());
// 二分查找最小距离
int left = 1; // 最小的可能距离
int right = positions[n - 1] - positions[0]; // 最大的可能距离
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2; // 取中间距离
if (canPlaceLamps(positions, n, k, mid)) {
result = mid; // 如果可以放置，更新结果
left = mid + 1; // 尝试增大距离
} else {
right = mid - 1; // 尝试缩小距离
}
}
cout << result << endl;
return 0;
}
排序的时间复杂度为 O(nlogn) ，二分查找时间复杂度 O(logx[n-1] - x[0])每次检查需要O(n) 的时间。
整体时间复杂度：O(nlogn)
黑白块
题目链接：https://kamacoder.com/problempage.php?pid=1245
思路分析
本题本质是一个带权图的最短路径问题，其中白色网格（0）表示权重为0，黑色网格（1）表示权重为1。目标是从起点 (1,1) 走到终点 (n,m)，经过的黑色网格数最少。
由于这是一个有特殊权重（0和1）的最短路径问题，我们可以使用贪心 + BFS 。
贪心：就是在队列里优先走选白色格子。
BFS 算法：
使用一个双端队列，存储待处理的节点。我们优先处理代价小的路径。 如果走到一个白色格子（0），我们将其放到队列的前端，因为不增加代价。（优先取出来） 如果走到一个黑色格子（1），我们将其放到队列的后端，因为会增加代价。（尽量靠后） 最终到达终点时，输出代价（经过的黑色格子数）。
代码实现
#include <iostream>
#include <vector>
#include <deque>
#include <climits>
using namespace std;
// 四个方向移动
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 最小经过的黑色格子数，初始化为一个很大的值
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
// 使用双端队列
deque<pair<int, int>> dq;
// 起点 (0,0)
dist[0][0] = grid[0][0]; // 起点是否是黑色
dq.push_back({0, 0});
// BFS 开始
while (!dq.empty()) {
auto [x, y] = dq.front();
dq.pop_front();
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 检查是否越界
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
int new_dist = dist[x][y] + grid[nx][ny];
// 如果找到更短路径
if (new_dist < dist[nx][ny]) {
dist[nx][ny] = new_dist;
// 白色格子优先放前端，黑色格子放后端
if (grid[nx][ny] == 0) {
dq.push_front({nx, ny});
} else {
dq.push_back({nx, ny});
}
}
}
}
}
// 输出结果
cout << dist[n-1][m-1] << endl;
return 0;
}
每个格子最多进出队列两次，时间复杂度为 O(n×m)
