leetcode回顾——ToeplitzMatrix

LeetCode

题目

“””
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512

In the above grid, the diagonals are “[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”, and in each diagonal all elements are the same, so the answer is True.
Example 2:

Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal “[1, 2]” has different elements.

Note:

matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].
“””

思路

这道题其实就是一个搜索问题，怎么去搜索？搜索的边界如何确定？这就是解决问题的关键。比如说题目的例子

1
2
3
[[1,2,3,4],
 [5,1,2,3],
 [9,5,1,2]]

实际上就是对角线去搜索元素是否相同就可以。一种做法是从第一行开始对角元素遍历，将遍历过的元素全部置为-1，表示已经访问过的元素，当第一行遍历完成后转向第二行开始遍历，同时注意遍历的边界——一个矩阵的行列；遍历过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
第一轮 (''号代表第一轮访问)
[['1',2,3,4],      [['1','2',3,4],      [['1','2','3',4],       [['1','2','3','4'],
 [5,'1',2,3],  =>   [5,'1','2',3],  =>   [5,'1','2','3'],        [5,'1','2','3'],
 [9,5,'1',2]]       [9,5,'1','2']]       [9,5,'1','2']]          [9,5,'1','2']]

 第二轮(‘’号代表第二轮访问)
[['1','2','3','4'],      [['1','2','3','4'],           [['1','2','3','4'],  
 [5,'’1‘','2','3'],  =>   ['5','’1‘','’2‘','3'],   =>   ['5','’1‘','’2‘','‘3’'],
 [9,5,'1','2']]           [9,'5','1','2']]              [9,'5','1','2']]

 第三轮
 [['1','2','3','4'],             [['1','2','3','4'],                [['1','2','3','4'],
  ['5','‘1’','‘2’','‘3’'],   =>   ['5','‘1’','‘2’','‘3’'],   =>      ['5','‘1’','‘2’','‘3’'],
  ['9','‘5’','1','2']]            ['9','‘5’','‘1’','2']]             ['9','‘5’','‘1’','‘2’']]

这种做法是最普通的，但也是最耗时的，因为在第一行进行第一轮的对角元素遍历后，再从第二行开始对角元素遍历时，实际上会遍历在刚刚第一轮就已经遍历过的元素，做了许多无用功。因此，重新观察矩阵之后，可以知道，只需要从第一行和第一列进行对角元素遍历就可以解决了，这就是第二种方法，相比于第一种方法，避免做了无用的访问。

解题代码

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
class Solution(object):
    def isToeplitzMatrix(self, matrix):
        """
        第一种解决方法
        :type matrix: List[List[int]]
        :rtype: bool
        """
        length = len(matrix[0])        
        width = len(matrix)
        for i in range(width):
            for j in range(length):
                if (i == 0 and j == length - 1) or (i == width - 1 and j == 0):
                    break
                if matrix[i][j] == -1:
                    continue
                temp_i = i + 1                
                for k in range(j + 1, length):
                    if temp_i <= width - 1:
                        if matrix[i][j] == matrix[temp_i][k]:
                            matrix[temp_i][k] = -1
                        else:
                            return False
                    temp_i += 1
                matrix[i][j] = -1
        return True
    
    def fun(self, matrix):
        """
        第二种解决方法
        :type matrix: List[List[int]]
        :rtype: bool
        """
        length = len(matrix[0])
        width = len(matrix)
        for i in range(length):
            if i == length: break
            j = 1
            for k in range(i + 1, length):
                if j == width: break
                if matrix[0][i] == matrix[j][k]: matrix[j][k] = -1
                else:
                    return False
                j += 1
            matrix[0][i] = -1
        for i in range(1, width):
            if i == width: break
            j = i + 1
            for k in range(1, length):
                if j == width: break
                if matrix[i][0] == matrix[j][k]: matrix[j][k] = -1
                else:
                    return False
                j += 1
            matrix[i][0] = -1
        return True


if __name__ == '__main__':
    s = Solution()
    print s.isToeplitzMatrix([[11,74,0,93],[40,11,74,7]])