Pow(x, n)、两数相除、分数到小数和x的平方根

pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

方法一 二分法

思路

看到题目首先想到可以用暴力计算，如果 $n$ 为整数，则做 $n$ 次底数 $x$的累乘，如果 $n$ 为负数，则做 $n$ 次 底数($1 / x$) 的累乘，于是有了如下代码：

function myPow (x, n) {
  // 考虑 n 为 0 的边界情况
  if (n === 0) {
      return 1;
  }
​
  const base = n > 0 ? x : 1 / x; // 通过正负号，确认参与幂运算的底数
  let result = 1;
​
  for (let i = 1; i <= Math.abs(n); i++) {
    result *= base;
  }
​
  return result;
};

但是暴力计算会在指数较大时超时，这时我们发现比如计算 $2^{20}，2^{20} = 2^{10}*2^{10}$，我们使用分治法，只需要计算出 $2^{10}$ 的值做相乘，便可以得出 $2^{20}$ 的值。 那么计算 $2^{10 }$的值，又可以拆解为 $2^5* 2^5$，以此类推……

详解

我们可以使用折半计算，每次把 n 缩小一半，通过递归，最终获取 $x$ 的 $n$ 次幂，递推公式如下：

​$x^n = x^{n / 2} x^{n / 2}$(当 $n$ 为偶数时)

​$x^n = x^{n / 2} + x^{n / 2}$ (当 $n$为 奇数时)

1. 边界情况：当 $n$ 为 0 时，返回 1，当$n$ 为 1 或者 -1 时 分别返回 $x$与 $1 / x$​

2. 其他情况：当 $n$ 为奇数时，需要多乘一次 $x$ 的值

判断 $n$ 是正数还是负数，如果是正数，则直接以 $x$ 作为底数计算；如果是负数，则以 $1 / x$ 作为底数计算。

代码

function myPow (x, n) {
  // 考虑 n 为 0, 1, -1 的边界情况
  if (n === 0) {
      return 1;
  } else if (n === 1) {
      return x;
  } else if (n === -1) {
      return 1 / x;
  }
​
  const base = n > 0 ? x : 1 / x; // 通过正负号，确认参与幂运算的底数
  const half = parseInt(n / 2, 10); // 将 n 的值缩小一半
  const result = myPow(x, half); // 保存折半计算的值，避免重复计算
​
  if (n % 2) { // 如果 n 是奇数，则需要额外乘以一次底数
    return base * result * result;
  }
  // 如果 n 是偶数，则直接返回折半计算的乘积
  return result * result;
};

复杂度分析

• 时间复杂度：$O(\log_2n)$​

  每次递归时，指数 $n$ 减小一半，即 $n, n/2, n/4, .... n/2^k$，最终趋近于1，令 $n/2^k = 1$，计算得出计算次数 $k = log2 n$，所以时间复杂度为 $O(\log_2n)$。

• 空间复杂度：$O(\log_2n)$​

  每一次递归计算，都需要变量保存底数、下一次计算的幂值以及每次递归计算的结果三个常量，递归深度为 $\log_2n$，所以空间复杂度为 $\log_2n$。

方法二 快速幂

思路

我们继续在指数 n 上做文章，将 n 看做数列之和，使得 $n = a_1 + a_2 + ... + a_n$；

那么由 $x^{(a + b)} = x^a x^b$，可得 $x^n = x^a1 x^a2 ... x^an$；如果能够快速计算出 $x^ai$ 的值，那么即可求得 $x^n$。

详解

有了以上分析，我们可以通过对幂值进行分解来简化计算，例如：

当 $n = 13$时，可转化为二进制表示法：1101，那么 $13 = 2 ^ 3 + 2 ^ 2 + 2 ^ 0$，即：

​$x^n = x^{2^3} x^{2^2} x^{2^0}$；

二进制： 1    1    0    1
权重：  x^8  x^4  x^2  x^1

可通过移位运算，当该位不为 0 时，乘以对应位上的权重，循环累乘，得到最终计算结果，对应位上的权重则可以通过低位的权重计算所得，如：

x^1 = x;
x^2 = (x^1) * (x^1);
x^4 = (x^2) * (x^2);
x^8 = (x^4) * (x^4)。

我们拿 $x = 5，n = 13$ 举例，需要进行 $log_2 13$ 次计算，即 4 次计算。

将 13 转化为二进制表示法，对应值为 1101，使用 result 来保存计算中间值，使用 base 来保存计算到第 i 位需要乘的权重

result 初始位 1，base 初始值为 $5^1$​

1. 第一轮：从低位取数 13 & 1 = 1，$result = result * base = 1 5^1$，更新 base 的值: base *= base 即 base 为 $5^2$​

2. 第二轮：13 右移 1 位后二进制表示为 110，(13 >> 1) & 1 = 0，则跳过不予计算 result，更新 base 的值: base *= base 即 base 为 $5^4$​

3. 第三轮：13 右移 2 位后二进制表示为 11，(13 >> 2) & 1 = 1，result = result base = 5^1 5^4，更新 base 的值: base *= base 即 base 为 $5^8$​

4. 第四轮：13 右移 3 位后二进制表示为 1，(13 >> 3) & 1 = 1， $result = result base = 5^1* 5^4 * 5^8$

移位运算完毕，得到最终结果 $result = 5^1 *5^4 *5^8 = 5^(1 + 4 + 8) = 5^13$。

代码

function myPow (x, n) {
  if (n === 0) {
    return 1;
  } else if (n === 1) {
    return x;
  } else if (n === -1) {
    return 1 / x;
  }
​
  let pow = Math.abs(n); // 取幂值绝对值，防止 -1 向右移位结果永远是 -1 的情况
  let result = 1; // 计算的最终结果
  let base = x; // 初始值为 x^1
​
  while (pow) {
    if (pow & 1 === 1) { // 判断当前位是 0 还是 1
      result = result * base;
    }
​
    base *= base; // 更新第 n 位上的权重值
    pow = pow >> 1; // 向右移位
  }
​
  return n > 0 ? result : 1 / result;
};

复杂度分析

• 时间复杂度：$O(\log_2 n)$​

  循环计算的次数为二进制的位数，将 $n$ 转换为二进制共有 $O(\log_2 n)$ 位，所以时间复杂度为 $O(\log_2 n)$。

• 空间复杂度：$O(1)$​

  我们使用了 3 个变量来保存中间值，所以空间复杂度为常数级别。

两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例

输入: dividend = 10, divisor = 3
输出: 3
示例 2:
​
输入: dividend = 7, divisor = -3
输出: -2
说明:

被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

方法一 利用累加的方式寻找商

思路

我们先让除数 divisor 左移直到大于被除数之前得到一个最大的 $n$ 的值，说明被除数dividend至少包含 $2^n$个 divisor ，然后减去这个数，再一次找到多少个$n - 1$、$n - 2$​

详解

1. 以100 / 4 为例， $4 * 2^4 = 64 <= 100$ , 得到 100 里最少有 $2^4$ 个 4

2. 将 100 - 64 得到 36， $4 * 2^3 = 32 <= 36$ , 此时得到 100 里最少有 $2^4 + 2^3$ 个 4

3. 将 36 -32 得到 4， $4 * 2^ 1 = 4 <= 4$ , 得出商为 $2^4 + 2^3 + 2^1 = 25$​

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
const divide = function (dividend, divisor) {
  const MIN_VALUE = -2147483648;
  const MAX_VALUE = 2147483647;
​
  const positive = (dividend ^ divisor) >= 0;
​
  let d = Math.abs(dividend);
  const b = Math.abs(divisor);
  let res = 0;
  while (d >= b) {
    let tmp = b;
    let p = 1;
    // 寻找有多少个 b
    while (d >= tmp << 1 && tmp < 1073741823) { // 1073741823 考虑溢出的情况
      tmp <<= 1;
      p <<= 1;
    }
    d -= tmp;
    res += p;
  }
​
  if (positive) {
    return res > MAX_VALUE ? MAX_VALUE : res;
  }
  return res < MIN_VALUE ? MIN_VALUE : -res;
};

复杂度分析

• 时间复杂度：$O(\log_2(n))$​

首先找出最大的 $n$​

dividend减去$2^n$个 divisor，再作为被除数，去找到多少个$n - 1$、$n - 2$​

​$O(n) = log_2(n) + log_2(n - 1) + ... = O(log_2(n))$​

• 空间复杂度分析：$O(1)$​

方法二 转化为减法

思路

任何一个整数都可以表示成以2的幂为底的一组基的线性组合，即

​$num = a_02^0 + a_12^1 + a_2 2^2 + ... + a_n2^n$​

题目要求不能用除法，要求商，可以转化为减法，能减多少次，商就是多少。但是光做减法的效率太低了，由于计算机擅长做移位计算，我们可以用移位。

详解

把被除数 dividend 除以 $2^n$，根据题干要求 $n$ 最大为 31，不断去尝试，当$dividend / 2^n >= divisor$ 时，将 $dividend$ 减去 $divisor * 2^n$ ，以此类推。

以 $10 / 3$ 为例，$10 / 2^1 = 5 > 3$ ，将 $10 - 2 * 3 = 4 > 3$ ，$res = 2^1 = 2$ 暂存

​$4 / 2^0 = 4 > 3$，4 - 1 * 3 = 1, $res = 2 + 2^0 = 3$，一共减去了 $2^1 + 2^0$ 个3， 因此答案是3

代码

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
const divide = function (dividend, divisor) {
  const MIN_VALUE = -2147483648;
  const MAX_VALUE = 2147483647;
​
  const positive = (dividend ^ divisor) >= 0;
​
  let t = Math.abs(dividend);
  const d = Math.abs(divisor);
​
  let res = 0;
  for (let i = 31; i >= 0; i--) {
    // 加绝对值是考虑溢出的情况，会变成负数
    if (Math.abs(t >> i) >= d) {
      res += Math.abs(1 << i);
      t -= Math.abs(d << i);
    }
  }
  if (positive) {
    return res > MAX_VALUE ? MAX_VALUE : res;
  }
  return res < MIN_VALUE ? MIN_VALUE : -res;
};

复杂度分析

• 时间复杂度：$O(n)$​

• 空间复杂度：$O(1)$​

分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例

输入: numerator = 1, denominator = 2
输出: "0.5"
​
输入: numerator = 2, denominator = 3
输出: "0.(6)"

解这道题只需要数学的基本知识长除法的运算规则。长除法的流程如下图：

​$\begin{array}{rll} 0.16 \\6 {\overline{\smash{\big)}\,1.00}} \\[-1pt]\underline{0\phantom{.00}} \\[-1pt]1\phantom{.}0 \phantom{0} && ...\ 余数为\ 1，标记\ 1\ 出现在位置\ 0。\\[-1pt]\underline{\phantom{0}6\phantom{0}} \\[-1pt]\phantom{0}40 && ...\ 余数为\ 4，标记\ 4\ 出现在位置\ 1。\\[-1pt]\underline{\phantom{0}36} \\[-1pt]\phantom{00}4 && ...\ 余数为\ 4，在位置\ 1\ 出现过，所以循环节从位置\ 1\ 开始，为\ 1(6)。\\[-1pt]\end{array}$​

由图中可知当余数出现循环的时候，对应的商也会循环，所以，当同一个余数出现两次时，我们就找到了循环位置

但是在计算过程中有诸多细节问题需要注意：

• 分母denominator为 0 时，应当抛出异常，这里为了简单起见不考虑

• 分子numerator为 0 时，结果为 0

• 分母denominator 和 分子numerator中存在一个负数时，结果为负数

方法一 递归

思路

用递归的方法实现。

维护一个记录余数的数组和记录余数第一次出现的位置的map，如果map中存在当前循环计算出的余数，则表示结果开始进入循环部分

详解

1. 先进行边界判断

2. 分别计算出整数和余数部分

3. 对余数部分使用长除法计算出新的余数

4. 若map中存在新计算出的余数，则说明出现循环，合并计算结果

5. 若map中不存在新计算出的余数，则将计算出的余数记录下来

6. 重复第3步

const fun = (map, remainder, remainders, denominator) => {
  if (!remainder) {
    return remainders;
  }
  let num = 0;
  if (map.has(remainder)) {
    remainders.splice(map.get(remainder), 0, '(');
    remainders.push(')');
    return remainders;
  } else {
    map.set(remainder, remainders.length);
    remainder *= 10;
    num = Math.floor(remainder / denominator);
    remainder %= denominator;
    remainders.push(num);
    return fun(map, remainder, remainders, denominator);
  }
};
const fractionToDecimal = function (numerator, denominator) {
  // 判断边界
  if (denominator === 0) {
    return '';
  }
  // 判断边界
  if (numerator === 0) {
    return '0';
  }
  let result = '';
  // 只存在1位负数
  if ((denominator < 0) ^ (numerator < 0)) {
    result += '-';
    denominator = Math.abs(denominator);
    numerator = Math.abs(numerator);
  }
  // 整数部分
  const integer = Math.floor(numerator / denominator);
  result += integer;
  // 余数部分
  const remainder = numerator % denominator;
  if (remainder) {
    result += '.';
  }
  let remainders = [];
  const map = new Map();
  if (remainder) {
    remainders = fun(map, remainder, remainders, denominator);
  }
  result += remainders.join('');
  return result;
};

复杂度分析

• 时间复杂度：$O(n)$​

  计算量与结果长度成正比，是线性的。

• 空间复杂度：$O(1)$​

  该解法中，申请了常数个变量，因此，空间复杂度为$O(1)$。

方法二 迭代

思路

使用迭代方法实现

维护一个记录以{remainder: position}形式记录每一个余数出现的位置的哈希对象， 如果存在当前循环计算出的余数，则表示结果开始进入循环部分

详解

1. 先进行边界判断

2. 分别计算出整数和余数部分

3. 对余数部分使用长除法计算出新的余数

4. 若remainders中存在新计算出的余数，则说明出现循环，合并计算结果

5. 若remainders中不存在新计算出的余数，则将计算出的余数和改余数出现的位置记录下来

6. 重复第3步

const fractionToDecimal = function (numerator, denominator) {
  // 判断边界
  if (denominator === 0) {
    return '';
  }
  // 判断边界
  if (numerator === 0) {
    return '0';
  }
  let result = '';
  // 只存在1位负数
  if ((denominator < 0) ^ (numerator < 0)) {
    result += '-';
    denominator = Math.abs(denominator);
    numerator = Math.abs(numerator);
  }
  // 整数部分
  const integer = Math.floor(numerator / denominator);
  result += integer;
  // 余数部分
  let remainder = numerator % denominator;
  if (remainder) {
    result += '.';
  }
  // 小数部分
  let decimal = '';
  let index = 0;
  const remainders = {};
  while (remainder) {
    const target = remainders[remainder];
    if (!isNaN(target)) {
      decimal = `${decimal.substring(0, target)}(${decimal.substring(target)})`;
      break;
    }
    remainders[remainder] = index++;
    remainder *= 10;
    const num = Math.floor(remainder / denominator);
    decimal = `${decimal}${num}`;
    remainder = remainder % denominator;
  }
  result += decimal;
  return result;
};

复杂度分析

• 时间复杂度：$O(n)$​

• 空间复杂度：$O(1)$​

  该解法中，申请了常数个变量，因此，空间复杂度为$O(1)$。

x的平方根

实现 int sqrt(int x) 函数。即计算并返回 x 的平方根，其中 x 是非负整数，由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例1

输入: 4
输出: 2

示例2

输入: 8
输出: 2
解释: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

方法一 顺序查找

思路

解题思路：从数字1开始找，一旦找到平方值等于x的数字i，直接返回i。如果找到平方值大于x的数字i，需要返回i - 1。

详解

1. 对于任一给定数字 x ，我们进行循环；

2. 对于每次循环的数字 i , 将 i * i 与 x 的值进行比较；

3. 如果前者大于后者，则说明 i 比我们需要的值大，又因为需要返回的是整数，所以 i-1 就是我们要找的值；

4. 如果两者值正好相等，那么 i 就是我们要找的值；

5. 如果前者小于后者，说明i与自身的乘积还没有达到要求，需要继续循环下去。

代码

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
 const mySqrt= function(x) {
    for (let i = 1; i <= x; i++) {
        if(i * i > x) {
            return (i - 1);
        }else if(i * i == x) {
            return i;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(sqrt(x))$​

对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，故需要耗费 $O(sqrt(x))$ 的时间。

• 空间复杂度：$O(1)$​

上述解法不需要申请额外的空间，故空间复杂度为 $O(1)$ 。

方法二 二分查找法

思路

解题思路： 采用二分查找的思想，因为x是非负整数，那么当x是0的时候平方根为0，x为1时平方根为1，只有当x大于1时才需要计算。因为当 x>1时，x 的平方根 y 肯定在 1到x 之间 即 1< y < x，知道了数值的范围, 我们可以每次把划分区间分为3部分 [(0,mid)，mid，(mid,end)]，从而不断缩小空间，即：在区间[0,end]取中间值mid,判断 mid * mid 与 x的大小关系.

当 mid mid > x 时 表示, mid mid 大了， 那么接下来在[1, mid-1]取中间值再判断.

当 mid mid < x时 表示, mid mid 小了， 那么接下来在[mid +1,x]取中间值再判断.

详解

1. 设置 3 个变量分别为 start 、 mid 、 end，并将 start赋值为1，end 赋值为所求目标 x 的一半的最正整数；

2. 因为存在0，这样的特殊情况，开始时循环条件就不成立，我们直接返回 end 即可；

3. 只要start 不大于 end，就进行循环操作，同时 给 mid 赋值 ，这样把划分区间分为3部分 [(start,mid)，mid，(mid,end)]；

4. 计算mid与自身的乘积 并且与 x 进行比较，前者大于后者时，则需要为 end 重新赋值；

5. 如果前者小于后者，我们需要更改最小值，则需要为 start 重新赋值;

6. 这样不断地缩小取值的范围，如果mid乘积 与 x 两者相同，mid 值就是我们需要的值。

代码

/**
 * @param {number} x
 * @return {number}
 */
const mySqrt = function(x) {
    let start = 1;
    let end = Math.floor(x/2) +1;
    let mid;
    while(start <= end) {
      mid = Math.floor((start + end) / 2);
      if (mid * mid > x) {
        // 更改最大值，继续取中间值
        end = mid - 1
      } else if (mid * mid < x) {
        // 更改最小值，继续取中间值
        start = mid + 1
      } else {
        return mid
      }
    }
    return end
};

复杂度分析

• 时间复杂度：$O(log(n))$​

二分法的时间复杂度是对数级别的,故时间复杂度为 $O(log(n))$。

• 空间复杂度：$O(1)$​

使用了常数个数的辅助空间用于存储和比较,不需要申请额外的空间，故空间复杂度为 $O(1)$。