Skip to content

LeetCode: 1572-Matrix Diagonal Sum 解題紀錄

Last Updated on 2023-05-08 by Clay

題目

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100

我們會得到一個矩陣 mat,我們要做的就是把該矩陣兩條對角線上所有的元素相加,並返回最終的總值。


解題思路

在把所有的對角線元素加總時,可以一行行地進行計算。不過由於需要考慮兩邊的對角線,所以需要同時取左右兩邊的索引;剛好這兩個索引是對稱的,所以只要從第一個索引就能計算出第二個索引的相對位置。

最後,如果該矩陣 mat 的尺寸是偶數,那麼矩陣的中心點會被重複計算,別忘了最後再減去該值一次。


C++ 範例程式碼

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        // Init
        int count = 0;
        int _size = mat.size() - 1;

        // Couting
        for (int i=0; i<=_size; ++i) {
            count += mat[i][i] + mat[_size-i][i];
        }

        // If mattrix size is odd number
        if (_size % 2 == 0) {
            count -= mat[_size/2][_size/2];
        }

        return count;
    }
};



Python 範例程式碼

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        # Init
        count = 0
        _size = len(mat) - 1

        # Couting
        for i in range(_size+1):
            count += mat[i][i] + mat[_size-i][i]

        # If mattrix size is odd number
        if _size % 2 == 0:
            count -= mat[_size//2][_size//2]

        return count

References


Read More

Leave a Reply取消回覆

Exit mobile version