📋
【Python3】コーディングテスト用チートシート（練習問題付き）
導入
コーディングテストに必要なアルゴリズムを図でやさしく説明してみた！ ではアルゴリズムの紹介をしたのですが、実際にアルゴリズムを使って問題を解くところまではできませんでした。
そこで、この記事ではPython3でコーディングテストや競技プログラミングに取り組むときに、よく使うアルゴリズムの実装や標準ライブラリーの使い方をまとめました。
さらに、練習問題を通してアルゴリズムを使って問題を解く経験を積めるようになっています。
おまけ程度ですが自分の解答をつけておいたので、よかったら参考にしてください。
この記事では、以下のような人を対象にしています。
基本的なアルゴリズムについては、上記の記事で紹介していますので、良かったら読んでください。
- 最低限の数学についての知識がある
- 使い慣れているプログラミング言語がある
- 基本的なアルゴリズムを理解している
- 練習問題を解き慣れている
Basics (条件分岐, 繰り返し)
- 入力サイズを確認する
-
10^7 - 入力サイズが小さければ
O(n^2)
-
- 簡単な例から考える
- 一番小さい入力サイズではどうなるか考えてみる
- 徐々に入力サイズを大きくしてアルゴリズムを考える
- 初級レベルの問題
- 条件分岐と繰り返し構文を扱う程度の問題もよく出る
- 難しく考え過ぎず、出来るだけ時間を使わない
# 多重ループ
for i in range(10):
for j in range(10):
for k in range(10):
for l in range(10):
print(i, j, k, l) # 0000 ~ 9999
# FizzBuzz問題
for i in range(100):
if i % 3 == 0 and i % 5 == 0:
print(i, "FizzBuzz") # 15 FizzBuzz
elif i % 3 == 0:
print(i, "Fizz") # 3 Fizz
elif i % 5 == 0:
print(i, "Buzz") # 5 Buzz
else:
print(i) # 1
Linked List (連結リスト)
- 連結リストは、要素と次のデータの場所からなるデータ構造である
# 連結リストをクラスとして定義
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 連結リストの作成
stack = collections.deque([5, 4, 3, 2, 1, 0])
head = ListNode(stack.pop())
pos = head # 参照渡し
while stack:
pos.next = ListNode(stack.pop())
pos = pos.next
# 連結リストから値を取り出す
while head != None:
print(head.val, end=" ") # 0 1 2 3 4 5
head = head.next
Stack (スタック)
- 入力サイズを確認する
- 簡単な例から考える
- スタックは、後に入れたものが先に出るデータ構造である
Python 標準ライブラリ >> データ型 >> コンテナデータ型 >> collections >> deque
公式ドキュメント
# スタックの作成
stack = collections.deque([])
# 追加
stack.append(1) # deque([1])
stack.append(2) # deque([1, 2])
# 取り出し
stack.pop() # deque([1])
練習問題
LeetCode 20. Valid Parentheses 目標時間: 15分
LeetCode 206. Reverse Linked List 目標時間: 15分
Heap Queue (ヒープキュー)
- 入力サイズを確認する
- 簡単な例から考える
- ヒープキューは、含まれる要素が何らかの優先度順に取り出されるデータ構造である
Python 標準ライブラリ >> データ型 >> heapq
公式ドキュメント
# 通常のリスト
heap = [4, 5, 8, 2]
# リストをでヒープに変換
heapq.heapify(heap) # [2, 4, 5, 8]
# 最小の要素にアクセス
heap[0] # 2
# 最小の要素を取り出す
heapq.heappop(heap) # [4, 5, 8]
# 要素を追加する
heapq.heappush(heap, 5) # [4, 5, 5, 8]
# ヒープキューの要素数
len(heap) # 4
練習問題
LeetCode 703. Kth Largest Element in a Stream 目標時間: 15分
LeetCode 347. Top K Frequent Elements 目標時間: 15分
LeetCode 373. Find K Pairs with Smallest Sums 目標時間: 30分
Hash Table (ハッシュテーブル)
- 入力サイズを確認する
- 簡単な例から考える
- ハッシュテーブルは、基本的なデータ構造の中でも非常に強力である
- 時間計算量を削減する必要がある場合にハッシュテーブルは必ず候補になる
Python 標準ライブラリ >> 組み込み型 >> マッピング型 >> dict
公式ドキュメント
# ハッシュテーブルの作成
d = {'apple': 100}
# キーが辞書にあればキーに対する値を返す
d.get('apple') # 100
# そうでなければ None を返す
d.get('banana') # None
Counter (カウンター)
Python 標準ライブラリ >> データ型 >> コンテナデータ型 >> collections >> Counter
公式ドキュメント
# リストを用意
nums = [1,1,1,2,2,3]
# 頻度を計算
c = collections.Counter(nums) # Counter({1: 3, 2: 2, 3: 1})
# 最も多いn要素を取得
c.most_common(2) # [(1, 3), (2, 2)]
Set (集合)
Python 標準ライブラリ >> 組み込み型 >> 集合型 >> set
公式ドキュメント
# 集合を作成する
visited = set()
# 集合に追加する
visited.add((0, 0)) # {(0, 0)}
visited.add((0, 1)) # {(0, 1), (0, 0)}
# 存在を確認する
(0, 0) in visited # True
練習問題
LeetCode 1. Two Sum 目標時間: 15分
LeetCode 49. Group Anagrams 目標時間: 15分
LeetCode 349. Intersection of Two Arrays 目標時間: 15分
LeetCode 929. Unique Email Addresses 目標時間: 15分
LeetCode 387. First Unique Character in a String 目標時間: 15分
LeetCode 560. Subarray Sum Equals K 目標時間: 30分
BFS (幅優先探索)
- 入力サイズを確認する
- 簡単な例から考える
- 幅優先探索は、問題をグラフとして扱える場合に有効なアルゴリズムである
- ある場所からある場所へ行くための経路を探す場合
- ある場所からある場所へ行くための最短経路を探す場合
- キューをスタックに置き換えれば、DFS(深さ優先探索)になる
- 行ける場所を探すための
explore関数を作成 - 行ける場所を保存しておく
queueを作成 - 訪れた場所を記録
Queue (キュー)
Python 標準ライブラリ >> データ型 >> コンテナデータ型 >> collections >> deque
公式ドキュメント
# キューの作成
queue = collections.deque([])
# 追加
queue.append(1) # deque([1])
queue.append(2) # deque([1, 2])
# 取り出し
queue.popleft() # deque([2])
練習問題
LeetCode 200. Number of Islands 目標時間: 30分
LeetCode 695. Max Area of Island 目標時間: 30分
Sort (ソート)
Python 標準ライブラリ >> 組み込み型 >> リスト型 >> sort
公式ドキュメント
Python 標準ライブラリ >> 組み込み関数 >> sorted()
公式ドキュメント
# 組み込み型のリストのソートメソッド(インプレースなソート)
nums = [3, 1, 4, 5, 2]
nums.sort() # [1, 2, 3, 4, 5]
# 組み込み関数のソート関数(新たなリストを生成)
nums = [3, 1, 4, 5, 2]
s_nums = sorted(nums) # [1, 2, 3, 4, 5]
Dynamic Programming (動的計画法)
- 入力サイズを確認する
- 一番簡単な例から考えていく
- 動的計画法は、問題を小さな問題に分割し、小さな問題を先に解くことによって解決する手法
- 小さな問題に分ける
- 結果を表(リストなど)に記録
- 表から必要な結果を利用
- どのタイプに当てはまるか考える
- フィボナッチ数列
- 部分和問題
- ナップサック問題
- 0から目標値までの最適解をそれぞれ求める
練習問題
LeetCode 300. Longest Increasing Subsequence 目標時間: 30分
LeetCode 53. Maximum Subarray 目標時間: 30分
LeetCode 62. Unique Paths 目標時間: 15分
LeetCode 63. Unique Paths II 目標時間: 30分
LeetCode 198. House Robber 目標時間: 15分
LeetCode 213. House Robber II 目標時間: 30分
LeetCode 121. Best Time to Buy and Sell Stock 目標時間: 15分
LeetCode 122. Best Time to Buy and Sell Stock II 目標時間: 30分
LeetCode 139. Word Break 目標時間: 30分
LeetCode 322. Coin Change 目標時間: 30分
Binary Search (二分探索)
- 入力サイズを確認する
- 入力サイズによっては二分探索を使う必要がない場合もある
- 一番簡単な例から考えていく
- 二分探索は、配列全体からある値を検索する場合に有効なアルゴリズムである
- 二分探索を使うためには、配列がソートされている必要がある
- 最小値と最大値を見つけて探索するの範囲を決める
- 中央値を見て、次に探索する範囲を決める
一つずつ見ていく方法の計算量は
となる O(n)
二分探索の計算量はである O(log n)
# 二分探索の実装
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
練習問題
LeetCode 35. Search Insert Position 目標時間: 15分
LeetCode 153. Find Minimum in Rotated Sorted Array 目標時間: 30分
LeetCode 33. Search in Rotated Sorted Array 目標時間: 30分
LeetCode 1011. Capacity To Ship Packages Within D Days 目標時間: 30分
Sliding Window (スライディングウィンドウ)
- 入力サイズを確認する
- 一番簡単な例から考えていく
- スライディングウィンドウは、配列内の(連続した)部分配列などを検索する場合に有効である
- 左右のポインターを用意する
- 範囲を指定してずらしながら調査していく
全ての組み合わせを見ていく方法の計算量は
となる O(n^2)
スライディングウィンドウの計算量はである O(n)
練習問題
LeetCode 3. Longest Substring Without Repeating Characters 目標時間: 15分
LeetCode 209. Minimum Size Subarray Sum 目標時間: 30分
Backtracking (バックトラッキング)
- 入力サイズを確認する
- 一番簡単な入力で考える
- バックトラッキングは、全通り試していく途中で、解になり得ないときは手を引く方法である
- 全ての順列と組み合わせを考える必要がある
- 途中で解になり得ないと分かった時点で止める枝刈りを追加する
順列と組み合わせ
Python 標準ライブラリ >> 関数型プログラミング用モジュール >> itertools >> 組合せイテレータ
公式ドキュメント
# リストを用意
l = ['0', '1', '2', '3']
# リストから順列を生成
for p in itertools.permutations(l, 2):
print(p) # ('0', '1') ~ ('3', '2')
# リストから組み合わせを生成
for c in itertools.combinations(l, 2):
print(c) # ('0', '1') ~ ('2', '3')
練習問題
LeetCode 46. Permutations 目標時間: 15分
LeetCode 78. Subsets 目標時間: 15分
LeetCode 39. Combination Sum 目標時間: 30分
LeetCode 22. Generate Parentheses 目標時間: 30分
その他
文字列
Python 標準ライブラリ >> 組み込み型 >> テキストシーケンス型 >> str
公式ドキュメント
# リストを用意
l = ["a", "b", "c", "d", "e"]
# リストを文字列に変換
s = "".join(l)
print(s) # "abcde"
# 文字列を指定して置換
s = s.replace("a", "")
print(s) # "bcde"
# 文字列を区切り文字で分割
s = s.split("c")
print(s) # ['b', 'de']
標準入力
lines = []
for l in sys.stdin:
lines.append(l.rstrip('\r\n'))
print(lines) # ['a', 'b', 'c', 'd']
まとめ
まずは、全ての練習問題を目標時間以内に解けることを目標としましょう。
コーディングテストのレベルによっては、さらに難易度の高い問題が出てくる場合もあります。
また、練習問題にないような実装問題と呼ばれる問題の練習もしておいた方が良いと思います。
参考資料
コーディング面接対策のために解きたいLeetCode 60問
ここで紹介されている練習問題を参考にさせていただきました。
どのような順番でアルゴリズムとデータ構造を説明すると分かりやすいのか参考にさせていただきました。
練習問題の解答
Stack (スタック)
LeetCode 20. Valid Parentheses
class Solution:
def isValid(self, s: str) -> bool:
# 括弧のペアを用意
parentheses = {
')': '(',
']': '[',
'}': '{'
}
# スタックを用意
stack = collections.deque([])
# スタックを利用
for i in s:
if not stack:
stack.append(i)
elif stack[-1] == parentheses.get(i):
stack.pop()
else:
stack.append(i)
return len(stack) == 0
LeetCode 206. Reverse Linked List
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 例外処理
if head == None:
return head
# スタックの用意
stack = collections.deque([])
# スタックに一旦入れる
while head != None:
stack.append(head.val)
head = head.next
# スタックから連結リストに入れ直す
head = ListNode(stack.pop())
pos = head
while stack:
pos.next = ListNode(stack.pop())
pos = pos.next
return head
Heap Queue (ヒープキュー)
LeetCode 703. Kth Largest Element in a Stream
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.nums = nums
self.k = k
# ヒープを使って上位k個の要素を用意
heapq.heapify(self.nums)
while len(self.nums) > self.k:
heapq.heappop(self.nums)
def add(self, val: int) -> int:
# 値が足りていないとき
if len(self.nums) < self.k:
heapq.heappush(self.nums, val)
return self.nums[0]
# 追加したい要素と最小値を比較
elif val < self.nums[0]:
return self.nums[0]
else:
heapq.heapreplace(self.nums, val)
return self.nums[0]
LeetCode 347. Top K Frequent Elements
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 頻度を計算
c = collections.Counter(nums)
# 頻度の高いk個の要素をリストに追加
ans = []
for k, v in c.most_common(k):
ans.append(k)
return ans
LeetCode 373. Find K Pairs with Smallest Sums
class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
ans = []
heap = []
heapq.heapify(heap)
visited = set()
# 1つ目の値をヒープに追加
heapq.heappush(heap, [nums1[0] + nums2[0], 0, 0])
visited.add((0, 0))
while heap and len(ans) < k:
# 最小値を取り出す
_, i, j = heapq.heappop(heap)
ans.append([nums1[i], nums2[j]])
# 訪れていなくて、リストの範囲内である場合に探索する場所を追加
if i + 1 < len(nums1) and (i+1, j) not in visited:
heapq.heappush(heap, [nums1[i+1] + nums2[j], i+1, j])
visited.add((i+1, j))
if j + 1 < len(nums2) and (i, j+1) not in visited:
heapq.heappush(heap, [nums1[i] + nums2[j+1], i, j+1])
visited.add((i, j+1))
return ans
Hash Table (ハッシュテーブル)
LeetCode 1. Two Sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 目標値との差分をキーとして登録
d = {}
for i, n in enumerate(nums):
d[target - n] = i
# 差分と等しい値を探す
for i, n in enumerate(nums):
if n in d:
# 同じインデックスでない場合
if d[n] != i:
return [i, d[n]]
LeetCode 49. Group Anagrams
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for i, s in enumerate(strs):
# 文字列をソートされた文字列に変換
new_s = ''.join(sorted(s))
# ソートされた文字列をキーとした辞書
if new_s in d:
d[new_s].append(s)
else:
d[new_s] = [s]
# アナグラムごとに分けて出力
ans = []
for v in d.values():
ans.append(v)
return ans
LeetCode 349. Intersection of Two Arrays
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 集合に変換
n1 = set(nums1)
n2 = set(nums2)
# 2つの集合から積集合を取得
return list(n1 & n2)
LeetCode 929. Unique Email Addresses
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
registered = set()
for email in emails:
# ローカル名とドメイン名に分割
local, domain = email.split("@")
# ローカル名からドットを削除する
local = local.replace(".", "")
# ローカル名から+以降を削除する
local = local.split("+")[0]
# 純粋なメールアドレスを抽出
email = local + "@" + domain
# 登録されているか確認
if email not in registered:
registered.add(email)
return len(registered)
LeetCode 387. First Unique Character in a String
class Solution:
def firstUniqChar(self, s: str) -> int:
d = {}
# 1回目はindex、2回目以降は-1を値とする
for i, c in enumerate(s):
if c in d:
d[c] = -1
else:
d[c] = i
# -1以外が出てくるまで取り出す
minIndex = float("inf")
for v in d.values():
if v != -1:
minIndex = min(minIndex, v)
if minIndex != float("inf"):
return minIndex
else:
return -1
LeetCode 560. Subarray Sum Equals K
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
total = 0
sums = {0: 1}
for n in nums:
total += n
diff = total - k
# 合計値と目標値との差分が、ある位置までの合計値と等しい場合
if diff in sums:
count += sums[diff]
# そこまでの合計値を辞書に追加
if total in sums:
sums[total] += 1
else:
sums[total] = 1
return count
BFS (幅優先探索)
LeetCode 200. Number of Islands
def explore(grid, queue, i, j):
# 上下左右の要素を調査
if 0 <= i - 1:
if grid[i-1][j] == "1":
grid[i-1][j] = "X"
queue.append((i-1, j))
if i + 1 < len(grid):
if grid[i+1][j] == "1":
grid[i+1][j] = "X"
queue.append((i+1, j))
if 0 <= j - 1:
if grid[i][j-1] == "1":
grid[i][j-1] = "X"
queue.append((i, j-1))
if j + 1 < len(grid[i]):
if grid[i][j+1] == "1":
grid[i][j+1] = "X"
queue.append((i, j+1))
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 島の数をカウント
count = 0
# 行列の全ての要素を探索
for i in range(len(grid)):
for j in range(len(grid[i])):
# 島ならカウント
if grid[i][j] == "1":
count += 1
# 隣接する陸を置き換える
grid[i][j] = "X"
queue = collections.deque([(i, j)])
while queue:
k, l = queue.popleft()
explore(grid, queue, k, l)
return count
LeetCode 695. Max Area of Island
def explore(grid, queue, i, j):
# 上下左右の要素を調査
if 0 <= i - 1:
if grid[i-1][j] == 1:
grid[i-1][j] = "X"
queue.append((i-1, j))
if i + 1 < len(grid):
if grid[i+1][j] == 1:
grid[i+1][j] = "X"
queue.append((i+1, j))
if 0 <= j - 1:
if grid[i][j-1] == 1:
grid[i][j-1] = "X"
queue.append((i, j-1))
if j + 1 < len(grid[i]):
if grid[i][j+1] == 1:
grid[i][j+1] = "X"
queue.append((i, j+1))
class Solution:
def maxAreaOfIsland(self, grid: List[List[str]]) -> int:
# 最大の面積
maxArea = 0
# 行列の全ての要素を探索
for i in range(len(grid)):
for j in range(len(grid[i])):
area = 0
# 島なら面積を計算
if grid[i][j] == 1:
grid[i][j] = "X"
queue = collections.deque([(i, j)])
while queue:
# 面積を加算
area += 1
k, l = queue.popleft()
explore(grid, queue, k, l)
# 最大の面積を更新
maxArea = max(maxArea, area)
return maxArea
Dynamic Programming (動的計画法)
LeetCode 300. Longest Increasing Subsequence
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 各部分で増加する部分配列の最長の長さを保存
length = [1 for _ in range(len(nums))]
# ある値とその左にある値を比較して最長の長さを更新
for i in range(len(nums)):
maxLen = 1
for j in range(0, i):
if nums[i] > nums[j]:
if maxLen < length[j] + 1:
maxLen = length[j] + 1
length[i] = maxLen
return max(length)
LeetCode 53. Maximum Subarray
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 例外処理
if len(nums) == 1:
return nums[0]
total = nums[0]
maxTotal = nums[0]
for n in nums[1:]:
# (今までの合計 + 次の値) > 次の値 なら加算する
if total + n > n:
total += n
# (今までの合計 + 次の値) > 次の値 なら置き換える
else:
total = n
# 今までの最大値を更新
if maxTotal < total:
maxTotal = total
return maxTotal
LeetCode 62. Unique Paths
from operator import mul
from functools import reduce
def combinations_count(n, r):
r = min(r, n - r)
numer = reduce(mul, range(n, n - r, -1), 1)
denom = reduce(mul, range(1, r + 1), 1)
return numer // denom
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 例外処理
if m == 1 or n == 1:
return 1
# 全ての道数
paths = (m-1) + (n-1)
return combinations_count(paths, (n-1))
LeetCode 63. Unique Paths II
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 配列のサイズを取得
m, n = len(obstacleGrid), len(obstacleGrid[0])
# あるマスまで行くことができる経路数を記録
pathsGrid = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
# 障害物があるときは加算しない
if obstacleGrid[i][j] == 1:
continue
# 上と左のマスへ行くことができる経路数を加算
if i == 0 and j == 0:
pathsGrid[i][j] = 1
elif i == 0:
pathsGrid[i][j] += pathsGrid[i][j - 1]
elif j == 0:
pathsGrid[i][j] += pathsGrid[i - 1][j]
else:
pathsGrid[i][j] += pathsGrid[i - 1][j] + pathsGrid[i][j - 1]
return pathsGrid[m - 1][n - 1]
LeetCode 198. House Robber
class Solution:
def rob(self, nums: List[int]) -> int:
# 例外処理
if len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums[0], nums[1])
# 各時点での最大の合計値を記録
amount = [i for i in nums]
# 隣を除いた左側で最大の要素を加算
for i in range(2, len(nums)):
amount[i] += max(amount[0:i-1])
return max(amount)
LeetCode 213. House Robber II
class Solution:
def rob(self, nums: List[int]) -> int:
# 例外処理
if len(nums) <= 3:
return max(nums)
# 左端を使って右端を使わない or 左端を使わず右端を使う
lAmount = [i for i in nums]
lAmount[0] = 0
rAmount = [i for i in nums]
rAmount[-1] = 0
# 隣を除いた左側で最大の要素を加算
for i in range(2, len(nums)):
lAmount[i] += max(lAmount[0:i-1])
rAmount[i] += max(rAmount[0:i-1])
# 最大値の比較
return max(max(lAmount), max(rAmount))
LeetCode 121. Best Time to Buy and Sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 例外処理
if len(prices) == 1:
return 0
elif len(prices) == 2:
profit = prices[1] - prices[0]
if profit < 0:
return 0
else:
return profit
# 初期値を設定
minPrice = prices[0]
maxProfit = 0
for price in prices[1:]:
# 最大値の更新
if maxProfit < price - minPrice:
maxProfit = price - minPrice
# 最小値の更新
if minPrice > price:
minPrice = price
return maxProfit
LeetCode 122. Best Time to Buy and Sell Stock II
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 例外処理
if len(prices) == 1:
return 0
elif len(prices) == 2:
profit = prices[1] - prices[0]
if profit < 0:
return 0
else:
return profit
# 初期値を設定
minPrice = prices[0]
maxProfit = 0
profitSum = 0
for price in prices[1:]:
# 最大値の更新
if maxProfit < price - minPrice:
maxProfit = price - minPrice
# 最大値を更新できなければ、利益確定して最小値の更新
else:
profitSum += maxProfit
maxProfit = 0
minPrice = price
return profitSum + maxProfit
LeetCode 139. Word Break
class Solution:
def wordBreak(self, s, wordDict):
n = len(s)
# 分割可能な位置を記録
is_divisible = [True] + [False] * n
# 範囲を決めてその部分の単語を調べる
for l in range(n):
for r in range(l, n):
# もし開始位置で区切ることができ、その単語が辞書にあれば
if is_divisible[l] and s[l:r+1] in wordDict:
# その場所も区切れる
is_divisible[r+1] = True
return is_divisible[n]
LeetCode 322. Coin Change
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# ある金額を払うために必要最小限のコインの枚数を記録
dp = [0] + [float("inf")] * amount
for subAmount in range(1, amount+1):
# コインを一枚追加して支払える金額を更新
for coin in coins:
remains = subAmount - coin
if remains >= 0:
# 必要な枚数 = あるコインを1枚 + 残りの金額を支払うの必要な枚数
dp[subAmount] = min(dp[subAmount], 1 + dp[remains])
if dp[amount] != float("inf"):
return dp[amount]
else:
return -1
Binary Search (二分探索)
LeetCode 35. Search Insert Position
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 最小値と最大値を見つけて探索するの範囲を決める
low = 0
high = len(nums) - 1
# 中央値を見て、次に探索する範囲を決める
while low <= high:
mid = (low + high) // 2
# 目標値なら返す
if nums[mid] == target:
return mid
# 次に探索する範囲を決める
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
# もし存在しない場合にどこに追加するか考える
if target <= nums[mid]:
return mid
else:
return mid + 1
LeetCode 153. Find Minimum in Rotated Sorted Array
class Solution:
def findMin(self, nums: List[int]) -> int:
# 最小値と最大値を見つけて探索するの範囲を決める
left = 0
right = len(nums) - 1
# 例外処理
if nums[left] <= nums[right]:
return nums[left]
# 中央値を見て、次に探索する範囲を決める
while left <= right:
mid = (left + right) // 2
# 目標値は 「左<右」のはずが「左>右」となっている箇所
if nums[mid] > nums[mid+1]:
return nums[mid+1]
elif nums[mid-1] > nums[mid]:
return nums[mid]
# 次に探索する範囲を決める
if nums[0] > nums[mid]:
right = mid - 1
else:
left = mid + 1
LeetCode 33. Search in Rotated Sorted Array
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 最小値と最大値を見つけて探索するの範囲を決める
left = 0
right = len(nums) - 1
# 中央値を見て、次に探索する範囲を決める
while left <= right:
mid = (left + right) // 2
# 目標値か確認
if nums[mid] == target:
return mid
# 次に探索する範囲を決める
elif nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
left = mid + 1
else:
right = mid - 1
return -1
LeetCode 1011. Capacity To Ship Packages Within D Days
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
# 最小値と最大値を見つけて探索するの範囲を決める
minCap = max(weights) # 最低でも一番重いものが運べる必要がある
maxCap = sum(weights) # 全て重さの合計を超えることはない
# 中央値を見て、次に探索する範囲を決める
while minCap < maxCap:
midCap = (minCap + maxCap) // 2
# この容量で何日かかるか計算
reqDays = 1
tmpWeights = 0
for w in weights:
tmpWeights += w
if tmpWeights > midCap:
reqDays += 1
tmpWeights = w
# 次に探索する範囲を決める
if reqDays <= days:
maxCap = midCap
else:
minCap = midCap + 1
return minCap
Sliding Window (スライディングウィンドウ)
LeetCode 3. Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 左右のポインターを用意する
left = 0
right = 0
# 例外処理
if len(s) < 1:
return 0
longest = 1
checked = set(s[0])
# 範囲を指定してずらしながら調査していく
while right < len(s) - 1:
right += 1
# 確認済みの文字が入ってきた場合
if s[right] in checked:
# 確認済みの文字まで、左のポインタをずらす
while left <= right:
if s[left] == s[right]:
left += 1
break
else:
checked.remove(s[left])
left += 1
else:
checked.add(s[right])
# 最大の長さを更新
if longest < right - left + 1:
longest = right - left + 1
return longest
LeetCode 209. Minimum Size Subarray Sum
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# 左右のポインターを用意する
left = 0
right = 0
tmpSum = 0
minLen = float("inf")
for right in range(len(nums)):
tmpSum += nums[right]
# 目標値を超えた場合
if tmpSum >= target:
# 目標値を下回るまで、左のポインタをずらす
while tmpSum >= target and left <= right:
# 最小の長さを更新
minLen = min(minLen, right - left + 1)
tmpSum -= nums[left]
left += 1
# 結果を処理
if minLen == float("inf"):
return 0
else:
return minLen
Backtracking (バックトラッキング)
LeetCode 46. Permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
# リストから順列を生成
for p in itertools.permutations(nums, len(nums)):
ans.append(p)
return ans
LeetCode 78. Subsets
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = [[]]
# リストから組み合わせを生成
for i in range(1, len(nums) + 1):
for c in itertools.combinations(nums, i):
ans.append(c)
return ans
LeetCode 39. Combination Sum
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
# 目標値から値を引いていく
queue = collections.deque([])
queue.append([candidates, target, 0, []])
ans = []
# 全ての組み合わせを幅優先探索
while queue:
candidates, remain, start, path = queue.popleft()
# 丁度ゼロになったら解答に追加
if remain == 0:
ans.append(path)
# 同じ文字を使えるルートと使えないルートに分岐
for i in range(start, len(candidates)):
# 目標値を超えてしまった時点で枝刈り
if remain - candidates[i] >= 0:
queue.append([candidates, remain - candidates[i], i, path + [candidates[i]]])
return ans
LeetCode 22. Generate Parentheses
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# "("と")"をn個ずつ用意し消費
queue = collections.deque([])
queue.append([n, n, ""])
ans = []
# 全ての組み合わせを幅優先探索
while queue:
left, right, pairs = queue.popleft()
# 丁度ゼロになったら解答に追加
if left == 0 and right == 0:
ans.append(pairs)
# left > right でない部分を枝刈り
if 0 <= left - 1 <= right:
queue.append([left - 1, right, pairs + "("])
if 0 <= left <= right - 1:
queue.append([left, right - 1, pairs + ")"])
return ans
Discussion