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:

  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].

Follow up:
  1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
  2. What if the matrix is so large that you can only load up a partial row into the memory at once?

題意：

給你一個M×N的矩陣matrix，讓判斷這個矩陣是否為Toeplitz矩陣（托普利茲矩陣），所謂的托普利茲矩陣就是說：除了第一行和第一列外其他元素都與左上角的元素相等（我的程序就是用這個思想實現的）。如果是Toeplitz矩陣就返回true，否則返回false。

以下為代碼：

class Solution {
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
int rows=matrix.size();
int cols=matrix[0].size();
if(rows+cols<=2)
return true;
// if(rows<2 || cols<2) // Note中都說是2D的了，沒想到LeetCode上還有一個元素來測試的，最後改成上面的if判斷
// return false;
bool res=true;
for(int r=0;r<rows-1;r++)
{
for(int c=0;c<cols-1;c++)
{
if(matrix[r][c]!=matrix[r+1][c+1])
res=false;
}
}
return res;

}
};

對於題中提到的Follow up，我想到的是將外層循環換成每次讀取一行內容來判斷，不知道矩陣大的話時間效率怎麼樣。

推薦閱讀：

相关文章