Swift – 第5页 – 柳婼の blog

[swift] LeetCode 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

var v = 0, res = 0
var dict = [Int: Int]()
nums.forEach {
    var t = 1
    if let n = dict[$0] {
        t = n + 1
    }

    if t > v {
        res = $0
        v = t
    }
    dict[$0] = t
}

return res

var v = 0, res = 0

var dict = [Int: Int]()

nums.forEach {

var t = 1

if let n = dict[$0] {

t = n + 1

}

if t > v {

res = $0

v = t

}

dict[$0] = t

}

return res

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