はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
-
- スライディングウインドウ
詳細
問題
原文
You are given an integer array
numsconsisting ofnelements, and an integerk.Find a contiguous subarray whose length is equal to
kthat has the maximum average value and return this value. Any answer with a calculation error less than10-5will be accepted.
Example 1:
Example 2:
Constraints:
n == nums.length1 <= k <= n <= 105-104 <= nums[i] <= 104
内容(和訳)
整数の配列nums（長さn）と整数kが与えられます。
長さがkである連続した部分配列を見つけて、その平均値が最大となる部分配列の値を返します。計算誤差が10^-5以下の答えも受け入れられます。
※chatGPTによる翻訳
解答
解答1：Python, スライディングウインドウ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: #平均値の最大値を保持する変数。numsの要素は負数もあるので、負の無限大で初期化 max_avg = float("-inf") #ウインドウの合計値を保持する変数 current_sum = 0 #ウインドウの左側のインデックス left = 0 #numsを一巡して走査。ループ変数rightはウインドウの右側のインデックス for right in range(len(nums)): #ウインドウの合計値にright番目の要素を追加 current_sum += nums[right] #ウインドウ内の要素数がk個になった場合 if (right-left) == k-1: #max_avgを更新 max_avg = max(max_avg, current_sum/k) #ウインドウの左端の要素の値を合計値から引く current_sum -= nums[left] #左側のインデックスを1つ進む left += 1 #戻り値を返す return max_avg |
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
疑問が解決した方は他の問題もどうぞ
次：1732. Find the Highest Altitude
コメント