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].Follow up:
Idea 1. Observe the example, found that all diagnals have the same k = rowIndex - columIndex, k in the range [M-1, -(N-1)]
Time complexity: O(M * N)
Space comlexity: O(1)
1 class Solution { 2 public boolean isToeplitzMatrix(int[][] matrix) { 3 int M = matrix.length; 4 int N = matrix[0].length; 5 6 for(int k = M-1; k >= -(N-1); --k) { 7 for(int i = M-2; i>= 0 && (i - k) >= 0; --i) { 8 if(i+1-k <= N-1 && matrix[i][i-k] != matrix[i+1][i+1-k]) { 9 return false; 10 } 11 } 12 } 13 14 return true; 15 } 16 }
Idea 1.a loop the matrix row by row, use hashMap to store the diffrence r - c, return false if one element has different r-c, much simpler logic
Time complexity: O(M*N)
Space complexity: O(M+N)
1 class Solution { 2 public boolean isToeplitzMatrix(int[][] matrix) { 3 int M = matrix.length; 4 int N = matrix[0].length; 5 6 Map<Integer, Integer> diagonals = new HashMap<>(); 7 for(int i = 0; i < M; ++i) { 8 for(int j = 0; j < N; ++j) { 9 diagonals.putIfAbsent(i-j, matrix[i][j]); 10 if(matrix[i][j] != diagonals.get(i-j)) { 11 return false; 12 } 13 } 14 } 15 16 return true; 17 18 } 19 }
Idea 1.c another observation would be make the code much easier, A[i][j] == A[i+1][j+1] on the same diagonal
Time complexity: O(M * N)
Space complexity: O(1)
1 class Solution { 2 public boolean isToeplitzMatrix(int[][] matrix) { 3 int M = matrix.length; 4 int N = matrix[0].length; 5 6 for(int i = 0; i < M; ++i) { 7 for(int j = 0; j < N; ++j) { 8 if(i+1 < M && j+1 < N && matrix[i][j] != matrix[i+1][j+1]) { 9 return false; 10 } 11 } 12 } 13 14 return true; 15 } 16 }
Follow up 1:
Idea 1. Store the previous row in a queue from right to left, store the element in the queue if it has neighbour on the next row [i+1][j+1], compare buffer[j] = matrix[i+1][j+1]
Time complexity: O(M*N)
Space complexity: O(N)
1 class Solution { 2 public boolean isToeplitzMatrix(int[][] matrix) { 3 int M = matrix.length; 4 int N = matrix[0].length; 5 6 Deque<Integer> buffer = new ArrayDeque<>(); 7 for(int j = N-2; j >= 0; --j) { 8 buffer.addLast(matrix[0][j]); 9 } 10 11 12 for(int i = 1; i < M; ++i) { 13 for(int j = N-1; j >= 1; --j) { 14 int prev = buffer.removeFirst(); 15 if(prev != matrix[i][j]) { 16 return false; 17 } 18 if(j <= N-2) { 19 buffer.addLast(matrix[i][j]); 20 } 21 } 22 buffer.addLast(matrix[i][0]); 23 } 24 return true; 25 } 26 }
Follow up 2: split the row into mulitple partial row, and do row comparison like follow up 1 for a block with partial matrix only, then continue for the next block unitl all the blocks are done.
原文：https://www.cnblogs.com/taste-it-own-it-love-it/p/10836253.html