[Swift]LeetCode885.螺旋矩阵III|SpiralMatrixIII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10603685.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 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]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：R = 1, C = 4, r0 = 0, c0 = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

示例 2：

输入：R = 5, C = 6, r0 = 1, c0 = 4
输出：[[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]]

提示：

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Runtime: 128 ms

Memory Usage: 19.7 MB

 1 class Solution {
 2     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {
 3         var r = r0
 4         var c = c0
 5         var res:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:2),count:R * C)
 6         res[0] = [r, c]
 7         var x:Int = 0
 8         var y:Int = 1
 9         var n:Int = 0
10         var i:Int = 0
11         var tmp:Int = 0
12         var j:Int = 1
13         while (j < R * C)
14         {
15             r += x
16             c += y
17             i += 1
18             if 0 <= r && r < R && 0 <= c && c < C
19             {
20                 res[j] = [r, c]
21                 j += 1
22             }
23             if i == (n / 2 + 1)
24             {
25                 i = 0
26                 n += 1 
27                 tmp = x
28                 x = y
29                 y = -tmp
30             }
31         }
32         return res
33     }
34 }

128ms

 1 class Solution {
 2     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {
 3         var result = [[Int]]()
 4         var i = r0
 5         var j = c0
 6         var currentLevel = 1
 7         self.appendResultIfInMatrix(&result,i,j,R,C) //adding first element
 8         while true {
 9             for _ in 1 ... currentLevel {
10                 j += 1
11                 self.appendResultIfInMatrix(&result,i,j,R,C)
12             }
13             if result.count == R*C {
14                 break
15             }
16             for _ in 1 ... currentLevel {
17                 i += 1
18                 self.appendResultIfInMatrix(&result,i,j,R,C)
19             }
20             if result.count == R*C {
21                 break
22             }
23             currentLevel += 1
24             for _ in 1 ... currentLevel {
25                 j -= 1
26                 self.appendResultIfInMatrix(&result,i,j,R,C)
27             }
28             if result.count == R*C {
29                 break
30             }
31             for _ in 1 ... currentLevel {
32                 i -= 1
33                 self.appendResultIfInMatrix(&result,i,j,R,C)
34             }
35             if result.count == R*C {
36                 break
37             }
38             currentLevel += 1
39         }
40         return result
41     }
42     
43     func appendResultIfInMatrix(_ result: inout [[Int]], _ i:Int, _ j:Int, _ R:Int, _ C: Int) {
44         if self.inMatrix(i,j,R,C) {
45             result.append([i,j])
46         }
47     }
48     
49     func inMatrix(_ i:Int, _ j:Int, _ R:Int, _ C: Int) -> Bool {
50         if i >= 0 && i < R && j >= 0 && j < C {
51             return true
52         } else {
53             return false
54         }
55     }
56 }

140ms

 1 class Solution {
 2     //first: true for row, false for col; second: true forward, false backward
 3     private let op = [(true,1),(false,1),(true,-1),(false,-1)] 
 4     private var ans = [[Int]]()
 5     private var current = [Int]()
 6     var visited = 1
 7     
 8     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {
 9         var step = 1; var turningCount = 0
10         self.visited = 1
11         self.current = [r0,c0]
12         self.ans = [current]
13         let total = R*C
14         
15         while (visited != total) {
16             let turningSignal = op[turningCount%4]
17             move(turningSignal.0, turningSignal.1, step, R, C)
18             turningCount += 1
19             if (turningCount&1 == 0) {
20                 step += 1
21             }
22         }
23         
24         return ans
25     }
26     
27     private func move(_ direction: Bool, _ forward: Int, _ step: Int, _ R: Int, _ C: Int) {
28         for _ in 0..<step {
29             if direction {
30                 current[1] += forward
31             } else {
32                 current[0] += forward
33             }
34             let row = current[0]; let col = current[1]
35             if (row < R && row >= 0 && col < C && col >= 0) {
36                 ans.append(current)
37                 visited += 1
38             }
39         }
40     }
41 }

152ms

 1 class Solution {
 2     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {
 3         var count = 1
 4         var right = 0
 5         var down = 0
 6         var left = 0
 7         var up = 0
 8         var currentRow = r0
 9         var currentCol = c0
10         var pointsCount = 0
11         var visitedPoints:[[Int]] = []
12 
13         while pointsCount < R*C {
14             if currentRow >= 0 && currentRow < R && currentCol >= 0 && currentCol < C {
15                 pointsCount = pointsCount + 1
16                 visitedPoints.append([currentRow, currentCol])
17             }
18 
19             if right < count {
20                 currentCol  = currentCol + 1
21                 right = right + 1
22             }else if down < right {
23                 currentRow = currentRow + 1
24                 down = down + 1
25             }else if left < right + 1{
26                 currentCol  = currentCol - 1
27                 left = left + 1
28             }else if up < right + 1 {
29                 currentRow = currentRow - 1
30                 up = up + 1
31             }
32 
33             if up == right + 1 {
34                 count = count + 2
35                 right = 0
36                 down = 0
37                 left = 0
38                 up = 0
39             }
40         }
41         return visitedPoints
42     }
43 }

204ms

 1 class Solution {
 2     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {        
 3         var r = r0,c = c0,n = 1,direction = 1,count = 1
 4         var arr : Array<Array<Int>> = [[]]
 5         arr.removeAll()
 6         arr.append([r,c])
 7         while arr.count < R * C {
 8             
 9             switch direction%4 {//上右下左
10             case 0: r-=1
11             case 1: c+=1
12             case 2: r+=1
13             case 3: c-=1
14             default: break
15             }
16             if (r >= 0 && r < R && c >= 0 && c < C) {
17                 arr.append([r,c])
18             }
19             
20             if count < n {
21                 count += 1
22             } else {
23             if direction % 4 == 0 || direction % 4 == 2 {
24                 n+=1
25             }
26             count = 1
27        direction += 1
28             }
29         }
30         return arr        
31     }
32 }

212ms

 1 class Solution {
 2     func spiralMatrixIII(_ R: Int, _ C: Int, _ r0: Int, _ c0: Int) -> [[Int]] {
 3     var arr: [[Int]] = [[r0, c0]]
 4     
 5     // 0 →  1 ↓  2 ←  3 ↑
 6     var dir = 0
 7     var dis = 1, cis = 1
 8     var r = r0, c = c0
 9     let max = R * C
10     
11     while true {
12         if arr.count == max { break }
13         let n = next(dir, r, c)
14         r = n.0
15         c = n.1
16         
17         cis -= 1
18         if cis == 0 {
19             dir += 1
20             if dir % 2 == 0 {
21                 dis += 1
22             }
23             cis = dis
24         }
25         
26         if outRect(R, C, r, c: c) { continue }
27         arr.append([r, c])
28     }
29     
30     return arr
31 }
32 
33 func outRect(_ R: Int, _ C: Int, _ r: Int, c: Int) -> Bool {
34     return (r < 0 || r >= R) || (c < 0 || c >= C)
35 }
36 
37 func next(_ dir: Int, _ r: Int, _ c: Int) -> (Int, Int) {
38     let d = dir % 4
39     switch d {
40     case 0: return (r, c+1)
41     case 1: return (r+1, c)
42     case 2: return (r, c-1)
43     case 3: return (r-1, c)
44     default:return (r, c)
45     }
46   }
47 }