Code – 第79页

[swift] LeetCode 121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

func maxProfit(_ prices: [Int]) -> Int {
    if prices.count < 2 { return 0 }

    var p = prices[0], m = 0
    for i in 1..<prices.count {
        m = max(m, prices[i] - p)
        p = min(p, prices[i])
    }
    return m
}

func maxProfit(_ prices: [Int]) -> Int {

if prices.count < 2 { return 0 }

var p = prices[0], m = 0

for i in 1..<prices.count {

m = max(m, prices[i] - p)

p = min(p, prices[i])

}

return m

}

[swift] LeetCode 114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

/ \

2 5

/ \ \

3 4 6

The flattened tree should look like:

func flatten(_ root: TreeNode?) {
    if let p = root {
        flatten(p.left)
        flatten(p.right)
        if let l = p.left {
            if let r = p.right {
                var lr = l
                while lr.right != nil {
                    lr = lr.right!
                }
                lr.right = r
            }
            p.right = l
            p.left = nil
        }
    }
}

func flatten(_ root: TreeNode?) {

if let p = root {

flatten(p.left)

flatten(p.right)

if let l = p.left {

if let r = p.right {

var lr = l

while lr.right != nil {

lr = lr.right!

}

lr.right = r

}

p.right = l

p.left = nil

}

[swift] LeetCode 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

return root == nil ? 0 : 1 + max(maxDepth(root?.left), maxDepth(root?.right))

1	return root == nil ? 0 : 1 + max(maxDepth(root?.left), maxDepth(root?.right))

[swift] LeetCode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }

    var q = [TreeNode](), lists = [[Int]]()
    q.append(root)

    while !q.isEmpty {
        lists.append(q.map { $0.val })

        q = q.reduce([]) { l, t in
            l + [t.left, t.right]
            }.compactMap({$0})
    }

    return lists
}

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

guard let root = root else { return [] }

var q = [TreeNode](), lists = [[Int]]()

q.append(root)

while !q.isEmpty {

lists.append(q.map { $0.val })

q = q.reduce([]) { l, t in

l + [t.left, t.right]

}.compactMap({$0})

}

return lists

}

[swift] LeetCode 101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.

func isSymmetricTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    if let p = p, let q = q {
        return p.val == q.val && isSymmetricTree(p.left, q.right) && isSymmetricTree(p.right, q.left)
    } else {
        return p == nil && q == nil
    }
}

func isSymmetric(_ root: TreeNode?) -> Bool {
    return isSymmetricTree(root?.left, root?.right)
}

func isSymmetricTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {

if let p = p, let q = q {

return p.val == q.val && isSymmetricTree(p.left, q.right) && isSymmetricTree(p.right, q.left)

} else {

return p == nil && q == nil

}

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

return isSymmetricTree(root?.left, root?.right)

}

[swift] LeetCode 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

if let p = p, let q = q {
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
} else {
    return p == nil && q == nil
}

if let p = p, let q = q {

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

} else {

return p == nil && q == nil

}