Title
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].
题目大意：判断一个矩阵是否是左上到右下那条线撒谎给你的点的值都是一样的
Solution
自己的，ac，遍历所有对角线。
//cpp:
class Solution {
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = i + 1,k = 1; j < m&&k < n; j++, k++) {
if (matrix[k][j] != matrix[0][i]) {
return false;
}
}
}
for (int i = 1; i < n; i++) {
for (int j = i + 1,k=1; j < n&&k<m; j++,k++) {
if (matrix[j][k] != matrix[i][0]) {
return false;
}
}
}
return true;
}
};
Approach #1: Group by Category [Accepted]
Intuition and Algorithm
We ask what feature makes two coordinates (r1, c1) and (r2, c2) belong to the same diagonal?
It turns out two coordinates are on the same diagonal if and only if r1 - c1 == r2 - c2.
This leads to the following idea: remember the value of that diagonal as groups[r-c]. If we see a mismatch, the matrix is not Toeplitz; otherwise it is.
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
Map<Integer, Integer> groups = new HashMap();
for (int r = 0; r < matrix.length; ++r) {
for (int c = 0; c < matrix[0].length; ++c) {
if (!groups.containsKey(r-c))
groups.put(r-c, matrix[r][c]);
else if (groups.get(r-c) != matrix[r][c])
return False;
}
}
return True;
}
}
Approach #2: Compare With Top-Left Neighbor [Accepted]
Intuition and Algorithm
For each diagonal with elements in order a1,a2,a3,…,ak, we can check a1=a2,a2=a3,…,ak−1=ak. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.
Every element belongs to some diagonal, and it’s previous element (if it exists) is it’s top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c].
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
for (int r = 0; r < matrix.length; ++r)
for (int c = 0; c < matrix[0].length; ++c)
if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
return false;
return true;
}
}