Skip to content

361 Bomb Enemy

361. Bomb Enemy

题目: https://leetcode.com/problems/bomb-enemy/

难度:

Medium

思路

  1. 首先，从每一行开始，从左到右，计算E的个数，然后一碰到W就将row_hits重置为0，一碰到0就将row_hits赋值给他
  2. 然后，从每一行开始，从右到左，原操作不变，唯一是碰到0的时候加上row_hits而不是直接等于row_hits
  3. 接下来，就是跟第二步一样的操作，只不过是变成了从每一列开始，从上到下
  4. 最后也是跟第二步一样的操作，只不过是变成了从每一列开始，并且是从下到上，然后就是每一次碰到0不但要加上col_hits的值还要决出max_hits
  5. 返回max_hits

时间复杂度是 O(m*n) * (m+n)

        if not grid or len(grid) == 0:
            return 0
        max_hits = 0
        nums = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]

        for i in range(len(grid)):
            row_hits = 0
            for j in range(len(grid[0])):
                if grid[i][j] == 'E':
                    row_hits += 1
                elif grid[i][j] == 'W':
                    row_hits = 0
                else:
                    nums[i][j] = row_hits

        for i in range(len(grid)):
            row_hits = 0
            for j in range(len(grid[0])-1, -1, -1):
                if grid[i][j] == 'E':
                    row_hits += 1
                elif grid[i][j] == 'W':
                    row_hits = 0
                else:
                    nums[i][j] += row_hits

        for i in range(len(grid[0])):
            col_hits = 0
            for j in range(len(grid)):
                if grid[j][i] == 'E':
                    col_hits += 1
                elif grid[j][i] == 'W':
                    col_hits = 0
                else:
                    nums[j][i] += col_hits

        for i in range(len(grid[0])):
            col_hits = 0
            for j in range(len(grid)-1, -1, -1):
                if grid[j][i] == 'E':
                    col_hits +=1
                elif grid[j][i] == 'W':
                    col_hits = 0
                else:
                    nums[j][i] += col_hits
                    max_hits = max(max_hits, nums[j][i])


        return max_hits
回到顶部