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

pow(x, n) 
实现 pow(x, n) ，即计算 x 的 n 次幂函数
示例 1:
1
输入: 2.00000, 10
2
输出: 1024.00000
Copied!
示例 2:
1
输入: 2.10000, 3
2
输出: 9.26100
Copied!
示例 3:
1
输入: 2.00000, -2
2
输出: 0.25000
3
解释: 2-2 = 1/22 = 1/4 = 0.25
Copied!
方法一 二分法
思路
看到题目首先想到可以用暴力计算，如果 nnn
 为整数，则做 nnn
 次底数 xx x
的累乘，如果 nnn
 为负数，则做 nnn
 次 底数(1/x1 / x1/x
) 的累乘，于是有了如下代码：
1
function myPow (x, n) {
2
  // 考虑 n 为 0 的边界情况
3
  if (n === 0) {
4
      return 1;
5
  }
6
​
7
  const base = n > 0 ? x : 1 / x; // 通过正负号，确认参与幂运算的底数
8
  let result = 1;
9
​
10
  for (let i = 1; i <= Math.abs(n); i++) {
11
    result *= base;
12
  }
13
​
14
  return result;
15
};
Copied!
但是暴力计算会在指数较大时超时，这时我们发现比如计算 220，220=210∗2102^{20}，2^{20} = 2^{10}*2^{10}220，220=210∗210
，我们使用分治法，只需要计算出 2102^{10}210
 的值做相乘，便可以得出 2202^{20}220
 的值。 那么计算 2102^{10 }210
的值，又可以拆解为 25∗252^5* 2^525∗25
，以此类推……
详解
我们可以使用折半计算，每次把 n 缩小一半，通过递归，最终获取 xxx
 的 nnn
 次幂，递推公式如下：
​xn=xn/2xn/2x^n = x^{n / 2}  x^{n / 2} xn=xn/2xn/2
(当 nnn
 为偶数时) 
​xn=xn/2+xn/2x^n = x^{n / 2} + x^{n / 2} xn=xn/2+xn/2
  (当 nn n
为 奇数时)
1.边界情况：当 nnn
 为 0 时，返回 1，当n nn
 为 1 或者 -1 时 分别返回 xx x
与 1/x1 / x1/x
​
2.其他情况：当 nnn
 为奇数时，需要多乘一次 xxx
 的值
判断 nnn
 是正数还是负数，如果是正数，则直接以 xxx
 作为底数计算；如果是负数，则以 1/x1 / x1/x
 作为底数计算。
代码
1
function myPow (x, n) {
2
  // 考虑 n 为 0, 1, -1 的边界情况
3
  if (n === 0) {
4
      return 1;
5
  } else if (n === 1) {
6
      return x;
7
  } else if (n === -1) {
8
      return 1 / x;
9
  }
10
​
11
  const base = n > 0 ? x : 1 / x; // 通过正负号，确认参与幂运算的底数
12
  const half = parseInt(n / 2, 10); // 将 n 的值缩小一半
13
  const result = myPow(x, half); // 保存折半计算的值，避免重复计算
14
​
15
  if (n % 2) { // 如果 n 是奇数，则需要额外乘以一次底数
16
    return base * result * result;
17
  }
18
  // 如果 n 是偶数，则直接返回折半计算的乘积
19
  return result * result;
20
};
Copied!
复杂度分析
时间复杂度：O(log⁡2n)O(\log_2n)O(log2​n)
​
每次递归时，指数 nnn
 减小一半，即 n,n/2,n/4,....n/2kn, n/2, n/4, .... n/2^kn,n/2,n/4,....n/2k
，最终趋近于1，令 n/2k=1n/2^k = 1n/2k=1
，计算得出计算次数 k=log2nk = log2 nk=log2n
，所以时间复杂度为 O(log⁡2n)O(\log_2n)O(log2​n)
。
空间复杂度：O(log⁡2n)O(\log_2n)O(log2​n)
​
每一次递归计算，都需要变量保存底数、下一次计算的幂值以及每次递归计算的结果三个常量，递归深度为 log⁡2n\log_2nlog2​n
，所以空间复杂度为 log⁡2n\log_2nlog2​n
。
方法二 快速幂
思路
我们继续在指数 n 上做文章，将 n 看做数列之和，使得 n=a1+a2+...+ann = a_1 + a_2 + ... + a_nn=a1​+a2​+...+an​
；
那么由 x(a+b)=xaxbx^{(a + b)} = x^a  x^bx(a+b)=xaxb
，可得 xn=xa1xa2...xanx^n = x^a1  x^a2  ...  x^anxn=xa1xa2...xan
；如果能够快速计算出 $x^ai$ 的值，那么即可求得 xnx^nxn
。
详解
有了以上分析，我们可以通过对幂值进行分解来简化计算，例如：
当 n=13n = 13n=13
时，可转化为二进制表示法：1101，那么 13=23+22+2013 = 2 ^ 3 + 2 ^ 2 + 2 ^ 013=23+22+20
，即：
​xn=x23x22x20x^n = x^{2^3}  x^{2^2}  x^{2^0}xn=x23x22x20
；
1
二进制： 1    1    0    1
2
权重：  x^8  x^4  x^2  x^1
Copied!
可通过移位运算，当该位不为 0 时，乘以对应位上的权重，循环累乘，得到最终计算结果，对应位上的权重则可以通过低位的权重计算所得，如：
1
x^1 = x;
2
x^2 = (x^1) * (x^1);
3
x^4 = (x^2) * (x^2);
4
x^8 = (x^4) * (x^4)。
Copied!
我们拿 x=5，n=13x = 5，n = 13x=5，n=13
 举例，需要进行 log213log_2 13log2​13
 次计算，即 4 次计算。
将 13 转化为二进制表示法，对应值为 1101，使用 result 来保存计算中间值，使用 base 来保存计算到第 i 位需要乘的权重
result 初始位 1，base 初始值为 515^151
​
1.第一轮：从低位取数 13 & 1 = 1，result=result∗base=151result = result  * base = 1  5^1result=result∗base=151
，更新 base 的值: base *= base 即 base 为 525^252
​
2.第二轮：13 右移 1 位后二进制表示为 110，(13 >> 1) & 1 = 0，则跳过不予计算 result，更新 base 的值: base *= base 即 base 为 545^454
​
3.第三轮：13 右移 2 位后二进制表示为 11，(13 >> 2) & 1 = 1，result = result  base = 5^1  5^4，更新 base 的值: base *= base 即 base 为 585^858
​
4.第四轮：13 右移 3 位后二进制表示为 1，(13 >> 3) & 1 = 1， result=resultbase=51∗54∗58result = result  base = 5^1* 5^4 * 5^8result=resultbase=51∗54∗58
 
移位运算完毕，得到最终结果 result=51∗54∗58=5(1+4+8)=513result = 5^1 *5^4 *5^8 = 5^(1 + 4 + 8) = 5^13result=51∗54∗58=5(1+4+8)=513
。
代码
1
function myPow (x, n) {
2
  if (n === 0) {
3
    return 1;
4
  } else if (n === 1) {
5
    return x;
6
  } else if (n === -1) {
7
    return 1 / x;
8
  }
9
​
10
  let pow = Math.abs(n); // 取幂值绝对值，防止 -1 向右移位结果永远是 -1 的情况
11
  let result = 1; // 计算的最终结果
12
  let base = x; // 初始值为 x^1
13
​
14
  while (pow) {
15
    if (pow & 1 === 1) { // 判断当前位是 0 还是 1
16
      result = result * base;
17
    }
18
​
19
    base *= base; // 更新第 n 位上的权重值
20
    pow = pow >> 1; // 向右移位
21
  }
22
​
23
  return n > 0 ? result : 1 / result;
24
};
Copied!
复杂度分析
时间复杂度：O(log⁡2n)O(\log_2 n)O(log2​n)
​
循环计算的次数为二进制的位数，将 nnn
 转换为二进制共有 O(log⁡2n)O(\log_2 n)O(log2​n)
 位，所以时间复杂度为 O(log⁡2n)O(\log_2 n)O(log2​n)
。
空间复杂度：O(1)O(1)O(1)
​
我们使用了 3 个变量来保存中间值，所以空间复杂度为常数级别。
两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例
1
输入: dividend = 10, divisor = 3
2
输出: 3
3
示例 2:
4
​
5
输入: dividend = 7, divisor = -3
6
输出: -2
7
说明:
Copied!
被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
方法一 利用累加的方式寻找商
思路
我们先让除数 divisor 左移直到大于被除数之前得到一个最大的 nnn
 的值，说明被除数dividend至少包含 2n2^n2n
个 divisor ，然后减去这个数，再一次找到多少个n−1n - 1n−1
、n−2n - 2n−2
​
详解
1.以100 / 4 为例， 4∗24=64<=1004 * 2^4 = 64 <= 1004∗24=64<=100
 , 得到 100 里最少有 242^424
 个 4
2.将 100 - 64 得到 36， 4∗23=32<=364 * 2^3 = 32 <= 36 4∗23=32<=36
 , 此时得到 100 里最少有 24+232^4 + 2^324+23
 个 4
3.将 36 -32 得到 4， 4∗21=4<=44 * 2^ 1 = 4 <= 44∗21=4<=4
 , 得出商为 24+23+21=252^4 + 2^3 + 2^1 = 2524+23+21=25
​
1
/**
2
 * @param {number} dividend
3
 * @param {number} divisor
4
 * @return {number}
5
 */
6
const divide = function (dividend, divisor) {
7
  const MIN_VALUE = -2147483648;
8
  const MAX_VALUE = 2147483647;
9
​
10
  const positive = (dividend ^ divisor) >= 0;
11
​
12
  let d = Math.abs(dividend);
13
  const b = Math.abs(divisor);
14
  let res = 0;
15
  while (d >= b) {
16
    let tmp = b;
17
    let p = 1;
18
    // 寻找有多少个 b
19
    while (d >= tmp << 1 && tmp < 1073741823) { // 1073741823 考虑溢出的情况
20
      tmp <<= 1;
21
      p <<= 1;
22
    }
23
    d -= tmp;
24
    res += p;
25
  }
26
​
27
  if (positive) {
28
    return res > MAX_VALUE ? MAX_VALUE : res;
29
  }
30
  return res < MIN_VALUE ? MIN_VALUE : -res;
31
};
Copied!
复杂度分析
时间复杂度：O(log⁡2(n))O(\log_2(n))O(log2​(n))
​
首先找出最大的 nnn
​
dividend减去2n2^n2n
个 divisor，再作为被除数，去找到多少个n−1n - 1n−1
、n−2n - 2n−2
​
​O(n)=log2(n)+log2(n−1)+...=O(log2(n))O(n) = log_2(n) + log_2(n - 1) + ... = O(log_2(n))O(n)=log2​(n)+log2​(n−1)+...=O(log2​(n))
​
空间复杂度分析：O(1)O(1)O(1)
​
方法二 转化为减法
思路
任何一个整数都可以表示成以2的幂为底的一组基的线性组合，即
​num=a020+a121+a222+...+an2nnum = a_02^0 + a_12^1 + a_2  2^2 + ... + a_n2^nnum=a0​20+a1​21+a2​22+...+an​2n
​
题目要求不能用除法，要求商，可以转化为减法，能减多少次，商就是多少。但是光做减法的效率太低了，由于计算机擅长做移位计算，我们可以用移位。
详解
把被除数 dividend 除以 2n2^n2n
，根据题干要求 nnn
 最大为 31，不断去尝试，当dividend/2n>=divisordividend / 2^n >= divisor dividend/2n>=divisor
 时，将 dividenddividenddividend
 减去 divisor∗2ndivisor * 2^ndivisor∗2n
 ，以此类推。
以 10/310 / 310/3
 为例，10/21=5>310 / 2^1 = 5 > 310/21=5>3
 ，将 10−2∗3=4>310 - 2 * 3 = 4 > 310−2∗3=4>3
 ，res=21=2res = 2^1 = 2res=21=2
 暂存
​4/20=4>34 / 2^0 = 4 > 34/20=4>3
，4 - 1 * 3 = 1, res=2+20=3res = 2 + 2^0 = 3res=2+20=3
，一共减去了 21+202^1 + 2^021+20
 个3， 因此答案是3
代码
1
/**
2
 * @param {number} dividend
3
 * @param {number} divisor
4
 * @return {number}
5
 */
6
const divide = function (dividend, divisor) {
7
  const MIN_VALUE = -2147483648;
8
  const MAX_VALUE = 2147483647;
9
​
10
  const positive = (dividend ^ divisor) >= 0;
11
​
12
  let t = Math.abs(dividend);
13
  const d = Math.abs(divisor);
14
​
15
  let res = 0;
16
  for (let i = 31; i >= 0; i--) {
17
    // 加绝对值是考虑溢出的情况，会变成负数
18
    if (Math.abs(t >> i) >= d) {
19
      res += Math.abs(1 << i);
20
      t -= Math.abs(d << i);
21
    }
22
  }
23
  if (positive) {
24
    return res > MAX_VALUE ? MAX_VALUE : res;
25
  }
26
  return res < MIN_VALUE ? MIN_VALUE : -res;
27
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
空间复杂度：O(1)O(1)O(1)
​
分数到小数
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。
示例
1
输入: numerator = 1, denominator = 2
2
输出: "0.5"
3
​
4
输入: numerator = 2, denominator = 3
5
输出: "0.(6)"
Copied!
解这道题只需要数学的基本知识长除法的运算规则。长除法的流程如下图：
​0.166) 1.00‾0.00‾1.00... 余数为 1，标记 1 出现在位置 0。060‾040... 余数为 4，标记 4 出现在位置 1。036‾004... 余数为 4，在位置 1 出现过，所以循环节从位置 1 开始，为 1(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}0.166)1.000.00​1.00060​040036​004​​... 余数为 1，标记 1 出现在位置 0。... 余数为 4，标记 4 出现在位置 1。... 余数为 4，在位置 1 出现过，所以循环节从位置 1 开始，为 1(6)。​
​
由图中可知当余数出现循环的时候，对应的商也会循环，所以，当同一个余数出现两次时，我们就找到了循环位置
但是在计算过程中有诸多细节问题需要注意：
分母denominator为 0 时，应当抛出异常，这里为了简单起见不考虑
分子numerator为 0 时，结果为 0
分母denominator 和 分子numerator中存在一个负数时，结果为负数
方法一 递归
思路
用递归的方法实现。
维护一个记录余数的数组和记录余数第一次出现的位置的map，如果map中存在当前循环计算出的余数，则表示结果开始进入循环部分
详解
1.先进行边界判断
2.分别计算出整数和余数部分
3.对余数部分使用长除法计算出新的余数
4.若map中存在新计算出的余数，则说明出现循环，合并计算结果
5.若map中不存在新计算出的余数，则将计算出的余数记录下来
6.重复第3步
1
const fun = (map, remainder, remainders, denominator) => {
2
  if (!remainder) {
3
    return remainders;
4
  }
5
  let num = 0;
6
  if (map.has(remainder)) {
7
    remainders.splice(map.get(remainder), 0, '(');
8
    remainders.push(')');
9
    return remainders;
10
  } else {
11
    map.set(remainder, remainders.length);
12
    remainder *= 10;
13
    num = Math.floor(remainder / denominator);
14
    remainder %= denominator;
15
    remainders.push(num);
16
    return fun(map, remainder, remainders, denominator);
17
  }
18
};
19
const fractionToDecimal = function (numerator, denominator) {
20
  // 判断边界
21
  if (denominator === 0) {
22
    return '';
23
  }
24
  // 判断边界
25
  if (numerator === 0) {
26
    return '0';
27
  }
28
  let result = '';
29
  // 只存在1位负数
30
  if ((denominator < 0) ^ (numerator < 0)) {
31
    result += '-';
32
    denominator = Math.abs(denominator);
33
    numerator = Math.abs(numerator);
34
  }
35
  // 整数部分
36
  const integer = Math.floor(numerator / denominator);
37
  result += integer;
38
  // 余数部分
39
  const remainder = numerator % denominator;
40
  if (remainder) {
41
    result += '.';
42
  }
43
  let remainders = [];
44
  const map = new Map();
45
  if (remainder) {
46
    remainders = fun(map, remainder, remainders, denominator);
47
  }
48
  result += remainders.join('');
49
  return result;
50
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
计算量与结果长度成正比，是线性的。
空间复杂度：O(1)O(1)O(1)
​
该解法中，申请了常数个变量，因此，空间复杂度为O(1)O(1)O(1)
。
方法二 迭代
思路
使用迭代方法实现
维护一个记录以{remainder: position}形式记录每一个余数出现的位置的哈希对象， 如果存在当前循环计算出的余数，则表示结果开始进入循环部分
详解
1.先进行边界判断
2.分别计算出整数和余数部分
3.对余数部分使用长除法计算出新的余数
4.若remainders中存在新计算出的余数，则说明出现循环，合并计算结果
5.若remainders中不存在新计算出的余数，则将计算出的余数和改余数出现的位置记录下来
6.重复第3步
1
const fractionToDecimal = function (numerator, denominator) {
2
  // 判断边界
3
  if (denominator === 0) {
4
    return '';
5
  }
6
  // 判断边界
7
  if (numerator === 0) {
8
    return '0';
9
  }
10
  let result = '';
11
  // 只存在1位负数
12
  if ((denominator < 0) ^ (numerator < 0)) {
13
    result += '-';
14
    denominator = Math.abs(denominator);
15
    numerator = Math.abs(numerator);
16
  }
17
  // 整数部分
18
  const integer = Math.floor(numerator / denominator);
19
  result += integer;
20
  // 余数部分
21
  let remainder = numerator % denominator;
22
  if (remainder) {
23
    result += '.';
24
  }
25
  // 小数部分
26
  let decimal = '';
27
  let index = 0;
28
  const remainders = {};
29
  while (remainder) {
30
    const target = remainders[remainder];
31
    if (!isNaN(target)) {
32
      decimal = `${decimal.substring(0, target)}(${decimal.substring(target)})`;
33
      break;
34
    }
35
    remainders[remainder] = index++;
36
    remainder *= 10;
37
    const num = Math.floor(remainder / denominator);
38
    decimal = `${decimal}${num}`;
39
    remainder = remainder % denominator;
40
  }
41
  result += decimal;
42
  return result;
43
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
空间复杂度：O(1)O(1)O(1)
​
该解法中，申请了常数个变量，因此，空间复杂度为O(1)O(1)O(1)
。
x的平方根
实现 int sqrt(int x) 函数。即计算并返回 x 的平方根，其中 x 是非负整数，由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例1
1
输入: 4
2
输出: 2
Copied!
示例2
1
输入: 8
2
输出: 2
3
解释: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
Copied!
方法一  顺序查找
思路
解题思路：从数字1开始找，一旦找到平方值等于x的数字i，直接返回i。如果找到平方值大于x的数字i，需要返回i - 1。
详解
1.对于任一给定数字 x ，我们进行循环；
2.对于每次循环的数字 i , 将 i * i 与 x 的值进行比较；
3.如果前者大于后者，则说明 i 比我们需要的值大，又因为需要返回的是整数，所以 i-1 就是我们要找的值；
4.如果两者值正好相等，那么 i 就是我们要找的值；
5.如果前者小于后者，说明i与自身的乘积还没有达到要求，需要继续循环下去。
代码
1
/**
2
 * @param {number} n - a positive integer
3
 * @return {number}
4
 */
5
 const mySqrt= function(x) {
6
    for (let i = 1; i <= x; i++) {
7
        if(i * i > x) {
8
            return (i - 1);
9
        }else if(i * i == x) {
10
            return i;
11
        }
12
    }
13
    return 0;
14
}
Copied!
复杂度分析
时间复杂度：O(sqrt(x))O(sqrt(x))O(sqrt(x))
​
对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，故需要耗费 O(sqrt(x))O(sqrt(x))O(sqrt(x))
 的时间。
空间复杂度：O(1)O(1)O(1)
​
上述解法不需要申请额外的空间，故空间复杂度为 O(1)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 值就是我们需要的值。
代码
1
/**
2
 * @param {number} x
3
 * @return {number}
4
 */
5
const mySqrt = function(x) {
6
    let start = 1;
7
    let end = Math.floor(x/2) +1;
8
    let mid;
9
    while(start <= end) {
10
      mid = Math.floor((start + end) / 2);
11
      if (mid * mid > x) {
12
        // 更改最大值，继续取中间值
13
        end = mid - 1
14
      } else if (mid * mid < x) {
15
        // 更改最小值，继续取中间值
16
        start = mid + 1
17
      } else {
18
        return mid
19
      }
20
    }
21
    return end
22
};
Copied!
复杂度分析
时间复杂度：O(log(n))O(log(n))O(log(n))
​
二分法的时间复杂度是对数级别的,故时间复杂度为 O(log(n))O(log(n))O(log(n))
。
空间复杂度：O(1)O(1)O(1)
​
使用了常数个数的辅助空间用于存储和比较,不需要申请额外的空间，故空间复杂度为 O(1)O(1)O(1)
。