はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
- 配列内のインデックスの扱いに注意
この記事で得られること
- 多重配列の扱い
- 配列内のインデックス操作の練習
詳細
問題
原文
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:
123456 Input: mat = [[1,2,3],[4,5,6],[7,8,9]]Output: 25Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25Notice that element mat[1][1] = 5 is counted only once.Example 2:
12345 Input: mat = [[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]Output: 8Example 3:
12 Input: mat = [[5]]Output: 5
Constraints:
n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100
内容(和訳)
行列matが与えられるので、対角線上の要素の合計を返してください。
※正しくない可能性があります。
解答
解答1:Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Solution: def diagonalSum(self, mat: List[List[int]]) -> int: #左上から右下いかけての対角線の合計を持つ変数 primary_sum = 0 #右上から左下にかけての対角線の合計を持つ変数 secondary_sum = 0 #列(内側の要素)のインデックス primary_column = secondary_column = 0 #行列の各行を走査 for i in range(len(mat)): #右端から左端へ向けてインデックスを動かす secondary_column -= 1 #2つの対角線に値を加える primary_sum += mat[i][secondary_column] secondary_sum += mat[i][primary_column] #左端から右端へ向けてインデックスを動かす primary_column += 1 #2つの対角線を合計する answer = primary_sum + secondary_sum #行列中央の要素が2回加算されるのは、行と列が奇数かつ同じ数の場合 if len(mat)%2==1 and len(mat)==len(mat[0]): # answer -= mat[len(mat)//2][len(mat)//2] #解答を返す return answer |
➀左上から右下と、②右上から左下の2つの対角線の合計を求めます。
各行をfor文で一巡しますが、各ループで列の位置を示すインデックスは、
➀の対角線は左から右に、②の対角線は右から左に動くように操作しています。
行列の数が奇数で、行数と列数が同じとき、行列の中央の要素は2つの対角線でそれぞれ加算されているので、2つの対角線を合計値から引いています。
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
疑問が解決した方は他の問題もどうぞ
前:1672. Richest Customer Wealth
コメント