LeetCode解题 Day09

764. Largest Plus Sign

https://leetcode.com/problems/largest-plus-sign/

题目解释

你会得到一个大小为n*n 的表格，接着你要在表格中划出一个最大的十字，并回传他从中心点对任一边延伸出去几格，但是有两个条件需要遵守:

第一，你画出来的十字需要四个方向都一样长

第二，在阵列mines 中标示着不能画到的座标，依照题目为这变数取的名字来看，你画到的话就会被炸死

example

解法:

这一题如果用暴力解法的话感觉就过不了O(n^3) ，所以我们用动态规划(Dynamic Programming)来减少一些计算步骤。解题的想法如下:

我们计算每个点的左右上下四个方向分别有几个空格能延伸出去，且要纪录最短的那个，例如第一行(row)的左右上下分别是[1,2,3,4,5]、[5,4,3,2,1]、[1,1,1,1,1]、[5,5,4,5,5]，所以第一行都只能涂满自己那格。

程序码

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        
        dp = [[0] * n for i in range(n)]
        banned = {tuple(mine) for mine in mines}
        # 要用set()才会比较快，我一开始没用就超时了
        
        for row in range(n): #左右
            
            count = 0
            for col in range(n): #左边有几格可以延伸
                if (row, col) not in banned:
                    count += 1
                else:
                    count = 0
                dp[row][col] = count
            
            count = 0
            for col in range(n-1, -1, -1): #右边有几格可以延伸
                if (row, col) not in banned:
                    count += 1
                else:
                    count = 0
                dp[row][col] = min(dp[row][col], count) #留下更短的那个
                
       
        for col in range(n): #上下
                
            count = 0
            for row in range(n): #上面有几格可以延伸
                if (row, col) not in banned:
                    count += 1
                else:
                    count = 0
                dp[row][col] = min(dp[row][col], count) #留下更短的那个
            
            count = 0
            for row in range(n-1, -1, -1): #下面有几格可以延伸
                if (row, col) not in banned:
                    count += 1
                else:
                    count = 0
                dp[row][col] = min(dp[row][col], count) #留下更短的那个
            
        ans = 0
        for i in dp:
            ans = max(max(i), ans) #回传最大的那个
        
        return ans