LeetCode Recursion 2

发表于 更新于 Disqus： 本文字数： 9k 阅读时长 ≈ 8 分钟

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

    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
class Solution {
    // iteratively
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var ans = [Int
        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
67
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
    }
}