[LeetCode] 361. Bomb Enemy 炸敌人
2024-10-20 21:13:40
Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.
Example:
For the given grid 0 E 0 0
E 0 W E
0 E 0 0 return 3. (Placing a bomb at (1,1) kills 3 enemies)
Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.
方法一：
遍历数组中的每一个点，当前点能够得到的最大值为从左边的头（边界或wall）到右边的头（遇到边界或wall）的值（row值）＋从上面的头（边界或wall）到下面的头（遇到边界或wall）的值（col值）。每一个row范围内的点都共用当前的row值，每一个col范围内的点都共用当前col值。当从新的边界或者wall开始时，相当于进入了新的一段范围，要重新计算row值或者col值。
1.遍历数组中每一个点，若为0则开始计算
2.若当前点为第一列或者左边一个点为wall，表明进入了一个新的区间，需要重新计算。从该点开始一直向右直到遇到边界或者wall，在该过程中，每遇到一个E就将row值＋1+
3.若当前点为第一行或者上边一个点为wall，表明进入了一个新的区间，需要重新计算。从该点开始一直向下直到遇到边界或者wall，在该过程中，每遇到一个E就将col值＋1
4.重复2-3步骤
方法二：
上面的方法，会存在大量的重复计算。好的解法是用DP，用一个cache来存下部分结果来避免重复运算。这里用一个m*2的数组enemyCount来储存每一行的结果。enemyCount[i][0]储存了第i行某一个W的位置，enemyCount[i][1]储存了enemyCount[i][0]所标识的W到之前一个W之间E的个数，初始化：enemyCount[i][0] = -1，enemyCount[i][1] = 0。
Java: Iteration
public class Solution {
/**
* @param grid Given a 2D grid, each cell is either 'W', 'E' or '0'
* @return an integer, the maximum enemies you can kill using one bomb
*/
public int maxKilledEnemies(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
int m = grid.length;
int n = grid[0].length;
int result = 0;
int rows = 0;
int[] cols = new int[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (j == 0 || grid[i][j-1] == 'W') {
rows = 0;
for (int k = j; k < n && grid[i][k] != 'W'; ++k)
if (grid[i][k] == 'E')
rows += 1;
}
if (i == 0 || grid[i-1][j] == 'W') {
cols[j] = 0;
for (int k = i; k < m && grid[k][j] != 'W'; ++k)
if (grid[k][j] == 'E')
cols[j] += 1;
}
if (grid[i][j] == '0' && rows + cols[j] > result)
result = rows + cols[j];
}
}
return result;
}
}
Java: Iteration
public class Solution {
public int maxKilledEnemies(char[][] A) {
if (A == null || A.length == 0 || A[0].length == 0) {
return 0;
}
int m = A.length;
int n = A[0].length;
int[][] up = new int[m][n];
int[][] down = new int[m][n];
int[][] left = new int[m][n];
int[][] right = new int[m][n];
int i, j, t;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
up[i][j] = 0;
if (A[i][j] != 'W') {
if (A[i][j] == 'E') {
up[i][j] = 1;
}
if (i - 1 >= 0) {
up[i][j] += up[i-1][j];
}
}
}
}
for (i = m - 1; i >= 0; --i) {
for (j = 0; j < n; ++j) {
down[i][j] = 0;
if (A[i][j] != 'W') {
if (A[i][j] == 'E') {
down[i][j] = 1;
}
if (i + 1 < m) {
down[i][j] += down[i+1][j];
}
}
}
}
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
left[i][j] = 0;
if (A[i][j] != 'W') {
if (A[i][j] == 'E') {
left[i][j] = 1;
}
if (j - 1 >= 0) {
left[i][j] += left[i][j-1];
}
}
}
}
for (i = 0; i < m; ++i) {
for (j = n - 1; j >= 0; --j) {
right[i][j] = 0;
if (A[i][j] != 'W') {
if (A[i][j] == 'E') {
right[i][j] = 1;
}
if (j + 1 < n) {
right[i][j] += right[i][j+1];
}
}
}
}
int res = 0;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
if (A[i][j] == '0') {
t = up[i][j] + down[i][j] + left[i][j] + right[i][j];
if (t > res) {
res = t;
}
}
}
}
return res;
}
}
Java: DP
public class Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int[][] enemyCount = new int[grid.length][2];
for (int i = 0; i < enemyCount.length; i++) {
enemyCount[i][0] = -1;
}
int max = 0;
for (int j = 0; j < grid[0].length; j++) {
int colEnemy = countColEnemy(grid, j, 0);
for (int i = 0; i < grid.length; i++) {
if (grid[i][j] == '0') {
if (j > enemyCount[i][0]) {
update(enemyCount, grid, i, j);
}
max = Math.max(colEnemy + enemyCount[i][1], max);
}
if (grid[i][j] == 'W') {
colEnemy = countColEnemy(grid, j, i + 1);
}
}
}
return max;
}
private void update(int[][] enemyCount, char[][] grid, int i, int j) {
int count = 0;
int k = enemyCount[i][0] + 1;
while (k < grid[0].length && (grid[i][k] != 'W' || k < j)) {
if (grid[i][k] == 'E') {
count += 1;
}
if (grid[i][k] == 'W') {
count = 0;
}
k += 1;
}
enemyCount[i][0] = k;
enemyCount[i][1] = count;
}
private int countColEnemy(char[][] grid, int j, int start) {
int count = 0;
int i = start;
while (i < grid.length && grid[i][j] != 'W') {
if (grid[i][j] == 'E') {
count += 1;
}
i += 1;
}
return count;
}
}
Python:
class Solution(object):
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
result = 0
if not grid or not grid[0]:
return result down = [[0 for _ in xrange(len(grid[0]))] for _ in xrange(len(grid))]
right = [[0 for _ in xrange(len(grid[0]))] for _ in xrange(len(grid))]
for i in reversed(xrange(len(grid))):
for j in reversed(xrange(len(grid[0]))):
if grid[i][j] != 'W':
if i + 1 < len(grid):
down[i][j] = down[i + 1][j]
if j + 1 < len(grid[0]):
right[i][j] = right[i][j + 1]
if grid[i][j] == 'E':
down[i][j] += 1
right[i][j] += 1 up = [0 for _ in xrange(len(grid[0]))]
for i in xrange(len(grid)):
left = 0
for j in xrange(len(grid[0])):
if grid[i][j] == 'W':
up[j], left = 0, 0
elif grid[i][j] == 'E':
up[j] += 1
left += 1
else:
result = max(result,
left + up[j] + right[i][j] + down[i][j]) return result
C++:
// Time: O(m * n)
// Space: O(m * n) class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int result = 0;
if (grid.empty() || grid[0].empty()) {
return result;
} vector<vector<int>> down{grid.size(), vector<int>(grid[0].size())};
vector<vector<int>> right{grid.size(), vector<int>(grid[0].size())};
for (int i = grid.size() - 1; i >= 0; --i) {
for (int j = grid[0].size() - 1; j >= 0; --j) {
if (grid[i][j] != 'W') {
if (i + 1 < grid.size()) {
down[i][j] = down[i + 1][j];
}
if (j + 1 < grid[0].size()) {
right[i][j] = right[i][j + 1];
}
if (grid[i][j] == 'E') {
++down[i][j];
++right[i][j];
}
}
}
} int left = 0;
vector<int> up(grid[0].size());
for (int i = 0; i < grid.size(); ++i) {
left = 0;
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 'W') {
up[j] = 0;
left = 0;
} else if (grid[i][j] == 'E') {
++up[j];
++left;
} else {
result = max(result, left + up[j] + right[i][j] + down[i][j]);
}
}
} return result;
}
};
C++:
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<int>> v1(m, vector<int>(n, 0)), v2 = v1, v3 = v1, v4 = v1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
v1[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int j = n - 1; j >= 0; --j) {
int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int i = m - 1; i >= 0; --i) {
int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
res = max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
}
}
}
return res;
}
};
C++:
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0, rowCnt, colCnt[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (j == 0 || grid[i][j - 1] == 'W') {
rowCnt = 0;
for (int k = j; k < n && grid[i][k] != 'W'; ++k) {
rowCnt += grid[i][k] == 'E';
}
}
if (i == 0 || grid[i - 1][j] == 'W') {
colCnt[j] = 0;
for (int k = i; k < m && grid[k][j] != 'W'; ++k) {
colCnt[j] += grid[k][j] == 'E';
}
}
if (grid[i][j] == '0') {
res = max(res, rowCnt + colCnt[j]);
}
}
}
return res;
}
};
All LeetCode Questions List 题目汇总
最新文章
- c++中string的常用函数说明
- Angularjs 如何在 post 请求时去掉因 ng-repeat 产生的 $$hashkey？
- Office 365 for TechNet 版本国家地区没有中国选项
- RemixOS Player 让用户在 Windows 上运行 Android App
- java的通信机制
- memcached学习——常用命令+基于java客户端的3种简单实现（二）
- 【JS】依据表格ID进行排序（附凝视）
- 杭电1162Eddy&#39;s picture
- knockout.js-创建视图模型
- Linux取代ifconfig指令的ip指令
- Linux 驱动——Button驱动7（Timer）消抖
- ARM核心板_迅为4412核心板_核心板中的小新潮
- 课程五(Sequence Models)，第一 周（Recurrent Neural Networks） —— 0.Practice questions：Recurrent Neural Networks
- b'driver "overlay" failed to remove root filesystem 的解决方法
- gtest简介及简单使用
- .NET反射的优化
- 【驱动】USB驱动实例·串口驱动·键盘驱动【转】
- 基于PhantomJS的网页抓取及写入文件
- LBP纹理特征
- org.apache.zookeeper.ClientCnxn - Got ping response for sessionid: 0x160fd6f04410017 after 0ms