文章目录
  1. 1. 题意描述
  2. 2. 题意翻译
  3. 3. 代码参考

题意描述

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:

1、matrix will be a 2D array of integers.

2、matrix will have a number of rows and columns in range [1, 20].

3、matrix[i][j] will be integers in range [0, 99].

题意翻译

这道题是解决一个叫做托普利茨矩阵的问题。Toeplitz矩阵(diagonal-constant matrix),指矩阵中每条自左上至右下的斜线上的元素相同。
这道题解法还是很简单的,可以通过直接遍历整个数组就可以完成,时间复杂度为 O(n2),空间复杂度为 O(1),然后 leetcode官方给了另一种非最优的解决方法,这种方法通过利用矩阵的特点来实现,就是斜线上的元素的共同特点是横纵坐标的差的绝对值是相同的,这样的话我们就可以利用hash的方法来实现。

代码参考

第一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
// 判断对角线上的元素是否相等
public boolean isToeplitzMatrix(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
for(int i=0 ; i<row-1 ; i++){
for(int j=0 ; j<col-1 ; j++){
if(matrix[i][j] != matrix[i+1][j+1]){
return false;
}
}
}
return true;
}
}

第二种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
HashMap<Integer , Integer> map = new HashMap();
for(int i=0 ; i<matrix.length ; i++){
for(int j=0 ; j<matrix[0].length ; j++){
if(!map.containsKey(j-i)){
map.put(j-i , matrix[i][j]);
}else{
if(map.get(j-i) != matrix[i][j]){
return false;
}
}
}
}
return true;
}
}

文章目录
  1. 1. 题意描述
  2. 2. 题意翻译
  3. 3. 代码参考