Code – 第80页

[swift] LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidNode(root, Int.min, Int.max)
}

private func isValidNode(_ root: TreeNode?, _ min: Int, _ max: Int) -> Bool {
    guard let p = root else { return true }
    if p.val >= max || p.val <= min { return false }
    return isValidNode(p.left, min, p.val) && isValidNode(p.right, p.val, max)
}

func isValidBST(_ root: TreeNode?) -> Bool {

return isValidNode(root, Int.min, Int.max)

}

private func isValidNode(_ root: TreeNode?, _ min: Int, _ max: Int) -> Bool {

guard let p = root else { return true }

if p.val >= max || p.val <= min { return false }

return isValidNode(p.left, min, p.val) && isValidNode(p.right, p.val, max)

}

[swift] LeetCode 96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

func numTrees(_ n: Int) -> Int {
    list = Array(repeating: 1, count: n+1)
    if n >= 2 { list[2] = 2 }
    return g(n)
}

private var list: [Int]!
private func g(_ n: Int) -> Int {
    if  n > 2 && list[n] == 1 {
        list[n] = (1...n).reduce(0) { $0 + f($1, n) }
    }
    return list[n]
}

private func f(_ i: Int, _ n: Int) -> Int {
    return g(i-1) * g(n-i)
}

func numTrees(_ n: Int) -> Int {

list = Array(repeating: 1, count: n+1)

if n >= 2 { list[2] = 2 }

return g(n)

}

private var list: [Int]!

private func g(_ n: Int) -> Int {

if n > 2 && list[n] == 1 {

list[n] = (1...n).reduce(0) { $0 + f($1, n) }

}

return list[n]

}

private func f(_ i: Int, _ n: Int) -> Int {

return g(i-1) * g(n-i)

}

[swift] LeetCode 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var list = [Int](), stack = [TreeNode](), p = root

    while p != nil || !stack.isEmpty {
        if let t = p {
            stack.append(t)
            p = t.left
        } else {
            let t = stack.popLast()!
            list.append(t.val)
            p = t.right
        }
    }

    return list
}

func inorderTraversal(_ root: TreeNode?) -> [Int] {

var list = [Int](), stack = [TreeNode](), p = root

while p != nil || !stack.isEmpty {

if let t = p {

stack.append(t)

p = t.left

} else {

let t = stack.popLast()!

list.append(t.val)

p = t.right

}

return list

}

[swift] LeetCode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

func sortColors(_ nums: inout [Int]) {
    var i0 = 0, i1 = 0, i2 = nums.count-1
    while i1 <= i2 {
        if nums[i1] == 2 {
            nums.swapAt(i1, i2)
            i2 -= 1
        } else if nums[i1] == 0 {
            nums.swapAt(i0, i1)
            i0 += 1; i1 += 1
        } else {
            i1 += 1
        }
    }
}

func sortColors(_ nums: inout [Int]) {

var i0 = 0, i1 = 0, i2 = nums.count-1

while i1 <= i2 {

if nums[i1] == 2 {

nums.swapAt(i1, i2)

i2 -= 1

} else if nums[i1] == 0 {

nums.swapAt(i0, i1)

i0 += 1; i1 += 1

} else {

i1 += 1

}

[swift] LeetCode 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

func climbStairs(_ n: Int) -> Int {
    if n < 4 { return n }
    var arr = Array(repeating: 1, count: n+1)

    arr[2] = 2; arr[3] = 3
    for i in (4...n) {
        arr[i] = arr[i-1] + arr[i-2]
    }

    return arr[n]
}

func climbStairs(_ n: Int) -> Int {

if n < 4 { return n }

var arr = Array(repeating: 1, count: n+1)

arr[2] = 2; arr[3] = 3

for i in (4...n) {

arr[i] = arr[i-1] + arr[i-2]

}

return arr[n]

}

[swift] LeetCode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

func uniquePaths(_ m: Int, _ n: Int) -> Int {
    pathMatrix = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)
    return pathMatrix(m, n)
}

private var pathMatrix: [[Int]]!
private func pathMatrix(_ m: Int, _ n: Int) -> Int {
    if m <= 0 || n <= 0 { return 0 }
    if m < 2 || n < 2 { pathMatrix[m][n] = 1; return 1 }

    if pathMatrix[m-1][n] == 0 {
        pathMatrix[m-1][n] = pathMatrix(m-1, n)
    }
    if pathMatrix[m][n-1] == 0 {
        pathMatrix[m][n-1] = pathMatrix(m, n-1)
    }
    return pathMatrix[m-1][n] + pathMatrix[m][n-1]
}

func uniquePaths(_ m: Int, _ n: Int) -> Int {

pathMatrix = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)

return pathMatrix(m, n)

}

private var pathMatrix: [[Int]]!

private func pathMatrix(_ m: Int, _ n: Int) -> Int {

if m <= 0 || n <= 0 { return 0 }

if m < 2 || n < 2 { pathMatrix[m][n] = 1; return 1 }

if pathMatrix[m-1][n] == 0 {

pathMatrix[m-1][n] = pathMatrix(m-1, n)

}

if pathMatrix[m][n-1] == 0 {

pathMatrix[m][n-1] = pathMatrix(m, n-1)

}

return pathMatrix[m-1][n] + pathMatrix[m][n-1]

}