LeetCode Recursion 1

Reverse String

class Solution {
    func reverseString(_ s: inout [Character]) {
        s.reverse()
    }
}

Swap Nodes in Pairs

class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        let h = swap(head)
        h?.next?.next = swapPairs(h?.next?.next)
        return h
    }

    private func swap(_ head: ListNode?) -> ListNode? {
        if let h0 = head, let h1 = h0.next {
            h0.next = h1.next
            h1.next = h0
            return h1
        } else {
            return head
        }
    }
}

Reverse Linked List

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil, cur = head
        while cur != nil {
            let p = cur?.next
            cur?.next = prev
            prev = cur
            cur = p
        }
        return prev
    }
}

Search in a Binary Search Tree

class Solution {
    func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        guard let root = root else { return nil }
        if root.val == val { return root }
        if val < root.val {
            return searchBST(root.left, val)
        } else {
            return searchBST(root.right, val)
        }
    }
}

Pascal’s Triangle II

class Solution {
    func getRow(_ rowIndex: Int) -> [Int] {
        var arr = [1], j = 0
        for _ in 0..<rowIndex {
            arr.append(1)
            j = arr.count - 2
            while j > 0 {
                arr[j] += arr[j-1]
                j -= 1
            }
        }
        return arr
    }
}

Fibonacci Number

class Solution {
    var arr = Array(repeating: 0, count: 31)
    func fib(_ N: Int) -> Int {
        arr[1] = 1
        if N < 2 || arr[N] != 0 {
            return arr[N]
        } else {
            arr[N-1] = fib(N-1)
            return arr[N-1] + arr[N-2]
        }
    }
}

Climbing Stairs

class Solution {
    var arr = [0,1,2,3] + Array(repeating: 0, count: 127)
    func climbStairs(_ n: Int) -> Int {
        if n < 4 || arr[n] != 0 {
            return arr[n]
        } else {
            arr[n-1] = climbStairs(n-1)
            return arr[n-1] + arr[n-2]
        }
    }
}

Maximum Depth of Binary Tree

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        return 1 + max(maxDepth(root.left), maxDepth(root.right))
    }
}

Pow(x, n)

class Solution {

    func myPow(_ x: Double, _ n: Int) -> Double {
        var dic = [Int:Double
        dic[-1] = 1/x; dic[0] = 1; dic[1] = x

        return fastPow(x, n, &dic)
    }


    func fastPow(_ x: Double, _ n: Int, _ arr: inout [Int:Double]) -> Double {
        if let v = arr[n] { return v }

        let l = n / 2, r = n - l

        if arr[l] == nil {
            arr[l] = fastPow(x, l, &arr)
        }
        if arr[r] == nil {
            arr[r] = fastPow(x, r, &arr)
        }

        return arr[l]! * arr[r]!
    }
}

Merge Two Sorted Lists

class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard let p1 = l1 else { return l2 }
        guard let p2 = l2 else { return l1 }

        let (p, q) = p1.val <= p2.val ? (p1, p2) : (p2, p1)
        p.next = mergeTwoLists(p.next, q)
        return p
    }
}

K-th Symbol in Grammar

class Solution {
    func kthGrammar(_ N: Int, _ K: Int) -> Int {
        if N < 2 { return 0 }
        return (kthGrammar(N-1, (K+1)/2) == 0) ? 1-K%2 : K%2
    }
}

Unique Binary Search Trees II

class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        if n < 1 { return [] }
        return helper(1, n)
    }

    private func helper(_ i1: Int, _ i2:Int) -> [TreeNode?] {
        if i1 > i2 { return [nil] }

        var tn = [TreeNode
        for i in i1...i2 {
            let l = helper(i1, i-1)
            let r = helper(i+1, i2)

            for li in l {
                for ri in r {
                    let n = TreeNode(i)
                    n.left = li
                    n.right = ri
                    tn.append(n)
                }
            }
        }

        return tn
    }
}