最近，组里来了一个新人，这哥们儿真是把“技术大牛”这一标签演绎得淋漓尽致！GitHub每天打卡，周末坚持写技术博客，甚至在各种技术群里辩论得不亦乐乎。说实话，看到他那台MacBook上贴满了各种框架和工具的酷炫贴纸。。
不过，最有意思的事发生在我们一起解决一个React性能优化问题的时候。
大家都在琢磨怎么优化，而这位“技术大神”居然淡定地说：“这个问题我在博客里写过，具体怎么解决...我得再查查资料。”
这啥情况？还需要“查资料”？
评论区有人说得挺有道理：“好记性不如烂笔头，谁能记得住所有东西啊？”确实，谁能记得住所有的技术细节呢？
再牛的技术大神，也有遗忘的时候嘛。咱们也别太苛刻，毕竟，我们自己也不可能做到事事都记得住，对吧？
算法题：棋盘上的战舰
今天想和大家聊聊一道挺有意思的算法题：棋盘上的战舰。说起来，这道题应该是某些面试题的常客，也算是“经典”题目之一。
题目背景是这样的：给定一个棋盘（一个二维数组），其中有战舰标记。战舰占据连续的若干个格子，可能是水平的，也可能是竖直的。我们需要找出有多少艘战舰。重要的是，战舰的格子之间是没有空格的，也就是说，每一艘战舰是“连体”的。如果有一个‘X’代表战舰的格子，‘.’代表空地，那么我们就要统计出整个棋盘中有多少艘战舰。
这类题目其实考察的点比较多，既考察如何遍历二维数组，也考察如何判断战舰之间的关系。好，废话不多说，直接上代码。首先，我们需要清楚，问题的本质是“如何通过检查战舰的边界来确定有多少艘战舰”。
public class Battleships {
public int countBattleships(char[][] board) {
if (board == null || board.length == 0) return 0;
int count = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
// 如果当前位置是战舰部分
if (board[i][j] == 'X') {
// 判断它是不是一艘新战舰
// 只要它不是左边和上边的战舰的一部分，就说明它是新战舰的一部分
if (i > 0 && board[i - 1][j] == 'X') {
continue; // 上方已经有了战舰，不算新战舰
}
if (j > 0 && board[i][j - 1] == 'X') {
continue; // 左边已经有了战舰，不算新战舰
}
count++; // 统计新战舰
}
}
}
return count;
}
public static void main(String[] args) {
Battleships solution = new Battleships();
char[][] board = {
{'X', '.', '.', 'X'},
{'.', '.', '.', 'X'},
{'.', '.', '.', 'X'}
};
System.out.println("Number of Battleships: " + solution.countBattleships(board));
}
}
这个代码实现了一个比较直接的方法，通过逐行逐列扫描棋盘上的每个格子来查找战舰。重点在于：我们需要检查当前格子是不是战舰的一部分，同时需要确定它是不是新战舰的起点。要知道，战舰在棋盘上可以是横向的，也可以是竖向的，因此如果左边和上边已经有战舰了，就说明当前的格子不是新战舰的起点。
代码解读：
边界检查：首先通过条件判断，确保我们不会访问数组越界的地方。 i > 0和j > 0用来判断当前格子的上方和左边是否已经有战舰。计数：如果当前格子是‘X’且其左边和上边没有战舰格子，我们就认为这是一个新的战舰的开始，所以加上计数。 效率：该方法的时间复杂度是O(m * n)，其中m和n分别是棋盘的行和列数，空间复杂度是O(1)，因为我们没有使用额外的空间。
小技巧：
避免重复计算：在这道题里，最关键的就是如何避免重复计算同一艘战舰。比如说，战舰的某些部分可能会被多次计数，但我们通过上边和左边的判断来确保不会重复计数。 代码优化：如果你觉得棋盘特别大，有一些额外的空间优化思路，比如将棋盘压缩成一个一维数组，然后进行遍历，但这会增加一定的复杂度，不太推荐除非特别需要。
可能的坑：
不区分竖直和横向：这道题最容易犯的错误之一就是没有考虑到竖直和横向战舰的情况。不要认为棋盘上每个‘X’都代表一艘独立的战舰！‘X’可能是横向的一部分，也可能是竖直的一部分，所以我们要准确地判断它是不是新战舰的一部分。 边界问题：当扫描到棋盘的边缘时，一定要确保没有越界访问。毕竟，我们是通过检查上方和左侧格子的‘X’来避免重复计数的。
总结一下，解决这道题的关键就在于如何判断一个格子是否是新战舰的起点。通过判断其左边和上边的格子，我们可以轻松避免重复计数。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
