LeetCode Recursion 2

Posted on Edited on Disqus: Word count in article: 9.1k Reading time ≈ 8 mins.

Sort an Array

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
28
29
30
31
class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        if nums.count < 2 { return nums }
        let i = nums.count/2, l = sortArray(Array(nums[..<i])), r = sortArray(Array(nums[i...]))
        return merge(l, r)
    }

    private func merge(_ n1: [Int], _ n2: [Int]) -> [Int] {
        var i1 = 0, i2 = 0
        var arr = [Int]()
        while i1 < n1.count, i2 < n2.count {
            if n1[i1] < n2[i2] {
                arr.append(n1[i1])
                i1 += 1
            } else {
                arr.append(n2[i2])
                i2 += 1
            }
        }
        while i1 < n1.count {
            arr.append(n1[i1])
            i1 += 1
        }
        while i2 < n2.count {
            arr.append(n2[i2])
            i2 += 1
        }

        return arr
    }
}

Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        return helper(root, Int.min, Int.max)
    }

    private func helper(_ node: TreeNode?, _ lower: Int, _ upper: Int) -> Bool {
        guard let n = node else { return true }

        if n.val <= lower || n.val >= upper {
            return false
        }

        return helper(n.left, lower, n.val) && helper(n.right, n.val, upper)
    }
}

Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let n = matrix.count-1, m = matrix.first?.count ?? 0; var i = n, j = 0
        while i >= 0 && j < m {
            if target > matrix[i][j] {
                j += 1
            } else if target < matrix[i][j] {
                i -= 1
            } else {
                return true
            }
        }
        return false
    }
}

N-Queens 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    func totalNQueens(_ n: Int) -> Int {
        if n < 1 { return 0 }
        return helper(n-1, Array(repeating: Array(repeating: 1, count: n), count: n)).count
    }

    private func helper(_ i: Int, _ board: [[Int]]) -> [[[Int]]] {
        if i == 0 { return put(i, board) }
        return helper(i-1, board).reduce( [[[Int]]]() ) { a, b in
            a + put(i, board)
        }
    }

    private func put(_ i: Int, _ board: [[Int]]) -> [[[Int]]] {
        var boards = [[[Int]]]()
        for j in 0..<board.count {
            if board[i][j] == 1 {
                let board = put((i,j), board)
                boards.append(board)
            }
        }
        return boards
    }

    private func put(_ p: (Int, Int), _ board: [[Int]]) -> [[Int]] {
        let n = board.count
        var board = board

        for i in 0..<n { board[i][p.1] = 0 }
        for j in 0..<n { board[p.0][j] = 0 }
        var p0 = p.0, p1 = p.1
        while p0 < n, p1 < n, p0 >= 0, p1 >= 0 {
            board[p0][p1] = 0
            p0 += 1; p1 += 1
        }
        p0 = p.0; p1 = p.1
        while p0 < n, p1 < n, p0 >= 0, p1 >= 0 {
            board[p0][p1] = 0
            p0 += 1; p1 -= 1
        }
        board[p.0][p.1] = 1

        return board
    }
}

Robot Room Cleaner

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
class Solution {
    func cleanRoom(_ robot: Robot) {
        var visited = Set<[Int]>()
        let directions = [[-1,0], [0,1], [1,0], [0,-1]]

        func backtrack(_ cell: [Int] = [0,0], _ d: Int = 0) {
            func goBack() {
                func uTurn() { robot.turnRight(); robot.turnRight() }
                uTurn(); robot.move(); uTurn()
            }

            visited.insert(cell)
            robot.clean()
            for i in 0..<4 {
                let d = (d+i)%4, cell = [cell[0]+directions[d][0], cell[1]+directions[d][1]]
                if !visited.contains(cell) && robot.move() {
                    backtrack(cell, d)
                    goBack()
                }
                robot.turnRight()
            }
        }

        backtrack()
    }
}

Sudoku Solver

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
28
class Solution {
    func solveSudoku(_ board: inout [[Character]]) {
        let chars: [Character] = ["1","2","3","4","5","6","7","8","9"]
        var boxes = Array(repeating: Array(repeating: Set<Character>(), count: 3), count: 3),  rows = (0..<9).map { Set(board[$0]) }, cols = (0..<9).map { i in Set( (0..<9).map { j in board[j][i] } )}
        (0..<9).forEach { i in (0..<9).forEach { j in boxes[i/3][j/3].insert(board[i][j]) } }

        func put(_ c: Character, _ i: Int, _ j: Int) {
            board[i][j] = c; rows[i].insert(c); cols[j].insert(c); boxes[i/3][j/3].insert(c)
        }
        func restore(_ c: Character, _ i: Int, _ j: Int) {
            board[i][j] = "."; rows[i].remove(c); cols[j].remove(c); boxes[i/3][j/3].remove(c)
        }
        func backtrack(_ k: Int = 0) -> Bool {
            let i = k/9, j = k%9
            if k >= 81 { return true }
            if board[i][j] != "." { return backtrack(k+1) }

            for c in chars.filter({ !rows[i].contains($0) && !cols[j].contains($0) && !boxes[i/3][j/3].contains($0) }) {
                put(c, i, j)
                if backtrack(k+1) { return true }
                restore(c, i, j)
            }
            return false
        }

        backtrack()
    }
}

Combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        if k > n { return [] }
        let b = (k...n).map { [$0] }
        if k == 1 { return b }

        let a = combine(n-1, k-1)
        var ans = [[Int]]()
        for i in a {
            for j in b {
                if let last = i.last, let first = j.first, last < first {
                    ans.append(i + j)
                }
            }
        }
        return ans
    }
}

Same Tree

1
2
3
4
5
6
7
8
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if let p = p, let q = q, p.val == q.val {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
        }
        return p == nil && q == nil
    }
}

Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var ans = [String]()
        func backtrack(_ s: String = "", _ l: Int = 0, _ r: Int = 0) {
            if s.count == n*2 {
                ans.append(s); return
            }
            if l < n { backtrack(s+"(", l+1, r) }
            if r < l { backtrack(s+")", l, r+1) }
        }
        backtrack()
        return ans
    }
}

Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
// iteratively
func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var ans = [Int]()
    var stack = [root]
    var p = root
    while p != nil || !stack.isEmpty {
        while let l = p {
            stack.append(l)
            p = l.left
        }
        
        if let n = stack.popLast() {
            ans.append(n.val)
            p = n.right
        }
    }
    return ans
}

Binary Tree Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
    var ans = [[Int]]()
    helper(root, 0, &ans)
    return ans
}

private func helper(_ root: TreeNode?, _ level: Int, _ ans: inout [[Int]]) {
    guard let root = root else { return }
    if level >= ans.count {
        ans.append( [root.val] )
    } else {
        ans[level].append(root.val)
    }
    
    helper(root.left, level+1, &ans)
    helper(root.right, level+1, &ans)
}
}

Convert Binary Search Tree to Sorted Doubly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
func treeToDoublyList(_ root: Node?) -> Node? {
    var first: Node?, last: Node?

    func helper(_ root: Node?) {
        guard let cur = root else { return }
        helper(cur.left)
        if let last = last {
            last.right = cur
            cur.left = last
        } else {
            first = cur
        }
        last = cur
        helper(cur.right)
    }

    helper(root)
    last?.right = first
    first?.left = last

    return first
}
}

Largest Rectangle in Histogram

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        func helper(_ i: Int, _ j: Int) -> Int {
            guard i <= j else { return 0 }
            var index = 0, v = Int.max
            for k in i...j {
                if heights[k] < v { index = k; v = heights[k] }
            }
            return max(v*(j-i+1), helper(i, index-1), helper(index+1, j))
        }
        return helper(0, heights.count-1)
    }
}

Permutations

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
    if nums.count < 2 { return [nums] }
    var ans = [[Int]]()
    for i in 0..<nums.count {
        var arr = nums; arr.remove(at: i)
        ans += permute(arr).map { [nums[i]] + $0 }
    }
    return ans
}
}

Letter Combinations of a Phone Number

1
2
3
4
5
6
7
8
9
class Solution {
    private let dict : [Character: [String]] = ["2":["a","b","c"],"3":["d","e","f"],"4":["g","h","i"],"5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]]

    func letterCombinations(_ digits: String) -> [String] {
        return digits.isEmpty ? [] : digits.reduce([""]) { (ans, digit) in
            ans.flatMap { s in dict[digit, default: [""]].map { c in s + c } }
        }
    }
}

The Skyline Problem

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
    let n = buildings.count
    if n == 0 { return [] }
    if n == 1 {
        return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]
    }
    
    let l = getSkyline(Array(buildings[..<(n/2)]))
    let r = getSkyline(Array(buildings[(n/2)...]))
    
    return merge(l, r)
}

private func merge(_ l: [[Int]], _ r: [[Int]]) -> [[Int]] {
    let ln = l.count, rn = r.count
    var lp = 0, rp = 0
    var curY = 0, lY = 0, rY = 0 , output = [[Int]]()
    
    
    func update(_ x: Int, _ y: Int) {
        if output.isEmpty || output.last?.first != x {
            output.append([x, y])
        } else {
            output[output.count-1][1] = y
        }
    }
    
    func append(_ p: Int, _ lst: [[Int]], _ n: Int, _ curY: Int) {
        var p = p, curY = curY
        while p < n {
            let (x, y) = (lst[p][0], lst[p][1])
            p += 1
            if curY != y {
                update(x, y)
                curY = y
            }
        }
    }
    
    
    while lp < ln && rp < rn {
        let lPoint = l[lp], rPoint = r[rp]
        
        var x = 0
        if lPoint[0] < rPoint[0] {
            (x, lY) = (lPoint[0], lPoint[1])
            lp += 1
        } else {
            (x, rY) = (rPoint[0], rPoint[1])
            rp += 1
        }
        
        let maxY = max(lY, rY)
        if curY != maxY {
            update(x, maxY)
            curY = maxY
        }
    }
    
    append(lp, l, ln, curY)
    append(rp, r, rn, curY)
    
    return output
}
}

Translated by gpt-3.5-turbo