LeetCode – 50. Pow(x, n)

題目連結: https://leetcode.com/problems/powx-n/

參考解法:

https://leetcode.com/problems/powx-n/discuss/270236/Swift-100-Optimized-O(logN)-recursive-binary-search-solution

https://leetcode.com/problems/powx-n/discuss/1356015/Swift%3A-Pow(x-n)-%2B-Test-Cases

法ㄧ(Recursive):

func myPow(_ x: Double, _ n: Int) -> Double {
    return n > 0 ? helper(x, n) : 1 / helper(x, n)
}

func helper(_ x: Double, _ n: Int) -> Double {
    if x == 0 { return 0 }
    else if x == 1 { return 1 }
    else if n == 0 { return 1 }
    else if x == -1 {
        return n % 2 == 0 ? 1 : -1
    } else {
        if n % 2 == 0 { return helper(x*x, n / 2) }
        else { return helper(x*x, n / 2) * x }
    }
}

法二(Iterative):

func myPow(_ x: Double, _ n: Int) -> Double {
    if x == 0 || x == 1 { return x }
    else if n == 0 { return 1 }
    else if x == -1 {
        return n % 2 == 0 ? 1 : -1
    } else {
        var result: Double = 1
        var x = x
        var num = abs(n)
        while num > 0 {
            if num % 2 != 0 { result = result * x }
            num = num / 2
            x *= x
        }
        return n > 0 ? result : 1 / result
    }
}

法三(Iterative): (p.s. 在極端case會產生time limit exceeded)

func myPow(_ x: Double, _ n: Int) -> Double {
    if x == 0 || x == 1 { return x }
    else if n == 0 { return 1 }
    else if x == -1 {
        return n % 2 == 0 ? 1 : -1
    } else {
        var result: Double = 1
        let num = abs(n)
        for _ in 0 ..< num {
            result *= x
        }
        return n > 0 ? result : 1 / result
    }
}