柳婼の blog – 第79页 – 我不管，反正我最萌～

[swift] LeetCode 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

func maxProduct(_ nums: [Int]) -> Int {
    if nums.isEmpty { return 0 }
    var gm = nums[0], lmax = nums[0], lmin = nums[0], i = 1
    while i < nums.count {
        let t = [lmax * nums[i], nums[i], lmin * nums[i]]
        lmin = t.min()!
        lmax = t.max()!
        gm = max(lmax, gm)
        i += 1
    }

    return gm
}

func maxProduct(_ nums: [Int]) -> Int {

if nums.isEmpty { return 0 }

var gm = nums[0], lmax = nums[0], lmin = nums[0], i = 1

while i < nums.count {

let t = [lmax * nums[i], nums[i], lmin * nums[i]]

lmin = t.min()!

lmax = t.max()!

gm = max(lmax, gm)

i += 1

}

return gm

}

[swift] LeetCode 148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

1 2	Input: 4->2->1->3 Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

1 2	Input: -1->5->3->4->0 Output: -1->0->3->4->5

func sortList(_ head: ListNode?) -> ListNode? {
    var arr = Array(repeating: 0, count: 256*128)
    var i = 0, p = head
    while let q = p {
        arr[i] = q.val
        p = q.next; i += 1
    }
    arr = Array(arr[..<i]).sorted()

    p = head; i = 0
    while let q = p {
        q.val = arr[i]
        p = q.next; i += 1
    }

    return head
}

func sortList(_ head: ListNode?) -> ListNode? {

var arr = Array(repeating: 0, count: 256*128)

var i = 0, p = head

while let q = p {

arr[i] = q.val

p = q.next; i += 1

}

arr = Array(arr[..<i]).sorted()

p = head; i = 0

while let q = p {

q.val = arr[i]

p = q.next; i += 1

}

return head

}

[swift] LeetCode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

return nums.reduce(0) { $0 ^ $1 }

1	return nums.reduce(0) { $0 ^ $1 }

[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))