Closed14
Leetcode自分用解答メモ[Explore - Recursion I]
リアルにサーモンleetcodeを説いていて、自分の回答とかsolutionを読んで実装したやつとか詰まったとことかメモしとく
チャプターごとにスクラップで記録して、終わったらアーカイブする。
リアルにサーモン
文字列の配列をin-placeで逆順にする。
最初の実装
object Solution {
def reverseString(s: Array[Char]): Unit = {
def loop(i: Int): Unit = {
if (i <= s.length / 2) {
val tmp = s(i - 1)
s(i - 1) = s(s.length - i)
s(s.length - i) = tmp
loop(i + 1)
}
}
loop(1)
}
}
Approach 2: Two Pointers, Iteration, \mathcal{O}(1)O(1) Space
object Solution {
def reverseString(s: Array[Char]): Unit = {
var left = 0
var right = s.length - 1
while (left < right) {
val tmp = s(left)
s(left) = s(right)
s(right) = tmp
left += 1
right -= 1
}
}
}
two pointerでIterationで特パターン。
リアルにサーモン
最初の実装
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def swapPairs(head: ListNode): ListNode = {
if (head != null && head.next != null) {
val tmp = head.next.next
head.next.next = head
val newHead = head.next
head.next = tmp
if (newHead.next.next != null) {
val tmp2 = swapPairs(newHead.next.next)
newHead.next.next = tmp2
}
return newHead
}
head
}
}
少し手間取った。こういうノードを入れ替える系でよく混乱してしまうので落ち着いてストレートに解けるようにしたい。
最初にfirstNodeとsecondNodeとしてコピーするべきだった
Approach 2: Iterative Approach
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def swapPairs(head: ListNode): ListNode = {
if (head == null) return null
val dummy = new ListNode(-1, head)
var prevNode = dummy
var curNode = head
while(curNode != null && curNode.next != null) {
val firstNode = curNode
val secondNode = curNode.next
firstNode.next = secondNode.next
secondNode.next = firstNode
prevNode.next = secondNode
prevNode = firstNode
curNode = prevNode.next
}
dummy.next
}
}
Space Complexity : O(1)で解ける。(prevNodeとcurNodeの分?)
ScalaではSolutionで示されているように引数のheadを書き換えられなかったのでcurNodeを定義している。
リアルにサーモン
自分の実装
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def reverseList(head: ListNode): ListNode = {
if (head == null) return null
val dummy = new ListNode()
var cur = dummy
def loop(node: ListNode): Unit = {
if (node.next != null) loop(node.next)
node.next = null
cur.next = node
cur = cur.next
}
loop(head)
dummy.next
}
}
Approach #2 (Recursive) [Accepted]
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def reverseList(head: ListNode): ListNode = {
if (head == null || head.next == null) return head
val p = reverseList(head.next)
head.next.next = head
head.next = null
p
}
}
Solutionで示されていた再帰の解法。再帰の実行順序をきちんと脳内で再生できないと理解できず最初ちょっと難しかったがなるほど。
リアルにサーモン
/**
* Definition for a binary tree node.
* class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
* var value: Int = _value
* var left: TreeNode = _left
* var right: TreeNode = _right
* }
*/
object Solution {
def searchBST(root: TreeNode, `val`: Int): TreeNode = {
if (root == null) return null
if (root.value == `val`) return root
val left = searchBST(root.left, `val`)
if (left != null) return left
val right = searchBST(root.right, `val`)
if (right != null) return right
null
}
}
単純な二分木のつもりで実装してしまったが、よく読むと二分探索木だった。
Approach 1: Recursion
/**
* Definition for a binary tree node.
* class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
* var value: Int = _value
* var left: TreeNode = _left
* var right: TreeNode = _right
* }
*/
object Solution {
def searchBST(root: TreeNode, `val`: Int): TreeNode = {
if (root == null || root.value == `val`) return root
if (`val` < root.value) searchBST(root.left, `val`) else searchBST(root.right, `val`)
}
}
Approach 2: Iteration
/**
* Definition for a binary tree node.
* class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
* var value: Int = _value
* var left: TreeNode = _left
* var right: TreeNode = _right
* }
*/
object Solution {
def searchBST(root: TreeNode, `val`: Int): TreeNode = {
var head = root
while (head != null && head.value != `val`) {
if (`val` < head.value) head = head.left
else head = head.right
}
head
}
}
自分の実装
object Solution {
def getRow(rowIndex: Int): List[Int] = {
var dp = Array[Int](1)
for (x <- 1 to rowIndex) {
val newDp = new Array[Int](x + 1)
newDp(0) = 1
newDp(newDp.length - 1) = 1
for (y <- 1 until newDp.length - 1) {
newDp(y) = dp(y - 1) + dp(y)
}
dp = newDp
}
dp.toList
}
}
パスカルの三角形の特定の1行分を取得する。
最初、素直に各値を再帰的に取得するBrute ForceでやってみたがらTimeoutになったので、DPでやってみた。
リアルにサーモン
object Solution {
def fib(n: Int): Int = {
val cache = scala.collection.mutable.Map[Int, Int]()
def loop(nn: Int): Int = {
if (nn == 0) return 0
if (nn == 1) return 1
cache.getOrElseUpdate(nn, fib(nn - 1) + fib(nn - 2))
}
loop(n)
}
}
メモ化の項。フィボナッチ数を求める。
ボトムアップのメモ化やイテレーションで求めるやり方、数学的手法など解説されていたが実装は省略
リアルにサーモン
自分の実装
object Solution {
def climbStairs(n: Int): Int = {
if (n == 1) return 1
if (n == 2) return 2
var prev = 1
var cur = 2
for (x <- 3 to n) {
val tmp = cur
cur = cur + prev
prev = tmp
}
cur
}
}
Approach 2: Recursion with Memoization
object Solution {
def climbStairs(n: Int): Int = {
val memo = new Array[Int](n + 1)
def loop(s: Int): Int = {
if (n < s) return 0
if (s == n) return 1
if (0 < memo(s)) return memo(s)
val result = loop(s + 1) + loop(s + 2)
memo(s) = result
memo(s)
}
loop(0)
}
}
メモ化再帰。スタート地点側をインクリメントして範囲を狭めていくわけね。
リアルにサーモン
木の高さを求める問題。
以前解いたものだが、Solutionを読んで末尾再帰での実装をしてみる
Approach 2: Tail Recursion + BFS
/**
* Definition for a binary tree node.
* class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
* var value: Int = _value
* var left: TreeNode = _left
* var right: TreeNode = _right
* }
*/
object Solution {
def maxDepth(root: TreeNode): Int = {
if (root == null) return 0
var max = 1
val queue = scala.collection.mutable.Queue[(TreeNode, Int)]()
queue.enqueue((root, 0))
@scala.annotation.tailrec
def tailRec(): Int = {
if (queue.isEmpty) return max
val v = queue.dequeue
max = List(max, v._2 + 1).max
if (v._1.left != null) queue.enqueue((v._1.left, v._2 + 1))
if (v._1.right != null) queue.enqueue((v._1.right, v._2 + 1))
tailRec()
}
tailRec()
}
}
末尾再帰とは、自身の再帰呼び出しがそのメソッドの最後のステップになっているような再帰のこと。中間の状態を保存せずに最後の呼び出しをオリジナルへ返すことで計算できるため、言語によっては最適化が適用されスタックオーバーフローを防げる。
Scalaでは、関数定義の前に@scala.annotation.tailrecアノテーションをつけることでその関数が末尾再帰出ない場合はコンパイルエラーが出るようにすることができる。
関数内で自身の再帰呼び出しを複数回行っている場合も、中間状態を保持する必要が出てくるので末尾再帰にはならず末尾最適化も適用されない。
リアルにサーモン階乗を求める問題。
自分の実装
object Solution {
def myPow(x: Double, n: Int): Double = {
val xx = if (n < 0) 1 / x else x
val absN = if (n == Int.MinValue) Int.MaxValue - 1 else scala.math.abs(n) // 奇数偶数を合わせるために Int.MaxValue - 1
var ans = xx
@scala.annotation.tailrec
def go(nn: Int): Double = {
if (nn == 0) return 1
if (nn == 1) return ans
if (ans == 1) return 1
if (ans == -1) {
if (nn % 2 == 0) return 1
else return -1
}
ans = ans * xx
go(nn - 1)
}
go(absN)
}
}
ぱっと見単純そうに見えたが、やってみると考慮することが多くて意外と面倒だった。最初再帰を使わずにやろうとしたが、答えが1になってその後何乗しても変わらない場合に計算を中断してTimeLimitを逃れたりするために再帰に変更した。
また、scalaのInt.MinValueは-をつけたりscala.math.abs()を使っても符号反転できないことを知った。
Approach 2: Fast Power Algorithm Recursive
object Solution {
def myPow(x: Double, n: Int): Double = {
def fastPow(xx: Double, nn: Int): Double = {
if (nn == 0) return 1
if (nn == 1) return xx
val half = fastPow(xx, nn / 2)
if (nn % 2 == 0) half * half
else half * half * xx
}
val absN = if (n == Int.MinValue) Int.MaxValue - 1 else scala.math.abs(n)
val xxx = if (n < 0) 1 / x else x
fastPow(xxx, absN)
}
}
x^nを求めるためにx^n/2を求めて階乗していくことでO(logn)時間で求められるという手法。言われてみると当然だが気づけなかった。なるほど。
リアルにサーモン
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
if (l1 == null) return l2
if (l2 == null) return l1
if (l1.x < l2.x) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
}
解答済みの問題
リアルにサーモン
少し前に時かけて苦戦し、Solutionを見た記憶がある問題を一から実装 -> と思ったがSolutionがまだない問題だった。
0 -> 01、1 -> 10と変化していくn行目の数列の、k番目の数値を取得する。
object Solution {
def kthGrammar(N: Int, K: Int): Int = {
if (N == 1) return 0
if (N == 2) {
if (K == 1) return 0
else return 1
}
val prev = kthGrammar(N - 1, (K - 1) / 2 + 1)
if (K % 2 == 0) {
if (prev == 0) return 1
else return 0
} else {
if (prev == 0) return 0
else return 1
}
}
def conv(s: String) = {
s.split("").map(t => if (t == "0") "01" else "10").mkString("")
}
}
素直に数列を導き出して値を得る方針だと、膨大なサイズになってしまう。
n行目のk番目の数字は、n-1行目の(K - 1) / 2 + 1番目の数字から判定できる特性を利用して再帰関数を実装する。
リアルにサーモン
1からnまでの各数字をノードとしたユニークなBSTを全て返す。
自分の実装
/**
* Definition for a binary tree node.
* class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
* var value: Int = _value
* var left: TreeNode = _left
* var right: TreeNode = _right
* }
*/
object Solution {
def generateTrees(n: Int): List[TreeNode] = {
// イテレートしてrootを選択
// 残りを左右で再帰的にtreeにして、結合する
// 結果を追加していく
generateRangeTrees(1, n)
}
def generateRangeTrees(s: Int, e: Int): List[TreeNode] = {
if (s == e) return List(new TreeNode(s))
var result = scala.collection.mutable.ListBuffer[TreeNode]()
for (i <- s to e) {
val leftNodes = if (s < i) generateRangeTrees(s, i - 1) else List(null)
val rightNodes = if (i < e) generateRangeTrees(i + 1, e) else List(null)
leftNodes.foreach(ln => {
rightNodes.foreach(rn => {
val root = new TreeNode(i)
root.left = ln
root.right = rn
result += root
})
})
}
result.toList
}
}
各数字をrootとするパターンをイテレートし、BSTの性質を利用して再帰的にノードのリストを作成する。
Solutionを見たところほぼぴったり同じ実装だった。
One thing that can be improved is to introduce memorization. :)
メモイゼーションを使うと最適化できるとのコメント、なるほど。
リアルにサーモンこの章は一通り終わったので一旦close
このスクラップは2021/06/23にクローズされました