361. Bomb Enemy

最后更新

二刷
11-Jan-2017

首先，正常做的话，是每个格子都纵向横向CHECK一下，这样复杂度爆炸。。

看起来是用dp[][]记录情况，避免重复计算。但是这样的话，得有2个dp[][]，分别记录某一个格子可在横向和纵向分别干死多少敌人。空间复杂度又爆炸。。O(2MN)

不过可以优化。

遍历的时候是从上往下，从左往右，所以对于grid[i][j]来说，假如他左边也是炸弹，那他横向能消灭多少敌人和左边格子横向消灭敌人数量一致。
纵向看他上面是不是炸弹，是的话也和上面能消灭的纵向敌人的数量一致。

所以对于一个格子，如果他左面或者上面是炸弹，可以直接用上面的数据，否则就要重新计算需要的方向，最后2个方向加起来。

空间上，每一行用一个变量记录能干死多少人就行了，纵向得一维数组，记录上一行这个位置能干死几个。

叙述挺麻烦，看眼代码一目了然。

Time Complexity:
O(MN)? 不会做，每个格子遍历，但是貌似worst case不太肯定，WORSTCASE是2个方向都要测一下，这也就意味着下一行下一列的格子不需要这样做了。。所以= =不确定。

Space: O(N)

public class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid.length == 0) return 0;
        
        int rows = grid.length;
        int cols = grid[0].length;
        int rowKill = 0;
        int[] colKill = new int[cols];
        
        int res = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                
                // horizontal
                if (j == 0 || grid[i][j-1] == 'W') {
                    rowKill = 0;
                    for (int t = j; t < cols && grid[i][t] != 'W'; t++) {
                        if (grid[i][t] == 'E') rowKill ++;
                    }
                }
                
                // vertical
                if (i == 0 || grid[i-1][j] == 'W') {
                    colKill[j] = 0;
                    for (int t = i; t < rows && grid[t][j] != 'W'; t++) {
                        if (grid[t][j] == 'E') colKill[j] ++;
                    }
                }
                
                int tempTotal = rowKill + colKill[j];
                if (grid[i][j] == '0') {
                    res = Math.max(res, tempTotal);
                }
            }
        }
        
        return res;
    }
}

一刷
14-Oct-2016

这个题确实不会。。只能想到naive的做法，不过那样应该是O(n³)，不会满足要求。

看TAG是DP，那应该是建立DP[][]记录每点可炸的情况。一个点如果左边/上边是墙，或者左边/上边是边界，就要重新计算，否则跟左边/上边的那个格子的情况一样。是空位就来一发，然后取最大。

这样应该是mn的extra space，时间变成（常数，但是不知道是什么。。）*n²。

不是很确定，看了答案，发现很巧妙。。

因为遍历是在一行一行的基础上，每列每列，所以没必要MN的extra space，一个变量记录每行的情况，过了那一行就自动更新，另一个int[cols]记录每列的情况就行了。。

时间上还是常熟*（n²)

public class Solution 
{
    public int maxKilledEnemies(char[][] grid) 
    {
        if(grid.length == 0) return 0;
        
        int res = 0;
        int row = 0; 
        int[] col = new int[grid[0].length];
        
        for(int i = 0; i < grid.length;i++)
        {
            for(int j = 0; j < grid[0].length;j++)
            {
                if(i == 0 || grid[i-1][j] == 'W')
                {
                    col[j] = 0;
                    int t = i;
                    while(t < grid.length && grid[t][j] != 'W')
                    {
                        if(grid[t][j] == 'E') col[j]++;
                        t++;
                    }
                }
                
                if(j == 0 || grid[i][j-1] == 'W')
                {
                    row = 0;
                    int t = j;
                    while(t < grid[0].length && grid[i][t] != 'W')
                    {
                        if(grid[i][t] == 'E') row++;
                        t++;
                    }
                }
                
                if(grid[i][j] == '0') res = Math.max(res,col[j]+row);
            }
            
        }   
            
        return res;
    }
}