leetcode/Python/spiral-matrix.py at master · OnlyChristmas/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
'''

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

'''


class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # Approach one  用498题思路解答，代码可读性强，但效率有待提升
#         if matrix == [] : return []
#         row , col = len(matrix) , len(matrix[0])
#         i = j = upper_bound = left_bound = 0
#         ans = []
#         count = row * col
#         down = up = left = False
#         right = True
#         while count:
#             count -= 1
#             ans.append(matrix[i][j])
#             if up:
#                 if i == upper_bound:
#                     up, right = False, True
#                     left_bound += 1
#                     j += 1
#                     continue
#                 else:
#                     i -= 1
#             if left:
#                 if j == left_bound:
#                     left, up = False, True
#                     row -= 1
#                     i -= 1
#                     continue
#                 else:
#                     j -= 1
#             if down:
#                 if i == row -1:
#                     down, left = False, True
#                     col -= 1
#                     j -= 1
#                     continue
#                 else:
#                     i += 1
#             if right:
#                 if j == col -1:
#                     right, down = False, True
#                     upper_bound += 1
#                     i += 1
#                     continue
#                 else:
#                     j += 1
#         return ans


        # # Approach two   简化代码
        # if matrix == []: return []
        # ans=[]
        # row , col = len(matrix) , len(matrix[0])
        # # flag = row * [ col * [1]]   # 这种初始化方式为什么有毒？
        # flag =  [[1 for i in range(col)] for i in range(row)]   # 保证每个元素只被添加一次
        # direction = 0  # 代表四个方向
        # i = j = pre_i = pre_j = 0
        # count = row * col
        # while len(ans) < count:
        #     if i >= row or j >= col or i < 0 or j < 0 or flag[i][j]==0:
        #         direction = (direction+1) % 4    # 控制转向
        #         i, j = pre_i, pre_j
        #         if direction==0:
        #             j=j+1
        #         elif direction==1:
        #             i=i+1
        #         elif direction==2:
        #             j=j-1
        #         elif direction==3:
        #             i=i-1
        #     elif flag[i][j] == 1:
        #         flag[i][j] = 0
        #         ans.append(matrix[i][j])
        #         pre_i, pre_j = i, j
        #         if direction==0:
        #             j=j+1
        #         elif direction==1:
        #             i=i+1
        #         elif direction==2:
        #             j=j-1
        #         elif direction==3:
        #             i=i-1
        # return ans


        # Approach three   进一步简化代码，丧失易读性
        if not matrix:return []
        row, col = len(matrix), len(matrix[0])
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        x, y = 0, -1
        boundary = [col - 1, row - 1, 0, 0]
        ans = []
        k = 0
        count = row * col
        while count:
            count -= 1
            x += dx[k]
            y += dy[k]
            ans.append(matrix[x][y])
            if k % 2 == 0 and y == boundary[k] or k % 2 == 1 and x == boundary[k]:
                o = (k - 1) % 4
                boundary[o] += 1 if o >= 2 else -1
                k = (k + 1) % 4
        return ans