Swift刷题打卡，不能再颓了

// 16. 3Sum Closest

/*Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).*/

func closet3Sum(_ nums: [Int], _ target: Int) -> Int {
    var ans = 0, abs = Int.max
    let sorted = nums.sorted()
    for i in 0..<sorted.count {
        var left = i + 1, right = sorted.count - 1
        while left < right {
            let sum = sorted + sorted[left] + sorted[right]
            if sum > target {
                if sum - target < abs {
                    abs = sum - target
                    ans = sum
                }
                right -= 1
            } else if sum < target {
                if target - sum < abs {
                    abs = target - sum
                    ans = sum
                }
                left += 1
            } else {
                return target
            }
        }
    }
    return ans
}

closet3Sum([-1, 2, 1, -4], 1)

// 142. Linked List Cycle II
func findLinkedListStart(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return nil
    }
    var fast = head, slow = head
    while fast?.next != nil && fast?.next?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow == fast {
            fast = head
            while fast != slow {
                fast = fast?.next
                slow = slow?.next
            }
            return slow
        }
    }
    return nil
}

// 85. Maximal Rectangle
/*Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6*/

func maximalRectangle(_ matrix: [[Character]]) -> Int {
    guard matrix.count > 0 && matrix[0].count > 0 else {
        return 0
    }
    var result = 0
    let M = matrix.count, N = matrix[0].count
    let matrix = [Array(repeating: 0, count: N)] + matrix.map { $0.map { ($0 == "1") ? 1 : 0 } }
    var dpH = Array(repeating: Array(repeating: 0, count: N), count: M + 1)
    var dpL = dpH
    var dpR = dpH.map { $0.map { _ in N - 1} }
    for i in 1...M {
        // get heights
        for j in 0..<N where matrix[i][j] == 1 {
            dpH[i][j] = dpH[i - 1][j] + matrix[i][j]
        }
        // get left edges
        for j in 0..<N where matrix[i][j] == 1 {
            dpL[i][j] = (j == 0 || matrix[i][j - 1] == 0 ? j : dpL[i][j - 1])
        }
        for j in 0..<N where matrix[i][j] == 1 {
            dpL[i][j] = max(dpL[i][j], dpL[i - 1][j])
        }
        // get right edges
        for j in (0..<N).reversed() where matrix[i][j] == 1 {
            dpR[i][j] = (j == N - 1 || matrix[i][j + 1] == 0) ? j : dpR[i][j + 1]
        }
        for j in (0..<N).reversed() where matrix[i][j] == 1 {
            dpR[i][j] = min(dpR[i][j], dpR[i-1][j])
        }
        // calculate
        for j in 0..<N where matrix[i][j] == 1 {
            let l = dpL[i][j], r = dpR[i][j], h = dpH[i][j]
            result = max(result, (r - l + 1) * h)
        }
    }
    return result
}
maximalRectangle([["1", "1", "1"],["1", "1", "1"],["1", "0", "1"]])

/* 273. Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"
Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
*/
'''class Solution {
    let ones = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
let tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
func numberToWords(_ num: Int) -> String {
    var result = ""
    numberToWordsHelper(num, &result)
    return result
}
func numberToWordsHelper(_ num: Int, _ result : inout String) {
    if num < 0 {
        result.append("Minus ")
        numberToWordsHelper(-num, &result)
    } else if num >= 1000000000 {
        numberToWordsHelper(num/1000000000, &result)
        result.append(" Billion")
        let remainder = num % 1000000000
        if remainder > 0 {
            result.append(" ")
            numberToWordsHelper(remainder, &result)
        }
    } else if num >= 1000000 {
        numberToWordsHelper(num/1000000, &result)
        result.append(" Million")
        let remainder = num % 1000000
        if remainder > 0 {
            result.append(" ")
            numberToWordsHelper(remainder, &result)
        }
    } else if num >= 1000 {
        numberToWordsHelper(num/1000, &result)
        result.append(" Thousand")
        let remainder = num % 1000
        if remainder > 0 {
            result.append(" ")
            numberToWordsHelper(remainder, &result)
        }
    } else if num >= 100 {
        numberToWordsHelper(num/100, &result)
        result.append(" Hundred")
        let remainder = num % 100
        if remainder > 0 {
            result.append(" ")
            numberToWordsHelper(remainder, &result)
        }
    } else if num >= 20 {
        result.append(tens[num/10])
        let remainder = num % 10
        if remainder > 0 {
            result.append(" ")
            numberToWordsHelper(remainder, &result)
        }
    } else {
        result.append(ones[num])
    }
}
}