leetcode
leetcode 301 ~ 350
轰炸敌人

轰炸敌人

难度:

标签:

题目描述

代码结果

运行时间: 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[i][j] 设置为 0 当 grid[i][j] == 'E' 是因为敌人本身不能被算作可以攻击的敌人数量。此处设置为 0 的目的是防止其自身被计算在内。这不会导致计算错误,反而是为了确保不将当前位置的敌人也算作可攻击的敌人。每个敌人都只在其被首次遇到时计数,之后即使在同一行或列中再次遇到也应重置计数器,以避免重复计数。
🦆
在更新 dprow 和 dpcol 数组时,你是如何确保不会重复计算同一行或同一列中的敌人数目?
在更新 dprow 和 dpcol 数组时,通过在遇到墙('W')时重置当前计数(设置为 0),确保每段连续的空地只统计到该段中的敌人。此外,在从一个方向开始遍历时,每次更新只基于当前方向的统计,当方向改变时,重置统计,这样可以避免重复计算同一行或同一列中的敌人数目。
🦆
为什么在计算每个空格能消灭的敌人总数时,直接将 dprow 和 dpcol 对应的值相加即可?这种方法是否考虑到了墙('W')的阻挡效应?
在计算每个空格能消灭的敌人总数时,直接将 dprow 和 dpcol 对应的值相加是可行的,因为这两个数组分别统计了在不考虑墙阻挡时,从行和列两个维度可以攻击到的敌人数。每个数组的更新过程中已经考虑到了墙的阻挡效果,即每次遇到墙时,计数会被重置。因此,这两个数组的值加起来即表示在没有墙阻挡的情况下,该点潜在能够攻击到的敌人总数。

相关问题