Code – 第78页

[swift] LeetCode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

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

func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
    if nums.isEmpty { return 0 }
    let sn = nums.sorted(by: >)
    return (k <= sn.count && k > 0) ? sn[k-1] : sn[0]
}

func findKthLargest(_ nums: [Int], _ k: Int) -> Int {

if nums.isEmpty { return 0 }

let sn = nums.sorted(by: >)

return (k <= sn.count && k > 0) ? sn[k-1] : sn[0]

}

[swift] LeetCode 206. Reverse Linked List

Reverse a singly linked list.

func reverseList(_ head: ListNode?) -> ListNode? {
    var stack = [Int](), p = head
    while let t = p {
        stack.append(t.val)
        p = t.next
    }
    p = head
    while let t = p {
        t.val = stack.popLast()!
        p = t.next
    }
    return head
}

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

var stack = [Int](), p = head

while let t = p {

stack.append(t.val)

p = t.next

}

p = head

while let t = p {

t.val = stack.popLast()!

p = t.next

}

return head

}

[swift] LeetCode 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

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

func rob(_ nums: [Int]) -> Int {
    if nums.count < 1 { return nums.first ?? 0 }
    var lm = 0, gm = 0
    for i in 0..<nums.count {
        let t = lm
        lm = gm
        gm = max(gm, t + nums[i])
    }

    return gm
}

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

if nums.count < 1 { return nums.first ?? 0 }

var lm = 0, gm = 0

for i in 0..<nums.count {

let t = lm

lm = gm

gm = max(gm, t + nums[i])

}

return gm

}

[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

}