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!

方法一 二分法

思路
看到题目首先想到可以用暴力计算,如果
nn
为整数,则做
nn
次底数
xx
的累乘,如果
nn
为负数,则做
nn
次 底数(
1/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!
但是暴力计算会在指数较大时超时,这时我们发现比如计算
220220=2102102^{20},2^{20} = 2^{10}*2^{10}
我们使用分治法,只需要计算出
2102^{10}
的值做相乘,便可以得出
2202^{20}
的值。 那么计算
2102^{10 }
的值,又可以拆解为
25252^5* 2^5
,以此类推……
详解
我们可以使用折半计算,每次把 n 缩小一半,通过递归,最终获取
xx
nn
次幂,递推公式如下:
xn=xn/2xn/2x^n = x^{n / 2} x^{n / 2}
(当
nn
为偶数时)
xn=xn/2+xn/2x^n = x^{n / 2} + x^{n / 2}
(当
nn
为 奇数时)
  1. 1.
    边界情况:当
    nn
    为 0 时,返回 1,当
    n n
    为 1 或者 -1 时 分别返回
    xx
    1/x1 / x
  2. 2.
    其他情况:当
    nn
    为奇数时,需要多乘一次
    xx
    的值
判断
nn
是正数还是负数,如果是正数,则直接以
xx
作为底数计算;如果是负数,则以
1/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(log2n)O(\log_2n)
    每次递归时,指数
    nn
    减小一半,即
    n,n/2,n/4,....n/2kn, n/2, n/4, .... n/2^k
    ,最终趋近于1,令
    n/2k=1n/2^k = 1
    ,计算得出计算次数
    k=log2nk = log2 n
    ,所以时间复杂度为
    O(log2n)O(\log_2n)
  • 空间复杂度:
    O(log2n)O(\log_2n)
    每一次递归计算,都需要变量保存底数、下一次计算的幂值以及每次递归计算的结果三个常量,递归深度为
    log2n\log_2n
    ,所以空间复杂度为
    log2n\log_2n

方法二 快速幂

思路
我们继续在指数 n 上做文章,将 n 看做数列之和,使得
n=a1+a2+...+ann = a_1 + a_2 + ... + a_n
那么由
x(a+b)=xaxbx^{(a + b)} = x^a x^b
,可得
xn=xa1xa2...xanx^n = x^a1 x^a2 ... x^an
;如果能够快速计算出 $x^ai$ 的值,那么即可求得
xnx^n
详解
有了以上分析,我们可以通过对幂值进行分解来简化计算,例如:
n=13n = 13
时,可转化为二进制表示法:1101,那么
13=23+22+2013 = 2 ^ 3 + 2 ^ 2 + 2 ^ 0
,即:
xn=x23x22x20x^n = x^{2^3} x^{2^2} x^{2^0}
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=5n=13x = 5,n = 13
举例,需要进行
log213log_2 13
次计算,即 4 次计算。
将 13 转化为二进制表示法,对应值为 1101,使用 result 来保存计算中间值,使用 base 来保存计算到第 i 位需要乘的权重
result 初始位 1,base 初始值为
515^1
  1. 1.
    第一轮:从低位取数 13 & 1 = 1,
    result=resultbase=151result = result * base = 1 5^1
    ,更新 base 的值: base *= base 即 base 为
    525^2
  2. 2.
    第二轮:13 右移 1 位后二进制表示为 110,(13 >> 1) & 1 = 0,则跳过不予计算 result,更新 base 的值: base *= base 即 base 为
    545^4
  3. 3.
    第三轮:13 右移 2 位后二进制表示为 11,(13 >> 2) & 1 = 1,result = result base = 5^1 5^4,更新 base 的值: base *= base 即 base 为
    585^8
  4. 4.
    第四轮:13 右移 3 位后二进制表示为 1,(13 >> 3) & 1 = 1,
    result=resultbase=515458result = result base = 5^1* 5^4 * 5^8
移位运算完毕,得到最终结果
result=515458=5(1+4+8)=513result = 5^1 *5^4 *5^8 = 5^(1 + 4 + 8) = 5^13

代码

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(log2n)O(\log_2 n)
    循环计算的次数为二进制的位数,将
    nn
    转换为二进制共有
    O(log2n)O(\log_2 n)
    位,所以时间复杂度为
    O(log2n)O(\log_2 n)
  • 空间复杂度:
    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 左移直到大于被除数之前得到一个最大的
nn
的值,说明被除数dividend至少包含
2n2^n
divisor ,然后减去这个数,再一次找到多少个
n1n - 1
n2n - 2
详解
  1. 1.
    以100 / 4 为例,
    424=64<=1004 * 2^4 = 64 <= 100
    , 得到 100 里最少有
    242^4
    个 4
  2. 2.
    将 100 - 64 得到 36,
    423=32<=364 * 2^3 = 32 <= 36
    , 此时得到 100 里最少有
    24+232^4 + 2^3
    个 4
  3. 3.
    将 36 -32 得到 4,
    421=4<=44 * 2^ 1 = 4 <= 4
    , 得出商为
    24+23+21=252^4 + 2^3 + 2^1 = 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(log2(n))O(\log_2(n))
首先找出最大的
nn
dividend减去
2n2^n
divisor,再作为被除数,去找到多少个
n1n - 1
n2n - 2
O(n)=log2(n)+log2(n1)+...=O(log2(n))O(n) = log_2(n) + log_2(n - 1) + ... = O(log_2(n))
  • 空间复杂度分析:
    O(1)O(1)

方法二 转化为减法

思路
任何一个整数都可以表示成以2的幂为底的一组基的线性组合,即
num=a020+a121+a222+...+an2nnum = a_02^0 + a_12^1 + a_2 2^2 + ... + a_n2^n
题目要求不能用除法,要求商,可以转化为减法,能减多少次,商就是多少。但是光做减法的效率太低了,由于计算机擅长做移位计算,我们可以用移位。
详解
把被除数 dividend 除以
2n2^n
,根据题干要求
nn
最大为 31,不断去尝试,当
dividend/2n>=divisordividend / 2^n >= divisor
时,将
dividenddividend
减去
divisor2ndivisor * 2^n
,以此类推。
10/310 / 3
为例,
10/21=5>310 / 2^1 = 5 > 3
,将
1023=4>310 - 2 * 3 = 4 > 3
res=21=2res = 2^1 = 2
暂存
4/20=4>34 / 2^0 = 4 > 3
,4 - 1 * 3 = 1,
res=2+20=3res = 2 + 2^0 = 3
,一共减去了
21+202^1 + 2^0
个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(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.000.001.00... 余数为 1,标记 1 出现在位置 0060040... 余数为 4,标记 4 出现在位置 1036004... 余数为 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}
由图中可知当余数出现循环的时候,对应的商也会循环,所以,当同一个余数出现两次时,我们就找到了循环位置
但是在计算过程中有诸多细节问题需要注意:
  • 分母denominator为 0 时,应当抛出异常,这里为了简单起见不考虑
  • 分子numerator为 0 时,结果为 0
  • 分母denominator 和 分子numerator中存在一个负数时,结果为负数

方法一 递归

思路
用递归的方法实现。
维护一个记录余数的数组和记录余数第一次出现的位置的map,如果map中存在当前循环计算出的余数,则表示结果开始进入循环部分
详解
  1. 1.
    先进行边界判断
  2. 2.
    分别计算出整数和余数部分
  3. 3.
    对余数部分使用长除法计算出新的余数
  4. 4.
    若map中存在新计算出的余数,则说明出现循环,合并计算结果
  5. 5.
    若map中不存在新计算出的余数,则将计算出的余数记录下来
  6. 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(1)O(1)
    该解法中,申请了常数个变量,因此,空间复杂度为
    O(1)O(1)

方法二 迭代

思路
使用迭代方法实现
维护一个记录以{remainder: position}形式记录每一个余数出现的位置的哈希对象, 如果存在当前循环计算出的余数,则表示结果开始进入循环部分
详解
  1. 1.
    先进行边界判断
  2. 2.
    分别计算出整数和余数部分
  3. 3.
    对余数部分使用长除法计算出新的余数
  4. 4.
    remainders中存在新计算出的余数,则说明出现循环,合并计算结果
  5. 5.
    remainders中不存在新计算出的余数,则将计算出的余数和改余数出现的位置记录下来
  6. 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(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. 1.
    对于任一给定数字 x ,我们进行循环;
  2. 2.
    对于每次循环的数字 i , 将 i * i 与 x 的值进行比较;
  3. 3.
    如果前者大于后者,则说明 i 比我们需要的值大,又因为需要返回的是整数,所以 i-1 就是我们要找的值;
  4. 4.
    如果两者值正好相等,那么 i 就是我们要找的值;
  5. 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(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. 1.
    设置 3 个变量分别为 start 、 mid 、 end,并将 start赋值为1,end 赋值为所求目标 x 的一半的最正整数;
  2. 2.
    因为存在0,这样的特殊情况,开始时循环条件就不成立,我们直接返回 end 即可;
  3. 3.
    只要start 不大于 end,就进行循环操作,同时 给 mid 赋值 ,这样把划分区间分为3部分 [(start,mid),mid,(mid,end)];
  4. 4.
    计算mid与自身的乘积 并且与 x 进行比较,前者大于后者时,则需要为 end 重新赋值;
  5. 5.
    如果前者小于后者,我们需要更改最小值,则需要为 start 重新赋值;
  6. 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(1)O(1)
使用了常数个数的辅助空间用于存储和比较,不需要申请额外的空间,故空间复杂度为
O(1)O(1)