【LeetCode】 766. Toeplitz Matrix

Description

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.

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 x N的矩陣，回傳該矩陣是否為常對角。

注意：

1. matrix 是二維的整數陣列.
2. matrix 的直排和橫列個數範圍是 [1, 20].
3. matrix[i][j] 是一個整數，範圍是 [0, 99].

進階：

1. 如果矩陣儲存於硬碟中，且記憶體受到限制，你一次最多只能讀出矩陣中的一行到記憶體中，該怎麼辦？
2. 如果矩陣很大，一次只能讀出部分的資料到記憶體中，該怎麼辦？

Example:

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.

Solution

• 不需要受到對角線影響而認為一次要處理一條對角線。
• 我們只需思考，是不是每個元素都和左上或右下的比較是否相等即可？
• 進階題沒想到怎麼做第一題，第二題倒是沒問題(我們一次只拿兩個元素出來比較)。

Code

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        for(int i = 1; i < matrix.size(); i++)
            for(int j = 1; j < matrix[0].size(); j++)
                if(matrix[i][j] != matrix[i - 1][j - 1])
                    return false;
        return true;
    }
};

tags: LeetCode C++