轰炸敌人
难度:
标签:
题目描述
代码结果
运行时间: 184 ms, 内存: 42.7 MB
/*
* Leetcode 题目:轰炸敌人
* 题目思路:
* 给定一个网格,每个网格可能是墙、敌人或者空位。我们需要在一个空位上放置炸弹,炸弹可以摧毁同一行和同一列的所有敌人,直到遇到墙为止。
* 目标是找出一个位置,使得这个位置可以摧毁尽可能多的敌人。
* 使用Java Stream的方式实现。
*/
import java.util.stream.IntStream;
public class BombEnemyStream {
public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
final int rows = grid.length;
final int cols = grid[0].length;
int[] max = {0};
IntStream.range(0, rows).forEach(i -> {
int[] rowHits = {0};
int[] colHits = new int[cols];
IntStream.range(0, cols).forEach(j -> {
if (j == 0 || grid[i][j - 1] == 'W') {
rowHits[0] = (int) IntStream.range(j, cols).takeWhile(k -> grid[i][k] != 'W').filter(k -> grid[i][k] == 'E').count();
}
if (i == 0 || grid[i - 1][j] == 'W') {
colHits[j] = (int) IntStream.range(i, rows).takeWhile(k -> grid[k][j] != 'W').filter(k -> grid[k][j] == 'E').count();
}
if (grid[i][j] == '0') {
max[0] = Math.max(max[0], rowHits[0] + colHits[j]);
}
});
});
return max[0];
}
}
解释
方法:
这个题解的思路是使用两个动态规划数组 dprow 和 dpcol 分别记录每个空格左边和上边的敌人数量。首先,遍历每一行,用 dprow 数组记录当前行每个空格左边的敌人数量。接着从右到左再次遍历该行,更新 dprow 数组,使其记录每个空格左右两侧的最大敌人数量。然后,用类似的方法遍历每一列,用 dpcol 数组记录每个空格上下两侧的最大敌人数量。最后,遍历整个网格,将每个空格在 dprow 和 dpcol 中对应的值相加,得到该空格所能消灭的敌人总数,并更新全局最大值。
时间复杂度:
O(mn)
空间复杂度:
O(mn)
代码细节讲解
🦆
为什么在处理每一行和每一列时,需要分别从两个方向进行遍历?
▷🦆
在从右到左遍历时,为什么将 dprow[i][j] 设置为 0 当 grid[i][j] == 'E'?这是否会导致计算上的错误?
▷🦆
在更新 dprow 和 dpcol 数组时,你是如何确保不会重复计算同一行或同一列中的敌人数目?
▷🦆
为什么在计算每个空格能消灭的敌人总数时,直接将 dprow 和 dpcol 对应的值相加即可?这种方法是否考虑到了墙('W')的阻挡效应?
▷