50. Pow(x, n)

Question:

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

Thinking:

通过二分法
- 如果是偶数，则pow(x, n /2) * pow(x, n /2)
- 如果是奇数， pow(x, n /2) * pow(x, n /2) * x 或者 pow(x, n /2) * pow(x, n /2) * （1/x）。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        if(strs == null || strs.length == 0) return result;
        Map<String, List<String>> m = new HashMap<>();
        for(String str : strs){
            char[] strArr = str.toCharArray();
            Arrays.sort(strArr);
            String cur = new String(strArr);
            if(!m.containsKey(cur)){
                List<String> temp = new ArrayList<String>();
                temp.add(str);
                m.put(cur, temp);
            }else{
                m.get(cur).add(str);
            }
        }
        result.addAll(m.values());
        return result;
    }
}

二刷

class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1D;
        double half = myPow(x, n / 2);
        return n % 2 == 0 ? half * half: n > 0 ? x * half * half : (1 / x) * half * half;
    }
}

Reference

50. Pow(x, n)