LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 快速幂

3 ^ 10 = 3 ^ 5 * 3 ^ 5
3 ^ 5 = 3 ^ 2 * 3 ^ 2 * 3
3 ^ 2 = 3 ^ 1 * 3 ^ 1
3 ^ 1 = 3 ^ 0 * 3 ^ 0 * 3

• 实现如下

double myPow(double x, int n) {
  if (!n) {
    return 1.0;
  }
  double t = myPow(x, n / 2);
  return n % 2 & 1 ? t * t * x : t * t;
}

• 此外要考虑指数为负数的情况，对此把底数转为倒数，再把指数转为正数即可。这里要考虑一个边界情况，即 INT_MIN（32 位为 -2 ^ 32）的相反数比 INT_MAX（32 位为 2 ^ 32 - 1）大，直接取反将溢出。对于负数，先加 1，再取反即可防溢出，最后需要多乘一次底数

class Solution {
 public:
  double myPow(double x, int n) {
    double t = 1;
    if (n < 0) {
      x = 1 / x;
      t = x;
      n = -(n + 1);
    }
    return t * helper(x, n);
  }

  double helper(double x, int n) {
    if (!n) {
      return 1.0;
    }
    double t = helper(x, n / 2);
    return n % 2 & 1 ? t * t * x : t * t;
  }
};