Math

[honghaoz]

Math [20/23]

❔	Title	Difficulty	Time	Space
✅	Add Binary	Easy	O(n)	O(n)
✅	Add Two Numbers	Medium	O(n)	O(1)
✅	Plus One	Easy	O(n)	O(1)
✅	Integer Break	Medium	O(logn)	O(1)
✅	Happy Number	Easy	O(n)	O(n)
✅	Single Number	Medium	O(n)	O(1)
✅	Ugly Number	Easy	O(logn)	O(1)
✅	Ugly Number II	Medium	O(n)	O(n)
✅	Super Ugly Number	Medium	O(n^2)	O(n)
✅	String to Integer (atoi)	Easy	O(n)	O(1)
✅	Pow(x, n)	Medium	O(logn)	O(1)
✅	Power of Two	Easy	O(1)	O(1)
❓	Power of Three	Easy	O(1)	O(1)
❓	Super Power	Medium	O(n)	O(1)
❓	Sum of Two Integers	Easy	O(n)	O(1)
✅	Reverse Integer	Easy	O(n)	O(1)
✅	Excel Sheet Column Number	Easy	O(n)	O(1)
✅	Integer to Roman	Medium	O(n)	O(1)
✅	Roman to Integer	Easy	O(n)	O(n)
✅	Rectangle Area	Easy	O(1)	O(1)
✅	Trapping Rain Water	Hard	O(n)	O(n)
✅	Container With Most Water	Medium	O(n)	O(1)
✅	Counting Bits	Medium	O(n)	O(n)

[honghaoz]

Add Binary

注意类型和Index，Character -> String -> Int!

class Solution {
    func addBinary(_ a: String, _ b: String) -> String {
        guard a.isEmpty == false else { return b }
        guard b.isEmpty == false else { return a }
        var a = [Character](a.characters).map { Int(String($0))! }
        var b = [Character](b.characters).map { Int(String($0))! }

        var res = ""
        var i = 0
        var c = 0
        while i < a.count || i < b.count {
            let ia = a.count - i - 1
            let ib = b.count - i - 1
            let na = 0 <= ia && ia < a.count ? a[ia] : 0
            let nb = 0 <= ib && ib < b.count ? b[ib] : 0
            let n = c + na + nb
            res.append(n % 2 == 0 ? "0" : "1")
            c = n > 1 ? 1 : 0
            i += 1
        }
        if c == 1 {
            res.append("1")
        }
        return String(res.characters.reversed())
    }
}

[honghaoz]

Add Two Numbers

ListNode 细节题

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard l1 != nil else { return l2 }
        guard l2 != nil else { return l1 }
        var p1 = l1
        var p2 = l2
        var carry = 0
        var pre = ListNode(0)
        var preHead = pre
        while p1 != nil && p2 != nil {
            let sum = p1!.val + p2!.val + carry
            let newNode = ListNode(sum % 10)
            pre.next = newNode
            pre = newNode
            carry = sum / 10
            p1 = p1?.next
            p2 = p2?.next
        }

        var p: ListNode?
        if p1 != nil { p = p1 }
        if p2 != nil { p = p2 }
        while p != nil {
            let sum = p!.val + carry
            let newNode = ListNode(sum % 10)
            pre.next = newNode
            pre = newNode
            carry = sum / 10
            p = p?.next
        }

        while carry != 0 {
            let newNode = ListNode(carry % 10)
            pre.next = newNode
            pre = newNode
            carry /= 10
        }

        return preHead.next
    }
}

[honghaoz]

Plus One

和linked list有点类似

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        guard digits.count > 0 else { return [] }
        var res = [Int]()
        var i = digits.count - 1
        var carry = 0
        while i >= 0 {
            var sum = digits[i] + carry
            if i == digits.count - 1 {
                sum += 1
            }
            res.append(sum % 10)
            carry = sum / 10
            i -= 1
        }

        while carry > 0 {
            res.append(carry % 10)
            carry = carry / 10
        }

        return Array(res.reversed())
    }
}

一个更好的方法

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var digits = digits
        var i = digits.count - 1
        while i >= 0 {
            if digits[i] < 9 {
                digits[i] += 1
                return digits
            }

            digits[i] = 0
            i -= 1
        }

        digits.insert(1, at: 0)
        return digits
    }
}

[honghaoz]

Integer Break

不知道怎么想出来的

class Solution {
    func integerBreak(_ n: Int) -> Int {
        var s = [Int : Int]()
        s[0] = 0
        s[1] = 1
        for i in 2...n {
            var mid = i / 2
            var mid2 = i - mid
            s[i] = max(s[mid]!, mid) * max(s[mid2]!, mid2)

            mid = i / 2 - 1
            mid2 = i - mid
            s[i] = max(max(s[mid]!, mid) * max(s[mid2]!, mid2), s[i]!)
        }
        return s[n]!
    }
}

[honghaoz]

Happy Number

Yelp面试过的问题。用一个set检查loop

class Solution {
    func isHappy(_ n: Int) -> Bool {
        var n = n
        var s = Set<Int>()
        s.insert(n)
        var ones = 0
        var tens = 0
        while n != 1 {
            var newN = 0
            while n != 0 {
                let ones = n % 10
                newN += ones * ones
                n /= 10
            }
            n = newN
            if s.contains(n) {
                return false
            } else {
                s.insert(n)
            }
        }
        return true
    }
}

https://discuss.leetcode.com/topic/12587/my-solution-in-c-o-1-space-and-no-magic-math-property-involved/2

class Solution {
    func isHappy(_ n: Int) -> Bool {
        var n = n
        var fast = n
        var slow = n
        repeat {
            slow = sumOfDigits(slow)
            if slow == 1 {
                return true
            }
            fast = sumOfDigits(fast)
            fast = sumOfDigits(fast)
        } while fast != slow
        return false
    }

    func sumOfDigits(_ n: Int) -> Int {
        var n = n
        var sum = 0
        while n != 0 {
            let ones = n % 10
            sum += ones * ones
            n /= 10
        }
        return sum
    }
}

[honghaoz]

Single Number

XOR

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        return nums.reduce(0) { return $0 ^ $1 }
    }
}

[honghaoz]

Ugly Number

class Solution {
    func isUgly(_ num: Int) -> Bool {
        guard num > 0 else { return false }
        var num = num

        while num != 1 {
            if num % 2 == 0 {
                num /= 2
            }
            else if num % 3 == 0 {
                num /= 3
            }
            else if num % 5 == 0 {
                num /= 5
            }
            else {
                return false
            }
        }
        return true
    }
}

[honghaoz]

Ugly Number II

nth ugly number must be min(x * 2, y * 3, z * 5), which x, y, z is previous ugly numbers.

class Solution {
    func nthUglyNumber(_ n: Int) -> Int {
        guard n > 0 else { return 0 }

        var uglyNumbers = [1]

        var t2 = 0 // 2
        var t3 = 0 // 3
        var t5 = 0 // 5

        var n = n
        while n > 1 {
            uglyNumbers.append(min(uglyNumbers[t2] * 2, uglyNumbers[t3] * 3, uglyNumbers[t5] * 5))
            if uglyNumbers.last == uglyNumbers[t2] * 2 {
                t2 += 1
            }
            if uglyNumbers.last == uglyNumbers[t3] * 3 {
                t3 += 1
            }
            if uglyNumbers.last == uglyNumbers[t5] * 5 {
                t5 += 1
            }
            n -= 1
        }
        return uglyNumbers.last!
    }
}

[honghaoz]

Super Ugly Number

是UglyNumber II 的延伸，不是很复杂

class Solution {
    func nthSuperUglyNumber(_ n: Int, _ primes: [Int]) -> Int {
        var s = [Int]()
        s.append(0)
        s.append(1) // s[1] -> 1
        if n == 1 { return s[1] }
        var t = Array(repeating: 1, count: primes.count)
        for i in 2...n {
            let next = zip(t, primes).map { s[$0] * $1 }.min()!
            s.append(next)
            for i in 0..<t.count {
                if s[t[i]] * primes[i] == next {
                    t[i] += 1
                }
            }
        }
        return s[n]
    }
}

[honghaoz]

String to Integer (atoi)

什么破题，纯是讨论各种奇葩input的题，没有什么编程技巧可言

class Solution {
    func myAtoi(_ str: String) -> Int {
        let str = [Character](str.characters)
        guard str.count > 0 else { return 0 }

        let intMax = Int(pow(Double(2), Double(32))) / 2 - 1
        let intMin = -(intMax + 1)

        var sign: Int?
        var sum = 0
        for i in 0..<str.count {
            let c = str[i]

            if let n = c.integer {
                if n == 0 && sum == 0 {
                    continue
                }
                else {
                    sum = sum * 10 + n
                }
            }
            else {
                if sum == 0 {
                    if c == "-" {
                        if sign != nil {
                            return sum * sign!
                        }
                        sign = -1
                        continue
                    }
                    if c == "+" {
                        if sign != nil {
                            return sum * sign!
                        }
                        sign = 1
                        continue
                    }
                    if c == " " && sign == nil { 
                        continue 
                    }
                }

                return (sign ?? 1) * sum   
            }

            if sum >= intMax {
                if sign == -1 {
                    return -min(-intMin, sum)
                } else {
                    return intMax
                }
            }
        }
        return (sign ?? 1) * sum
    }
}

extension Character {
    var integer: Int? {
        switch self {
            case "0": return 0
            case "1": return 1
            case "2": return 2
            case "3": return 3
            case "4": return 4
            case "5": return 5
            case "6": return 6
            case "7": return 7
            case "8": return 8
            case "9": return 9
            default: return nil
        }
    }
}

[honghaoz]

Pow(x, n)

没有仔细做，copy的别人的。基本上是把x 和 n先查查0 1 边界条件，然后求abs的pow结果。然后在处理x正负以及n为奇偶的特殊情况

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        guard x != 0 else { return 0 }
        guard n != 0 else { return 1 }

        var res = _helper(abs(x), abs(n))
        if n < 0 {
            return 1 / res
        }
        if n % 2 != 0 && x < 0 {
            res = -res
        }
        return res
    }

    private func _helper(_ x: Double, _ n: Int) -> Double {
        guard n != 0 else { return 1 }
        guard n != 1 else { return x }

        if n % 2 == 0 {
            return _helper(x * x, n / 2)
        } else {
            return _helper(x, n - 1) * x
        }
    }
}

[honghaoz]

Power of Two

错位求与。如果是0则是2的power

class Solution {
    func isPowerOfTwo(_ n: Int) -> Bool {
        guard n > 0 else {
            return false
        }

        return n & (n - 1) == 0
    }
}

[honghaoz]

Power of Three

一个奇葩的题目，完全没有必要去做

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        // var n = n
        // if n > 1 {
        //     while n % 3 == 0 { n = n / 3 }
        // }
        // return n == 1

        // return n > 0 && (n == 1 || (n % 3 == 0 && isPowerOfThree(n / 3)))

        // return n > 0 && (1162261467 % n == 0)

        guard n > 0 else {
            return false
        }

        return 1162261467 % n == 0
    }
}

[honghaoz]

Sum of Two Integers

不懂啊不懂啊

[honghaoz]

Reverse Integer

想不明白为什么要考虑 Int.max?

class Solution {
    func reverse(_ x: Int) -> Int {
        var x = x
        var res = 0
        while x != 0 {
            let d = x % 10
            res = res * 10 + d
            x /= 10
            if res > Int(Int32.max) || res < Int(Int32.min) {
                return 0
            }
        }
        return res
    }
}

[honghaoz]

Excel Sheet Column Number

就是26进制

class Solution {
    func titleToNumber(_ s: String) -> Int {
        var res = 0
        var s = [Character](s.characters)
        while s.count > 0 {
            let lastNum = s.first!.ascii! - Int("A".unicodeScalars.first!.value) + 1
            res = res * 26 + lastNum
            s.removeFirst()
        }
        return res
    }
}

extension Character {
    var ascii: Int? {
        guard let val = String(self).unicodeScalars.first?.value else { return nil }
        return Int(val)
    }
}

[honghaoz]

Integer to Roman

基本思路是从大到小，查看倍数

class Solution {
    func intToRoman(_ num: Int) -> String {
        let nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        let symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        var num = num
        var res = ""
        var i = 0
        while num > 0 {
            let current = num / nums[i]
            for _ in 0..<current {
                res += symbols[i]
            }
            num -= current * nums[i]
            i += 1
        }
        return res
    }
}

[honghaoz]

Roman to Integer

Iterate from end to start, because there's at most one "I" on "V", and for "XIV", I belongs to IV

class Solution {
    func romanToInt(_ s: String) -> Int {
        let dict = initDict()
        let chars = [Character](s.characters.reversed())
        var res = 0

        for i in 0 ..< chars.count {
            guard let current = dict[String(chars[i])] else {
                return res
            }
            if i > 0 && current < dict[String(chars[i - 1])]! {
                res -= current
            } else {
                res += current
            }
        }

        return res
    }

    private func initDict() -> [String: Int] {
        var dict = [String: Int]()

        dict["I"] = 1
        dict["V"] = 5
        dict["X"] = 10
        dict["L"] = 50
        dict["C"] = 100
        dict["D"] = 500
        dict["M"] = 1000

        return dict
    }
}

[honghaoz]

Rectangle Area

class Solution {
    func computeArea(_ A: Int, _ B: Int, _ C: Int, _ D: Int, _ E: Int, _ F: Int, _ G: Int, _ H: Int) -> Int {
        let w1 = C - A
        let h1 = D - B
        let area1 = w1 * h1

        let w2 = G - E
        let h2 = H - F
        let area2 = w2 * h2

        // A C E G
        // B D F H
        let w = max(min(C, G) - max(A, E), 0)
        let h = max(min(D, H) - max(B, F), 0)
        let overlaps = w * h

        return area1 + area2 - overlaps
    }

    // func computeArea(A: Int, _ B: Int, _ C: Int, _ D: Int, _ E: Int, _ F: Int, _ G: Int, _ H: Int) -> Int {
       // var magicA = A - E
       // var magicB = G - C

       // if magicA < 0 && magicB < 0 {
       //   magicA *= -1
       //   magicB *= -1
    //  }

    //  let width = max((G - E) + (C - A) - max((G - A), (C - E)) - max(min(magicA, magicB), 0), 0)

    //  magicA = B - F
    //  magicB = H - D

       // if magicA < 0 && magicB < 0 {
       //   magicA *= -1
       //   magicB *= -1
    //  }

    //  let height = max((H - F) + (D - B) - max((H - B), (D - F)) - max(min(magicA, magicB), 0), 0)

       // return (C - A) * (D - B) + (G - E) * (H - F) - width * height
    // }
}

[honghaoz]

Trapping Rain Water

Divide and Conquer

class Solution {
    func trap(_ height: [Int]) -> Int {
        return trap(height, 0, height.count)
    }

    func trap(_ height: [Int], _ from: Int, _ to: Int) -> Int {
        if to - from <= 2 { return 0 }
        var maxIndex = -1
        for i in from..<to {
            if maxIndex == -1 { 
                maxIndex = i
                continue
            }

            if height[i] > height[maxIndex] {
                maxIndex = i
            }
        }

        if maxIndex == from {
            // Find adjacent maxIndex
            var nextMaxIndex = -1 // nextMax <= max
            for i in (maxIndex + 1)..<to {
                if nextMaxIndex == -1 {
                    nextMaxIndex = i
                    continue
                }

                if height[i] > height[nextMaxIndex] {
                    nextMaxIndex = i
                }
            }

            // Cal water trap between from to nextMaxIndex
            var water = 0
            for i in (maxIndex + 1)..<nextMaxIndex {
                water += height[nextMaxIndex] - height[i]
            }
            return water + trap(height, nextMaxIndex, to)
        }
        else if maxIndex == to - 1 {
            var preMaxIndex = -1
            for i in stride(from: maxIndex - 1, to: from - 1, by: -1) {
                if preMaxIndex == -1 {
                    preMaxIndex = i
                    continue
                }

                if height[i] > height[preMaxIndex] {
                    preMaxIndex = i
                }
            }

            var water = 0
            for i in (preMaxIndex + 1)..<maxIndex {
                water += height[preMaxIndex] - height[i]
            }
            return water + trap(height, from, preMaxIndex + 1)
        }
        else {
            return trap(height, from, maxIndex + 1) + trap(height, maxIndex, to)
        }
    }
}

[honghaoz]

Container With Most Water

左右荚逼

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        if height.count <= 1 { return 0 }

        var left = 0
        var right = height.count - 1
        var res = min(height[left], height[right]) * (right - left)
        while left < right {
            if height[left] < height[right] {
                left += 1
            }
            else {
                right -= 1
            }

            let newSize = min(height[left], height[right]) * (right - left)
            res = max(res, newSize)
        }
        return res
    }
}

[honghaoz]

Counting Bits

class Solution {
    func countBits(_ num: Int) -> [Int] {
        let originalNum = num
        var num = num
        var bits = [0, 1]

        // 0 -> [0, 1]
        // 1 -> [0, 1, 1, 2]
        // 2 -> [0, 1, 1, 2, ...]
        // 3 -> 
        while num != 0 {
            bits = bits + bits.map { $0 + 1 }
            num /= 2
        }

        var res = [Int]()
        for i in 0...originalNum {
            res.append(bits[i])
        }

        return res
    }
}