一【題目類別】

• 矩陣

二【題目難度】

• 簡單

三【題目編號】

• 766.托普利茨矩陣

四【題目描述】

• 給你一個 m x n 的矩陣 matrix 。如果這個矩陣是托普利茨矩陣，返回 true ；否則，返回 false 。
• 如果矩陣上每一條由左上到右下的對角線上的元素都相同，那么這個矩陣是 托普利茨矩陣 。

五【題目示例】

• 示例 1：

  • 
  • 輸入：matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
  • 輸出：true
  • 解釋：
    • 在上述矩陣中, 其對角線為:
    • “[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”。
    • 各條對角線上的所有元素均相同, 因此答案是 True 。

• 示例 2：

  • 
  • 輸入：matrix = [[1,2],[2,2]]
  • 輸出：false
  • 解釋：
    • 對角線 “[1, 2]” 上的元素不同。

六【題目提示】

• $m==matrix.length$
• $n==matrix[i].length$
• $1<=m,n<=20$
• $0<=matrix[i][j]<=99$

七【題目進階】

• 如果矩陣存儲在磁盤上，并且內(nèi)存有限，以至于一次最多只能將矩陣的一行加載到內(nèi)存中，該怎么辦？
• 如果矩陣太大，以至于一次只能將不完整的一行加載到內(nèi)存中，該怎么辦？

八【解題思路】

• 本題的思路比較簡單，我們無需逐個對角線去比較，只需要比較前一行除了最后一個元素和后一行除了第一個元素后剩余的元素是否想等
• 因為如果是托普利茨矩陣的話，下一行一定是上一行向右移動一個位置之后形成的矩陣，所以上一行的最后一個元素和下一行的第一個元素，可以無須判斷，因為上一行的最后一個元素被移出了，下一行的第一個元素單獨成為對角線
• 最后返回結(jié)果即可

九【時間頻度】

• 時間復雜度：$O(m?n)$，$m、n$分別為傳入數(shù)組的行數(shù)和列數(shù)
• 空間復雜度：$O(1)$

十【代碼實現(xiàn)】

1. Java語言版

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0;i < m - 1;i++){
            for(int j = 0;j < n - 1;j++){
                if(matrix[i][j] != matrix[i+1][j+1]){
                    return false;
                }
            }
        }
        return true;
    }
}

2. C語言版

bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize)
{
    int m = matrixSize;
    int n = matrixColSize[0];
    for(int i = 0;i < m - 1;i++)
    {
        for(int j = 0;j < n - 1;j++)
        {
            if(matrix[i][j] != matrix[i+1][j+1])
            {
                return false;
            }
        }
    }
    return true;
}

3. Python語言版

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m - 1):
            for j in range(n - 1):
                if matrix[i][j] != matrix[i+1][j+1]:
                    return False
        return True

4. C++語言版

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

十一【提交結(jié)果】

1. Java語言版
   

2. C語言版
   

3. Python語言版
   

4. C++語言版
   文章來源地址http://www.zghlxwxcb.cn/news/detail-619602.html

到了這里，關(guān)于【LeetCode每日一題】——766.托普利茨矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！