LeetCode Recursion 1

Reverse String

1
2
3
4
5
class Solution {
func reverseString(_ s: inout [Character]) {
s.reverse()
}
}

Swap Nodes in Pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
}
}

Translated by gpt-3.5-turbo