カバーするコンセプトは
- LinkedList
- Stack
- Heap, PriorityQueue
- HashMap
- Graph, BFS, DFS
- Tree, BT, BST
- Sort
- Dynamic Programming
- Binary search
- Recursion
- Sliding window
- Greedy + Backtracking
LinkedList
Greedy + Backtracking
Permutations
問題リンク: 46. Permutations
この問題は**バックトラッキング（backtracking）**というアルゴリズムが最も適しています
バックトラッキングとは？
「試行」と「戻る」を繰り返しながら、解の候補を探索する手法です。途中で解にならないと分かった場合は探索を打ち切り（枝刈り）、効率的に解を求めます
アルゴリズムの流れ
コード
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(path, used):
# パスが完成したら結果に追加
if len(path) == len(used):
result.append(path.copy()) # リストはポインタとして渡されるから
return
for i in range(len(nums)):
if used[i]:
continue
# 選択
used[i] = True
path.append(nums[i])
# 探索：次の要素を選ぶ
backtrack(path, used)
# 戻る：選択を取り消す(backtrack)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(path, used):
# パスが完成したら結果に追加
if len(path) == len(used):
result.append(path.copy()) # リストはポインタとして渡されるから
return
for i in range(len(nums)):
if used[i]:
continue
# 選択
used[i] = True
path.append(nums[i])
# 探索：次の要素を選ぶ
backtrack(path, used)
# 戻る：選択を取り消す(backtrack)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
計算量
時間計算量: \(O(n! × n)\) 順列の数が \(n!\) 通り 各順列をコピーするのに \(O(n)\) 時間
空間計算量: O(n) 再帰のスタック深さが最大 \(n\) used配列やpathのサイズも \(O(n)\)
ポイント
- 小さな入力から試す: [1] → [1,2] → [1,2,3] と順にデバッグ
- 再帰の呼び出しを図に描くと理解しやすい
- 「選ぶ→進む→戻す」の3ステップを必ず守る。関数呼び出しがスタックになっていることと、実装のイメージを結びつける
Subsets
問題リンク: 78. Subsets
考え方
図を書いてみると
- 探索範囲の値よりも後の要素を
numsから見れば良さそう pop()による戻る操作は必要なさそうで、進むだけで良さそう- 木構造の探索
であることがわかる
コード
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(start_idx, path):
result.append(path.copy()) # ポインタではなくオブジェクトを渡すため
for i in range(start_idx, len(nums)):
backtrack(i + 1, path + [nums[i]])
backtrack(0, [])
return result
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(start_idx, path):
result.append(path.copy()) # ポインタではなくオブジェクトを渡すため
for i in range(start_idx, len(nums)):
backtrack(i + 1, path + [nums[i]])
backtrack(0, [])
return result
解けるようになるポイント
- 最初は図を描いて理解する
- 木構造の探索と回帰での実装を手に馴染ませる
Combination Sum
問題リンク: 39. Combination Sum
解き方
図を描いてみると78. Subsets同様に根と葉のセットを再帰的に探索することで結果が得られそうと考える
コード
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
def backtrace(start_idx: int, current_nums: List[int], current_sum: int):
if current_sum == target:
result.append(current_nums)
return
elif current_sum > target:
return
for i in range(start_idx, len(candidates)):
backtrace(
i, current_nums + [candidates[i]], current_sum + candidates[i]
)
backtrace(0, [], 0)
return result
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
def backtrace(start_idx: int, current_nums: List[int], current_sum: int):
if current_sum == target:
result.append(current_nums)
return
elif current_sum > target:
return
for i in range(start_idx, len(candidates)):
backtrace(
i, current_nums + [candidates[i]], current_sum + candidates[i]
)
backtrace(0, [], 0)
return result
解くためのポイント
- 図を描いて直感を得る
for文の外でreturnする。それ以上枝を伸ばす意味のない状況になったら早期に抜ける[2,2,3], [3,2,2]などの重複を避けるために自身以降のみの探索をする(start_idxの部分)
ノート
current_nums + [candidates[i]]では毎回コピーが発生するので、pop()で毎回掃除をしつつ一つのオブジェクトを保持しながら探索するやり方もできるように
Generate Parentheses
Binary Search
1011. Capacity To Ship Packages Within D Days
考え方
まず、二分探索でcapacityを探索する問題だと気づいた。 これはcapacityにある値以上では常に解けるが、その値未満では常に解けないという単調性があることを感じたから。 その後、この直感が正しいかを簡単にいくつかのケースで脳内で考えおそらく合っていると考えた。 次に、二分探索内で考えるべき問題の"そのcapacity で days 以内に解けるか"をどのように判別するかを考える必要がある。 これに関しては貪欲法が良いだろう。weightsから任意の数の組み合わせに分けて、そのどれの合計もcapacityを超えないといけないので、これを確かめるために全探索を考えるかもしれないが、今回は"並んでいる順番に処理する"という制約があるので、少なくとも全探索よりはいい方法があるだろうと考える。 結果的にはできるだけ前から詰めていって、その結果がdays以下になる貪欲法でいいと判断した。 ただ、貪欲法よりもっといい組み合わせが存在しないという証明は正直出来ない（TODO）
コード
はじめに書いたコードはtime exceededになってしまった。
from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
min_capacity = max(weights)
max_capacity = sum(weights)
def canCompleteWithin(weights: List[int], days: int, capacity: int) -> bool:
required_days = 1
current_weight = 0
for w in weights:
if current_weight >= capacity:
required_days += 1
current_weight = w
continue
current_weight += w
return required_days <= days
left = min_capacity
right = max_capacity
while left < right:
mid = (left + right + 1) // 2
if canCompleteWithin(weights, days, mid):
right = mid # midで運べるならmid自身を残す
else:
left = mid + 1 # midで運べないならそれよりは大きい必要がある
return left
from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
min_capacity = max(weights)
max_capacity = sum(weights)
def canCompleteWithin(weights: List[int], days: int, capacity: int) -> bool:
required_days = 1
current_weight = 0
for w in weights:
if current_weight >= capacity:
required_days += 1
current_weight = w
continue
current_weight += w
return required_days <= days
left = min_capacity
right = max_capacity
while left < right:
mid = (left + right + 1) // 2
if canCompleteWithin(weights, days, mid):
right = mid # midで運べるならmid自身を残す
else:
left = mid + 1 # midで運べないならそれよりは大きい必要がある
return left
問題点として、このコードは
canCompleteWithin()内で指定されたdaysを超えてしまっても一応最後の荷物まで計算してしまっている点canCompleteWithin()の関数呼び出しのオーバーヘッドがある
という点が考えられた。正直、二つ目はあまり本質的ではない気がする。
これらの点を改善すると、間に合うようになる。
from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
left = max(weights)
right = sum(weights)
while left < right:
mid = (left + right) // 2
required_days = 1
current_weight = 0
for w in weights:
if current_weight + w > mid:
required_days += 1
current_weight = w
if required_days > days:
break
else:
current_weight += w
if required_days <= days:
right = mid
else:
left = mid + 1
return left
from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
left = max(weights)
right = sum(weights)
while left < right:
mid = (left + right) // 2
required_days = 1
current_weight = 0
for w in weights:
if current_weight + w > mid:
required_days += 1
current_weight = w
if required_days > days:
break
else:
current_weight += w
if required_days <= days:
right = mid
else:
left = mid + 1
return left
ノート
- 最適スケジューリング系の問題なので二分探索は典型
- パターンマッチングになってしまうだけではなく、自分で単調性を確認してから方針を確定できると良い