自己紹介
初めまして。
本誌を訪問頂き有難うございます。
趣味で python を始めた中年おじさんです。
基礎から始めたくて記事を書き始めた今日この頃です。
本誌は基礎編 第三弾です。
第一弾 基礎編:木構造の全探索(DFS/BFS)
第二弾 基礎編:基礎編:二分探索
学習目標
今回は Leetcode:Recursion I の理解を目標とします。
どのように理解するかは、以下のアプローチで進めます。
テンプレートの暗記 =>
記述の理解(イメージ作成) =>
自分なりのアプローチで再検証 =>
理解の穴を埋める
試行錯誤を繰り返すことで理解が深まり、思考力が養われると思います。
例題1 Reverse String
文字列を反転できる機能を実装してください。
#Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
#Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
解説
純粋に反転するなら以下の記述が簡潔です。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
再帰処理であれば以下です。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def helper(left,right):
if left < right:
s[left],s[right] =s[right],s[left]
helper(left+1,right-1)
helper(0,len(s)-1)
この再帰的な記述は用途は不明ですが、
def reverseString に文字列を入れたら
反転した文字列を出力できた方が良いと思います。
別解もセットで考えなおしました。
class Reverse:
def Approach1(nums):
left,right = 0,len(nums)-1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left +=1
right -=1
return nums
def Approach2(nums):
def helper(left,right):
if left < right:
helper(left+1,right-1)
nums[left],nums[right] = nums[right],nums[left]
return nums
return helper(0,len(nums)-1)
nums =['a','b','c','d','e','f','g','h','i','j']
#-select approach-
#-----------------
#1.iterative
#print(Reverse.Approach1(nums))
#2.recursive
print(Reverse.Approach2(nums))
Recursive に関しては基本かもしれませんが、
逆転できる最下層まで一旦潜った後に、中央から left,right を反転し、
上位層に戻って反転を繰り返すことで意図した出力になります。
例題2 Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
与えられた linked list で 2 ノードずつ逆転させて、その head を返してください。
#Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
#Example 2:
Input: head = []
Output: []
#Example 3:
Input: head = [1]
Output: [1]
制約:
The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100
解説
ノードの値を反転させる場合は、
head を格納する箱を 2 つ用意する必要があります。
これは、一方に格納した head の値を、もう一方の head に繋ぎあわせる作業を
繰り返すことで求められている回答を output するためです。
回答のコードと、その動きを追うための GIF を用意しました。
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
first_node = head
second_node= head.next
first_node.next = self.swapPairs(second_node.next)
second_node.next=first_node
return second_node
例題3 Pascal's Triangle
パスカルの三角形において f(5,3) の値を求めてください。
※個人的に面白かったので掲載します。
解説
leetcode 先生のありがたい教えを賜ることが出来ました。
再帰処理を組む前に大事なことが 2 つあるそうです。
1.漸化式の定義
2.終点の定義
本件に当てはめて考えてみると、
以下のようになると思います。
1.漸化式 : f(i,j) = f(i-1,j-1) + f(i-1,j)
2.終点 : i == 1 or j == 1 or i == j の時、f(i,j) == 1
これを念頭にコードを書いてみます。
def pascal(i,j):
if i == 1 or j == 1 or i == j:
return 1
return pascal(i-1,j-1)+pascal(i-1,j)
print(pascal(5,3))
#output : 6
先生の説明にもありますが重複した計算を行わなければならないのが
欠点になります。しっかり計算済みの物は保存して計算を最適化しましょうとのことです。
後の方で出てくるそうです。。。
また、この方法では後程出てくる問題は時間が掛かり過ぎて fail しますので注意が必要です。
演習1 Reverse Linked List
linked list を逆転させてください。
#Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
コメント:
iteratively or recursively のいずれでも解けます. 両方できますか?
解説
iteratively を取り急ぎやってみました。
ざっくり以下のイメージで書いています。
POINT1. head から val を取り出して q =[] に格納する
POINT2. q の値をもとに LinkList を作り直す
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#POINT1
q =[]
while head:
q.append(head.val)
head = head.next
q.reverse()
#POINT2
root = None
while q:
nums = q.pop(0)
if not root:
root = ListNode(nums)
else:
runner = root
while runner.next:
runner = runner.next
runner.next = ListNode(nums)
return root
recursively approach も挑戦してみましたが、
LinkedList の circle がイメージ出来ないと厳しいようです。
自分なりに情報取集してみました。
Design Linked List
基礎の見直しと、特に Delete のイメージが circle を作る時に役に立ちます。
Linked List Cycle
与えられた LinkedList に circle が含まれているかを確認する問題で、チャレンジ & 解説を読むと good
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
p = self.reverseList(head.next)
head.next.next = head # make cycle
head.next = None # remove cycle
return p
前述にある make cycle でサイクルを作っています。
p は、名称は p ですが、中身は head です。
そのため #make cycle , #remove cycle の記述にある
head を編集する記述を適用することが出来るようです。
[LinkedList: 1 -> 2 の場合]
[LinkedList: 1 -> 2 -> 3 の場合]
演習2 Search in a Binary Search Tree
BST と 整数をお渡しします。
整数が BST に含まれているか確認をお願いいたします。
含まれていれば、その値を起点とした部分木の値を全て返してください。
もし、こちらが指定した整数が含まれていなければ null を返してください。
#Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
#Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
制約:
ノード数は 1 ~ 5000。
ノードで格納されるデータは 1 以上 10^7 以下
与えられた Tree は必ず二分探索義
解説
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if root is None or val == root.val:
return root
return self.searchBST(root.left, val) if val < root.val \
else self.searchBST(root.right, val)
演習3 Pascal's Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
#Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
#Example 2:
Input: rowIndex = 0
Output: [1]
#Example 3:
Input: rowIndex = 1
Output: [1,1]
解説
Iterative ですが、BSF の要領で解いてみました。
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
ans =[]
for i in range(rowIndex+1):
ans.append([])
for j in range(i+1):
if j == 0 or j == i:
ans[i].append(1)
else:
ans[i].append(ans[i-1][j-1]+ans[i-1][j])
return ans[rowIndex]
Recursive も出来たのですが、
Time over になりました。JAVA なら、この記述でもいけるのに(泣
class Solution:
def getNum(row,col):
if row == 0 or col == 0 or row == col:
return 1
return Solution.getNum(row-1,col-1)+Solution.getNum(row-1,col)
def getRow(self, rowIndex: int) -> List[int]:
ans = []
for i in range(rowIndex+1):
ans.append(Solution.getNum(rowIndex,i))
return ans
因みに時間は掛かりますが、後述している memorization の考え方を導入すると通ります。
#164ms
import numpy as np
class Solution:
def getNum(row,col):
memo = np.zeros((34,34),dtype = "int")
def helper(row,col):
if memo[row][col] != 0:
return memo[row][col]
if row == 0 or col == 0 or row == col:
result = 1
else:
result = helper(row-1,col-1)+helper(row-1,col)
memo[row][col] = result
return result
return helper(row,col)
def getRow(self, rowIndex: int) -> List[int]:
ans = []
for i in range(rowIndex+1):
ans.append(Solution.getNum(rowIndex,i))
return ans
recursive かつ時間に拘るなら以下のような記述も
あるようです(もっとシンプルに書けないのかなー)。
#12ms
class Solution:
def getRowHelper(self, row, rowList, currentList):
if row == 0:
return
if row == 1:
return
self.getRowHelper(row-1, rowList, currentList)
for i in range(1, row):
rowList[i] = currentList[i-1] + currentList[i]
currentList[:] = rowList[:]
return
def getRow(self, rowIndex: int) -> List[int]:
totalNumber = rowIndex + 1
rowList = [1]*totalNumber
currentList = [1]*totalNumber
self.getRowHelper(rowIndex, rowList, currentList)
return rowList
演習4 Fibonacci Number
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence,
such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
#Example 1:
Input: n = 2
Output: 1
#Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
#Example 2:
Input: n = 3
Output: 2
#Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
#Example 3:
Input: n = 4
Output: 3
#Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
解説
再帰処理の欠点として重複計算が挙げられます。
これにより、処理時間が大幅に増えるケースがあることが挙げられます。
これを改善するために重複箇所はメモしたところから取り出すことで
処理時間の改善を図ることが可能です。
上図の "memo 前" にあるように再帰処理をしてみると
全探索のイメージで重複計算も含めて全部計算しようとします。
では、その計算量は如何ほどなのでしょうか。
ご覧のとおり実行の工程をツリー化してみて分かるように二分木として判断されます。
例えば n = 4 で計算する場合、Tree の深さは 4 となります。
これは 2^n -1 になりますので、O(2^n) と判断されます。
一方で "memo 後"を見ていきましょう。
以下のコードを実行してみればわかると思いますが、
fibo(n-1) + fibo(n-2) とあれば、左側の fibo(n-1) から再帰処理を解こうとします。
これは Binary Tree の inorder と同じような考え方で進んでいきます。
よって上図にあるように F(0) ~ F(3) まで演算した結果をメモしていきます。
その後発生する点線で表現された演算はメモから取り出すので演算は免除となります。
つまり計算量は n に依存するので O(n) となります。
詳細は Time Complexity - Recursion から確認ができます。
class Solution:
#796ms
def fib_none_memo(self, N: int) -> int:
if N <= 1:
return N
return self.fib_none_memo(N-1) + self.fib_none_memo(N-2)
#24ms
def fib_use_memo(self, N: int) -> int:
cache = {}
def helper(n):
if n in cache:
return cache[n]
if n < 2:
result = n
else:
result = helper(n-2) + helper(n-1)
cache[n] = result
return result
return helper(N)
計算内容をメモしていく考え方は勿論 leetcode 先生の教えです。
memorization をクリックすると詳細を確認することが可能です。
ハッシュを使った考え方がベースになるので hash の学習は必須になりそうです。
演習5 Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
#Example 1:
Input: n = 2
Output: 2
#Explanation: There are two ways to climb to the top.
#1. 1 step + 1 step
#2. 2 steps
#Example 2:
Input: n = 3
Output: 3
#Explanation: There are three ways to climb to the top.
#1. 1 step + 1 step + 1 step
#2. 1 step + 2 steps
#3. 2 steps + 1 step
解説
一般的な再帰処理の解は time over となりうるのですが、
前述にある memorization を導入すると見事に通ります。
#28ms
class Solution:
def climbStairs(self, n: int) -> int:
cache = {}
def helper(cnt,t1,t2,n):
if n in cache:
return cache[n]
if n == 0:
cnt += 1
return cnt
if 0 <= n-1:t1 = helper(cnt,t1,t2,n-1)
if 0 <= n-2:t2 = helper(cnt,t1,t2,n-2)
cache[n] = t1 + t2
return t1 + t2
return helper(0,0,0,n)
例題3 RversePrinting
入力した文字を反転して出力してください。
アプローチは再帰処理でお願いいたします。
解説
筆者の環境は Python 3 だからでしょうか。
以下のように修正しないと、こちらの環境では思うように動きませんでした。
def sum_non_tail_recursion(ls):
if len(ls) == 0:
return ""
return sum_non_tail_recursion(ls[1:]) + ls[0]
def sum_tail_recursion(ls):
def helper(ls, acc):
if len(ls) == 0:
return acc
return helper(ls[1:], ls[0] + acc)
return helper(ls, "")
ls = ["a","b","c","d"]
print(sum_non_tail_recursion(ls))
print(sum_tail_recursion(ls))
前述の解説 Tail recursion に素晴らしいことが記載されていました。
関数を call するときに現在の関数のパラメータとの演算をしている場合、
現在の関数の情報をメモリに残した状態で次の関数用のメモリを確保する必要があります。
しかし、再帰用に関数を call するときに現在の関数のパラメータとの演算なく、
関数の call だけで完結できれば既存のメモリ領域内で処理が完結するできるそうです。
すばらしい。
例題4 Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
#Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
#Example 2:
Input: root = [1,null,2]
Output: 2
#Example 3:
Input: root = []
Output: 0
#Example 4:
Input: root = [0]
Output: 1
解説
これは過去に解いている問題で、Tree の深さを求める問題です。
例題3 にあったように leetcode 先生の教えから none tail , tail で解いて比較してみました。
class Solution:
#run time : 48ms
#memory usage : 18.8MB
def maxDepth_none_tail(self, root: TreeNode) -> int:
def helper(l,r):
if not root:
return 0
if root.left: l = self.maxDepth_none_tail(root.left) + 1
if root.right:r = self.maxDepth_none_tail(root.right)+ 1
return max(l,r)
return helper(1,1)
#run time : 36ms
#memory usage : 16.5MB
def maxDepth_tail(self, root: TreeNode) -> int:
if not root:return 0
def helper(node,cnt,l,r):
if not node.left and not node.right:
return cnt
if node.left: l = helper(node.left,cnt+1,l,r)
if node.right:r = helper(node.right,cnt+1,l,r)
cnt = max(l,r)
return cnt
return helper(root,0,0,0)+1
教えのとおりにメモリの使用率も減り、
その分、処理スピードも上がりました。
演習6 Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
#Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
#Example 2:
Input: l1 = [], l2 = []
Output: []
#Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
解説
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
演習7 K-th Symbol in Grammar
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).
#Examples1:
Input: N = 1, K = 1
Output: 0
Input: N = 2, K = 1
Output: 0
Input: N = 2, K = 2
Output: 1
Input: N = 4, K = 5
Output: 1
#Explanation:
#row 1: 0
#row 2: 01
#row 3: 0110
#row 4: 01101001
Note:
N will be an integer in the range [1, 30].
K will be an integer in the range [1, 2^(N-1)].
解説
class Solution():
def kthGrammar(self, N, K):
if N == 1: return 0
if K <= (2**(N-2)):
return self.kthGrammar(N-1, K)
return self.kthGrammar(N-1, K - 2**(N-2)) ^ 1
演習8 Unique Binary Search Trees II
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
#Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
#Example 2:
Input: n = 1
Output: [[1]]
制約:
1 <= n <= 8
解説
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generate_trees(start, end):
if start > end:
return [None,]
all_trees = []
for i in range(start, end + 1): # pick up a root
# all possible left subtrees if i is choosen to be a root
left_trees = generate_trees(start, i - 1)
# all possible right subtrees if i is choosen to be a root
right_trees = generate_trees(i + 1, end)
# connect left and right subtrees to the root i
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
return generate_trees(1, n) if n else []