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

方法一 二分法

思路

看到题目首先想到可以用暴力计算,如果 nn 为整数,则做 nn 次底数 xx 的累乘,如果 nn 为负数,则做 nn 次 底数(1/x1 / 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;
};

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

详解

我们可以使用折半计算,每次把 n 缩小一半,通过递归,最终获取 xxnn 次幂,递推公式如下:

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. 边界情况:当 nn 为 0 时,返回 1,当n n 为 1 或者 -1 时 分别返回 xx 1/x1 / x

  2. 其他情况:当 nn 为奇数时,需要多乘一次 xx 的值

判断 nn 是正数还是负数,如果是正数,则直接以 xx 作为底数计算;如果是负数,则以 1/x1 / 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(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 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=5n=13x = 5,n = 13 举例,需要进行 log213log_2 13 次计算,即 4 次计算。

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

result 初始位 1,base 初始值为 515^1

  1. 第一轮:从低位取数 13 & 1 = 1,result=resultbase=151result = result * base = 1 5^1,更新 base 的值: base *= base 即 base 为 525^2

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

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

  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

代码

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(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 得到的商。

示例

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

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

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

思路

我们先让除数 divisor 左移直到大于被除数之前得到一个最大的 nn 的值,说明被除数dividend至少包含 2n2^ndivisor ,然后减去这个数,再一次找到多少个n1n - 1n2n - 2

详解

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

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

  3. 将 36 -32 得到 4, 421=4<=44 * 2^ 1 = 4 <= 4 , 得出商为 24+23+21=252^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(log2(n))O(\log_2(n))

首先找出最大的 nn

dividend减去2n2^ndivisor,再作为被除数,去找到多少个n1n - 1n2n - 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 > 3res=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

代码

/**
* @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(n)

  • 空间复杂度:O(1)O(1)

分数到小数

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

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

示例

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

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

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. 先进行边界判断

  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(n)

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

  • 空间复杂度:O(1)O(1)

    该解法中,申请了常数个变量,因此,空间复杂度为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(n)

  • 空间复杂度:O(1)O(1)

    该解法中,申请了常数个变量,因此,空间复杂度为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(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. 设置 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(log(n))O(log(n))

  • 空间复杂度:O(1)O(1)

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