概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。
その対策としてLeetCodeなるサイトで対策を行うようです。
※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。
未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。
問題
2389. Longest Subsequence With Limited Sum
numsからの数値の和がqueries[i]を超えないように、含めることができる部分配列の要素数を返す問題。
Example 1:
Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
説明：
・部分配列[2,1]は和が3以下。このような部分配列の最大サイズは2であることが証明できるので、answer[0] = 2である。
・部分配列[4,5,1]は和が10以下である。3がそのような部分列の最大サイズであることが証明できるので，answer[1] = 3である．
・部分配列[4,5,2,1]は和が21以下である．4がそのような部分列の最大サイズであることは証明できるので，answer[2] = 4である。
Example 2:
Input: nums = [2,3,4,5], queries = [1]
Output: [0]
説明:
空の部分列は，和が1以下である部分文字列なので，answer[0] = 0である。
制約条件:
n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106
解法
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
answer = []
for query in queries:
count = 0
current_sum = 0
for num in nums:
if current_sum + num <= query:
current_sum += num
count += 1
else:
break
answer.append(count)
return answer
1. 数値リストのソートと結果リストの初期化
nums.sort()
answer = []
nums.sort()
リストを昇順にソート。
より多くの数値を合計に含めるために、常に最も小さい数値から順に含めるため。
answer = []
各要素に対する結果を格納するための空のリスト。
例
Input: nums = [4,5,2,1], queries = [3,10,21]
| 元のnums | ソート後のnums |
|---|---|
| [4,5,2,1] | [1,2,4,5] |
2.各要素に対する処理
for query in queries:
count = 0
current_sum = 0
for num in nums:
if current_sum + num <= query:
current_sum += num
count += 1
else:
break
answer.append(count)
return answer
count = 0
現在の要素に対して、含めることができる数値の数を追跡するカウンターを初期化する。
current_sum = 0
現在の要素に対して、これまでに含めた数値の合計を追跡する変数を初期化する。
if current_sum + num <= query
現在の合計current_sumにnumを加えてもqueryの値を超えない場合、current_sum += numでnumを合計に加える。
count += 1
含めることができる数値の数を1増やす。
内側のループが終了すると、現在のquery[i]に対して含めることができる数値の最大数がcountに格納されているため、answer.append(count)でcountをanswerリストに追加する。
すべての要素に対する処理が完了すると、answerリストには各要素に対する結果が順番に格納されているので最後に、answerリストを返して終了する。
例
nums = [1,2,4,5], queries = [3,10,21]
query = 3
初期化： current_sum = 0, count = 0
| 処理中のnumsの要素(num) | current_sum | count |
|---|---|---|
| 1 | (0 + 1 <= 3 True) | 1 |
| 2 | (1 + 2 <= 3 True) | 3 |
| 4 | (3 + 4 <= 3 False) | (ループ終了) |
結果
| クエリ | 最終的なcount | answerリストの更新 |
|---|---|---|
| 3 | 2 | [2] |
query = 10
初期化： current_sum = 0, count = 0
| 処理中のnumsの要素(num) | current_sum | count |
|---|---|---|
| 1 | (0 + 1 <= 10 True) | 1 |
| 2 | (1 + 2 <= 10 True) | 3 |
| 4 | (3 + 4 <= 10 True) | 7 |
| 5 | (7 + 5 <= 10 False) | (ループ終了) |
結果
| クエリ | 最終的なcount | answerリストの更新 |
|---|---|---|
| 10 | 3 | [2, 3] |
query = 21
初期化： current_sum = 0, count = 0
| 処理中のnumsの要素(num) | current_sum | count |
|---|---|---|
| 1 | (0 + 1 <= 21 True) | 1 |
| 2 | (1 + 2 <= 21 True) | 3 |
| 4 | (3 + 4 <= 21 True) | 7 |
| 5 | (7 + 5 <= 21 True) | 12 |
結果
| クエリ | 最終的なcount | answerリストの更新 |
|---|---|---|
| 21 | 4 | [2, 3, 4] |
Discussion