LWC 68: 766. Toeplitz Matrix
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 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].
思路： 对角线遍历，注意对角线的性质：当前元素为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本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018年01月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
