Closed14

# Leetcode自分用解答メモ[Explore - Recursion I]

リアルにサーモン

leetcodeを説いていて、自分の回答とかsolutionを読んで実装したやつとか詰まったとことかメモしとく

チャプターごとにスクラップで記録して、終わったらアーカイブする。

リアルにサーモン

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で特パターン。

リアルにサーモン

/**
* class ListNode(_x: Int = 0, _next: ListNode = null) {
*   var next: ListNode = _next
*   var x: Int = _x
* }
*/
object Solution {
def swapPairs(head: ListNode): ListNode = {

}

}
}
}


### Approach 2: Iterative Approach

/**
* 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

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の分?)

リアルにサーモン

/**
* 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
}

dummy.next
}
}


### Approach #2 (Recursive) [Accepted]

/**
* class ListNode(_x: Int = 0, _next: ListNode = null) {
*   var next: ListNode = _next
*   var x: Int = _x
* }
*/
object Solution {
def reverseList(head: ListNode): ListNode = {

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 = {
while (head != null && head.value != val) {
if (val < head.value) head = head.left
}
}
}

リアルにサーモン

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行分を取得する。

リアルにサーモン

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)
}
}


メモ化再帰。スタート地点側をインクリメントして範囲を狭めていくわけね。

リアルにサーモン

### 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)時間で求められるという手法。言われてみると当然だが気づけなかった。なるほど。

リアルにサーモン

/**
* 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
}
}
}


リアルにサーモン

0 -> 011 -> 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
}
}


Solutionを見たところほぼぴったり同じ実装だった。

One thing that can be improved is to introduce memorization. :)
メモイゼーションを使うと最適化できるとのコメント、なるほど。

このスクラップは2021/06/23にクローズされました