转自Kindem的博客

问题

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

优雅解法--动态规划

一行(列)经过两次扫描来标记出该行(列)所有位置的Order，总共经过四轮扫描之后获取所有位置的Order从而求出Order最大值

class Solution:
    def orderOfLargestPlusSign(self, N, mines):
        """
        :type N: int
        :type mines: List[List[int]]
        :rtype: int
        """
        banned = {tuple(mine) for mine in mines}
        depth = [[0] * N for _ in range(N)]
        answer = 0

        for row in range(N):
            count = 0
            for col in range(N):
                count = 0 if (row, col) in banned else count + 1
                depth[row][col] = count

            count = 0
            for col in range(N - 1, -1, -1):
                count = 0 if (row, col) in banned else count + 1
                if count < depth[row][col]:
                    depth[row][col] = count

        for col in range(N):
            count = 0
            for row in range(N):
                count = 0 if (row, col) in banned else count + 1
                if count < depth[row][col]:
                    depth[row][col] = count

            count = 0
            for row in range(N - 1, -1, -1):
                count = 0 if (row, col) in banned else count + 1
                if count < depth[row][col]:
                    depth[row][col] = count
                if depth[row][col] > answer:
                    answer = depth[row][col]

        return answer

学到了什么

1. 遇到暴力求解时间复杂度过大的问题，应该转而优先考虑动态规划，面对数组、字符串问题也应该多考虑一下动态规划，并且利用各种语法糖和语言特性降低时间消耗
2. 语法糖: 一行初始化列表、元组等容器
3. 语法糖：for中垃圾桶变量的使用