666
2025-08-03 20:38:19
发布于：浙江
二分查找
时间复杂度 O(logn)
前提: 数组是 有序的
1、二分模板
// 确定左右端点（二分范围）
int l = 左端点,r = 右端点;
int ans = 初始化;
while(l<=r){
// 1、找中间值
int mid=(l+r)/2;
// 2、比较查找到中间元素和目标元素的大小
if( ){ // 符合条件的情况
ans=mid; // 答案更新为 mid
// 缩小范围 画图！判断缩小左边界还是右边界
// l=mid+1; r=mid-1;
}
else{
// 缩小范围 和上一个反过来
// r=mid-1; l=mid+1;
}
}
3、lower_bound 和 upper_bound
在 a 数组中找到第一个大于等于 x 的元素 (下界)
lower_bound(a + 1, a + n + 1, x) - a;
在 a 数组中找到第一个大于 x 的元素 (上界)
upper_bound(a + 1, a + n + 1, x) - a;
应用: 快速找到某个数 x 在 有序 数组中的个数
x 的下界 - x 的上界 = x 的个数
全部评论 1
一个非常典型的信奥竞赛题目——扫雷游戏的数字生成问题。这道题虽然看起来训练我们对**二维数组处理、边界判断能力的经典范例。作为你的老师，我会一步步引导你深入理解这个问题，并帮助你构建清晰的解题思路。
🌟 第一步：理解题意，明确任务
我们先来“翻译”一下题目在说什么：给定一个 n × m 的字符网格。
每个格子要么是地雷（用 * 表示），要么是非地雷（用 ? 表示）。
我们的任务是：把每一个 ? 替换成一个数字，这个数字表示它周围8个方向相邻格子中格（即 *）。
而原本就是 * 的格子 所以最终输出是一个更新后的网格：
地雷格仍然是 *
非地雷格变成对应的“周围地雷数量”的数字字符（如 '0', '1', ..., '8'）
###样例，验证理解我们来看第一组样例：
输入：
3 3
??
???
??期望输出：
10
221
11
我们手动模拟几个关键点：左上角 [0][0] 输出还是 *
[0][1] 是 ?，它的邻居有哪些 它的八个方向中，只有右边 [0][2] 和下面 [1][0], [1][ 等可能相关。 实与 [0][）是地雷 →为 1
[0][2] 是 ?，它的左边 [0][1] 不是地雷，下方]和[1][2]呢？都不是是0`
继续下去……你会发现输出对每个非地雷格进行一次“数周围地雷个数”的操作。💡 第三步：思考核心问题 —— 如何高效计算“周围地雷数”？
现在于每一个格子 (i, j)，如果它是 ?，我们就需要检查它的八个邻居中，有多少个是我们可以考虑以下策略循环 + 方向偏移法使用两层循环遍历整个 n × m 的网格。
当前位置是 *，就保留；
如果是 ?，则进入“计数模式”：
枚举8个方向：上、下、左、右、四个对角线
对每个方向，计算新坐标 (ni, nj)
判断 (ni, nj) 是否越界（是否在 [0, n) 和 [0, m) 内）
如果没越界且原图中该位置是 *，计数器加一
最后把这个计数值转换成字符（比如 cnt=2 → '2'🧠 关键技巧提示：你可以定义一个“方向数组”来简化代码！
例如：int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, -1, 1, -1, 0, 1};
这样就可以用一个循环遍历8个方向，而不是写8次 if。⚠️ 第四步：注意边界情况
这是很多同学容易出错的地方！当你在一个角落（比如 (0,0)）时，很多邻居根本不存在。必须做越界检查！
例如：
不能访问 [-1][-1] 或 [n][m] 这样的非法地址。📌 提醒：C界会导致未定义行为（可能是崩溃或错误答案）。所以每坐标是否合法。
###结构与实现建议
输入可以用 `字符数组存储。
可以直接在原数组上修改（因为题目不要求保留原始 ?字要转成字符：char c = '0' + count;
###拓展：有没有其他方法？你现在可以思考一下：
能否反过来所有地雷，然后影响”周围的非地雷格？
-地雷格的计数都 +1？
💡 这也是一种可行思路！相当于“反向传播”，适合某些变种题目（比如动态更新先掌握正向枚举的方法更稳妥。✅这道题，奥核心技能：
技能 说明
二维数组遍历 熟练使用嵌套循环处理网格
方向枚举技巧 使用 dx/dy 数组处理上下左右等方向
边界条件处理 提升程序鲁棒性
字符与数字转换 '0' + num 的常用技巧
📚我建议你现在尝试：
1.模拟第二组样例，确认你能。
2. 然后尝试写出伪代码（中文步骤描述）。
3. 再试着写出 C++ 代码框架，尤其是那个“8方向循环”的部分。
4.比如只有一个格子、全是地雷、全是非地雷等情况。如果你在写代码不知道怎么判断越界、或者方向数组不会用），欢迎回来问我：“老师，我在XX步骤卡住了，我的想法是XXX，您觉得哪里有问题？”
而不是直接告诉你答案。
记住：**真正的成长来自于自己动手正确的思路上了！💪
2025-12-24 来自 浙江
1
有帮助，赞一个