1. 问题背景与题目解析甲板上的战舰这个题目乍看有些抽象实际上它源自一道经典的算法编程题。题目描述通常是给定一个二维的甲板矩阵上面用X和.标记了战舰的位置和空白区域。战舰只能水平或垂直放置且不会相邻即没有两艘战舰在水平或垂直方向上相邻。要求统计甲板上战舰的数量。这个题目看似简单但考察了以下几个核心能力对二维矩阵的遍历和理解对相邻元素关系的判断对边界条件的处理对问题本质的抽象能力2. 战舰识别的基本思路2.1 直观解法分析最直观的解法是遍历整个矩阵每当遇到一个X时就检查它的上方和左方是否也是X。如果不是则认为这是一个新的战舰的头部计数器加一。这种方法的正确性基于题目给出的两个关键约束战舰只能是1xN或Nx1的形状即水平或垂直战舰之间不会相邻2.2 代码实现示例def countBattleships(board): count 0 for i in range(len(board)): for j in range(len(board[0])): if board[i][j] X: # 检查上方和左方是否也是X if (i 0 or board[i-1][j] ! X) and (j 0 or board[i][j-1] ! X): count 1 return count这个解法的时间复杂度是O(mn)其中m和n分别是矩阵的行数和列数空间复杂度是O(1)因为只使用了常数个额外空间。3. 算法优化与边界条件3.1 为什么不需要检查所有四个方向很多初学者会疑惑为什么只需要检查上方和左方而不需要检查下方和右方。这是因为如果当前X是一个战舰的中间部分那么它的上方或左方必然已经有一个X题目保证战舰不会相邻所以不需要担心其他战舰的影响从左上到右下的遍历顺序确保了每个战舰只会被计数一次3.2 边界条件处理需要特别注意矩阵边界的情况当i0时不需要检查上方当j0时不需要检查左方空矩阵的情况虽然题目通常保证非空4. 实际应用场景4.1 游戏开发中的应用这个算法虽然简单但在游戏开发中有实际应用价值。例如战舰类游戏的自动布局验证游戏存档的状态统计AI对手的局势分析4.2 图像处理中的连通区域计数类似的算法可以应用于图像处理中的连通区域计数只需将X视为目标像素.视为背景。虽然实际图像处理需要考虑8连通而不仅仅是4连通但核心思路是相通的。5. 常见错误与调试技巧5.1 初学者容易犯的错误双重计数没有正确处理战舰的连续性导致同一艘战舰被多次计数边界越界在检查相邻元素时没有考虑矩阵边界修改原矩阵有些解法会修改原矩阵来标记已访问的位置这在某些场景下可能不被允许5.2 调试建议对于这类矩阵遍历问题建议先用小例子手工模拟算法过程打印中间结果验证逻辑特别注意边界情况如全X、全.、单行、单列等6. 算法扩展与变种6.1 允许战舰相邻的情况如果去掉战舰不相邻的限制问题会变得复杂很多。这时需要使用DFS或BFS来标记已访问的位置需要额外的空间来记录访问状态时间复杂度可能提高到O(mn)但空间复杂度变为O(mn)6.2 三维战舰识别如果将问题扩展到三维空间比如立体战舰游戏算法需要增加z轴方向的检查考虑三维连通性使用三维数组来表示空间7. 性能优化实践对于非常大的矩阵可以考虑以下优化并行处理将矩阵分块在多核或GPU上并行计算增量更新如果矩阵是动态变化的可以只重新计算受影响区域压缩存储对于稀疏矩阵使用特殊数据结构节省空间8. 个人实战经验分享在实际编程比赛中这类题目看似简单但很容易因为粗心失分。我的经验是一定要先明确题目给出的所有约束条件写代码前先用几个小例子验证思路特别注意循环的边界条件变量命名要清晰比如用rows和cols而不是m和n添加适当的注释说明关键逻辑提示在面试中遇到这类题目时建议先和面试官确认所有假设条件比如战舰的形状限制、相邻规则等。清晰的沟通有时比完美的代码更重要。
1. 问题背景与题目解析甲板上的战舰这个题目乍看有些抽象实际上它源自一道经典的算法编程题。题目描述通常是给定一个二维的甲板矩阵上面用X和.标记了战舰的位置和空白区域。战舰只能水平或垂直放置且不会相邻即没有两艘战舰在水平或垂直方向上相邻。要求统计甲板上战舰的数量。这个题目看似简单但考察了以下几个核心能力对二维矩阵的遍历和理解对相邻元素关系的判断对边界条件的处理对问题本质的抽象能力2. 战舰识别的基本思路2.1 直观解法分析最直观的解法是遍历整个矩阵每当遇到一个X时就检查它的上方和左方是否也是X。如果不是则认为这是一个新的战舰的头部计数器加一。这种方法的正确性基于题目给出的两个关键约束战舰只能是1xN或Nx1的形状即水平或垂直战舰之间不会相邻2.2 代码实现示例def countBattleships(board): count 0 for i in range(len(board)): for j in range(len(board[0])): if board[i][j] X: # 检查上方和左方是否也是X if (i 0 or board[i-1][j] ! X) and (j 0 or board[i][j-1] ! X): count 1 return count这个解法的时间复杂度是O(mn)其中m和n分别是矩阵的行数和列数空间复杂度是O(1)因为只使用了常数个额外空间。3. 算法优化与边界条件3.1 为什么不需要检查所有四个方向很多初学者会疑惑为什么只需要检查上方和左方而不需要检查下方和右方。这是因为如果当前X是一个战舰的中间部分那么它的上方或左方必然已经有一个X题目保证战舰不会相邻所以不需要担心其他战舰的影响从左上到右下的遍历顺序确保了每个战舰只会被计数一次3.2 边界条件处理需要特别注意矩阵边界的情况当i0时不需要检查上方当j0时不需要检查左方空矩阵的情况虽然题目通常保证非空4. 实际应用场景4.1 游戏开发中的应用这个算法虽然简单但在游戏开发中有实际应用价值。例如战舰类游戏的自动布局验证游戏存档的状态统计AI对手的局势分析4.2 图像处理中的连通区域计数类似的算法可以应用于图像处理中的连通区域计数只需将X视为目标像素.视为背景。虽然实际图像处理需要考虑8连通而不仅仅是4连通但核心思路是相通的。5. 常见错误与调试技巧5.1 初学者容易犯的错误双重计数没有正确处理战舰的连续性导致同一艘战舰被多次计数边界越界在检查相邻元素时没有考虑矩阵边界修改原矩阵有些解法会修改原矩阵来标记已访问的位置这在某些场景下可能不被允许5.2 调试建议对于这类矩阵遍历问题建议先用小例子手工模拟算法过程打印中间结果验证逻辑特别注意边界情况如全X、全.、单行、单列等6. 算法扩展与变种6.1 允许战舰相邻的情况如果去掉战舰不相邻的限制问题会变得复杂很多。这时需要使用DFS或BFS来标记已访问的位置需要额外的空间来记录访问状态时间复杂度可能提高到O(mn)但空间复杂度变为O(mn)6.2 三维战舰识别如果将问题扩展到三维空间比如立体战舰游戏算法需要增加z轴方向的检查考虑三维连通性使用三维数组来表示空间7. 性能优化实践对于非常大的矩阵可以考虑以下优化并行处理将矩阵分块在多核或GPU上并行计算增量更新如果矩阵是动态变化的可以只重新计算受影响区域压缩存储对于稀疏矩阵使用特殊数据结构节省空间8. 个人实战经验分享在实际编程比赛中这类题目看似简单但很容易因为粗心失分。我的经验是一定要先明确题目给出的所有约束条件写代码前先用几个小例子验证思路特别注意循环的边界条件变量命名要清晰比如用rows和cols而不是m和n添加适当的注释说明关键逻辑提示在面试中遇到这类题目时建议先和面试官确认所有假设条件比如战舰的形状限制、相邻规则等。清晰的沟通有时比完美的代码更重要。
