模擬應用: 順時針迴旋路徑 Spiral Matrix III_Leetcode #885

k null on Unsplash

題目敘述:

給定一個二維陣列的高與寬，並且給定起點位置座標。

測試範例

Example 1:

Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

約束條件

Constraints:

• 1 <= rows, cols <= 100

陣列的高和寬都介於1~100之間。

• 0 <= rStart < rows

起點的row一定是合法位置。

• 0 <= cStart < cols

起點的column一定是合法位置。

演算法 模擬順時針走法

順時針拜訪方向固定是往右，往下，往左，往上。

初始step步伐為一步。

進入迴圈

接著往右step步，往下step步。

step 累加多一步

接著往左step步，往上step步。

step 累加多一步

...如此反覆循環，一直到拜訪所有陣列的格子點為止。

程式碼 模擬順時針走法

class Solution():
    
    def spiralMatrixIII(self, R, C, r0, c0):

        # path, initialized on starting point
        path = [(r0, c0)] 

        is_valid = lambda row, col: 0 <= row < R and 0 <= col < C
        
        # length of steps to move
        steps = 1 
        r, c = r0, c0 

        # Keep walking until all grids are visited
        while len(path) < R * C: 

            # Go east 
            for step in range(steps):
                r, c = r, c + 1 
                if is_valid(r, c): path.append((r, c))
                    
            # Go down 
            for step in range(steps):
                r, c = r + 1, c 
                if is_valid(r, c): path.append((r, c))
                    
            steps += 1
                    
            # Go west 
            for step in range(steps):
                r, c = r, c - 1
                if is_valid(r, c): path.append((r, c))           
            
            # Go north 
            for step in range(steps):
                r, c = r - 1, c 
                if is_valid(r, c): path.append((r, c))           
                    
            steps += 1
            
        return path 

複雜度分析

時間複雜度: O( Max{R, C}^2)

相當於以起點為圓心，邊長為半徑，以同心圓擴散，
順時針走的圖形，走的軌跡是一個回字型。
所需時間 = O( Max{R, C}^2) ~ (比較長的邊長)的平方

空間複雜度: O( R * C )

需要額外一個陣列去儲存走過的格子點，格子點總數 = 陣列大小 = R * C

Reference

[1]Spiral Matrix III - LeetCode