【LeetCode】766. Toeplitz Matrix 解题报告

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

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:

In the above grid, the diagonals are:

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

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].

题目大意

如果一个矩阵中每条从左上到右下的线上的数值都相等，那么满足题目条件，否则不满足。求判断输入的每个矩阵是否满足。

解题方法

方法一：两两比较

这个题目如果按照题目意思解答，求出矩阵的所有对角线，情况很复杂。所以使用的是直接两两进行比较的方式。

判断每行元素的每个元素和其右下角的元素是否相等，如果不等就返回False；全部相等返回True.

class Solution(object):

    def isToeplitzMatrix(self, matrix):

        """

        :type matrix: List[List[int]]

        :rtype: bool

        """

        for row in xrange(len(matrix) - 1):

        	for col in xrange(len(matrix[0]) - 1):

        		if matrix[row][col] != matrix[row+1][col+1]:

        			return False

        return True

方法二：切片相等

只要观察到第二行的后面部分和第一行的前面部分相等即可。使用切片和一个for循环就能解决问题。

class Solution(object):

    def isToeplitzMatrix(self, matrix):

        """

        :type matrix: List[List[int]]

        :rtype: bool

        """

        return all(matrix[row+1][1:] == matrix[row][:-1] for row in range(len(matrix)-1))

方法三：判断每条对角线

二刷的时候没有想到更简单的方法，所以直接使用了题目说的，判断每条对角线的方式。把第一行和第一列作为起始，然后判断向右下的每条线上的元素是否和它相等。

class Solution:

    def isToeplitzMatrix(self, matrix):

        """

        :type matrix: List[List[int]]

        :rtype: bool

        """

        M, N = len(matrix), len(matrix[0])

        for row in range(M):

            first = matrix[row][0]

            j = 0

            for i in range(row, M):

                if 0 <= j < N:

                    if matrix[i][j] != first:

                        return False

                j += 1

        for col in range(N):

            first = matrix[0][col]

            i = 0

            for j in range(col, N):

                if 0 <= i < M:

                    if matrix[i][j] != first:

                        return False

                i += 1

        return True

日期

2018 年 1 月 22 日
2018 年 11 月 8 日 —— 项目进展缓慢

巴特西