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

閒聊

感覺我今天講解的滿爛的，實在是不知道要怎麼寫才好，如果有動畫的話會更好理解

另外，如果有不認識DP的讀者，蠻建議照著這網頁用DP練習寫費氏數列，稍微體驗一下DP的感覺