Problem:
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[i][j], 下一元素为matrix[i+1][j+1]。
代码如下:
public boolean isToeplitzMatrix(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
for (int j = 0; j < m; ++j) {
int i = 0;
while (i + 1 < n && j + 1 < m) {
if (matrix[i + 1][j + 1] != matrix[i][j]) return false;
i ++;
j ++;
}
}
for (int i = 0; i < n; ++i) {
int j = 0;
while (i + 1 < n && j + 1 < m) {
if (matrix[i + 1][j + 1] != matrix[i][j]) return false;
i ++;
j ++;
}
}
return true;
}
当然你可以直接遍历,只要判断每个元素所在对角线的下一个元素是否与当前元素相等即可。
Java版本:
public boolean isToeplitzMatrix(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m - 1; ++j) {
if (matrix[i][j] != matrix[i + 1][j + 1]) return false;
}
}
return true;
}
Python版本:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
n = len(matrix)
m = len(matrix[0])
for i in range(0, n - 1):
for j in range(0, m - 1):
if matrix[i][j] != matrix[i + 1][j + 1]: return False
return True