实现 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
思路
看到题目首先想到可以用暴力计算,如果 为整数,则做 次底数 的累乘,如果 为负数,则做 次 底数() 的累乘,于是有了如下代码:
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;};
但是暴力计算会在指数较大时超时,这时我们发现比如计算 ,我们使用分治法,只需要计算出 的值做相乘,便可以得出 的值。 那么计算 的值,又可以拆解为 ,以此类推……
详解
我们可以使用折半计算,每次把 n 缩小一半,通过递归,最终获取 的 次幂,递推公式如下:
(当 为偶数时)
(当 为 奇数时)
边界情况:当 为 0 时,返回 1,当 为 1 或者 -1 时 分别返回 与
其他情况:当 为奇数时,需要多乘一次 的值
判断 是正数还是负数,如果是正数,则直接以 作为底数计算;如果是负数,则以 作为底数计算。
代码
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;};
复杂度分析
时间复杂度:
每次递归时,指数 减小一半,即 ,最终趋近于1,令 ,计算得出计算次数 ,所以时间复杂度为 。
空间复杂度:
每一次递归计算,都需要变量保存底数、下一次计算的幂值以及每次递归计算的结果三个常量,递归深度为 ,所以空间复杂度为 。
思路
我们继续在指数 n 上做文章,将 n 看做数列之和,使得 ;
那么由 ,可得 ;如果能够快速计算出 $x^ai$ 的值,那么即可求得 。
详解
有了以上分析,我们可以通过对幂值进行分解来简化计算,例如:
当 时,可转化为二进制表示法:1101,那么 ,即:
;
二进制: 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)。
我们拿 举例,需要进行 次计算,即 4 次计算。
将 13 转化为二进制表示法,对应值为 1101,使用 result 来保存计算中间值,使用 base 来保存计算到第 i 位需要乘的权重
result 初始位 1,base 初始值为
第一轮:从低位取数 13 & 1 = 1,,更新 base 的值: base *= base 即 base 为
第二轮:13 右移 1 位后二进制表示为 110,(13 >> 1) & 1 = 0,则跳过不予计算 result,更新 base 的值: base *= base 即 base 为
第三轮:13 右移 2 位后二进制表示为 11,(13 >> 2) & 1 = 1,result = result base = 5^1 5^4,更新 base 的值: base *= base 即 base 为
第四轮:13 右移 3 位后二进制表示为 1,(13 >> 3) & 1 = 1,
移位运算完毕,得到最终结果 。
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^1while (pow) {if (pow & 1 === 1) { // 判断当前位是 0 还是 1result = result * base;}base *= base; // 更新第 n 位上的权重值pow = pow >> 1; // 向右移位}return n > 0 ? result : 1 / result;};
复杂度分析
时间复杂度:
循环计算的次数为二进制的位数,将 转换为二进制共有 位,所以时间复杂度为 。
空间复杂度:
我们使用了 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
左移直到大于被除数之前得到一个最大的 的值,说明被除数dividend
至少包含 个 divisor
,然后减去这个数,再一次找到多少个、
详解
以100 / 4 为例, , 得到 100 里最少有 个 4
将 100 - 64 得到 36, , 此时得到 100 里最少有 个 4
将 36 -32 得到 4, , 得出商为
/*** @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;// 寻找有多少个 bwhile (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;};
复杂度分析
时间复杂度:
首先找出最大的
dividend
减去个 divisor
,再作为被除数,去找到多少个、
空间复杂度分析:
思路
任何一个整数都可以表示成以2的幂为底的一组基的线性组合,即
题目要求不能用除法,要求商,可以转化为减法,能减多少次,商就是多少。但是光做减法的效率太低了,由于计算机擅长做移位计算,我们可以用移位。
详解
把被除数 dividend
除以 ,根据题干要求 最大为 31,不断去尝试,当 时,将 减去 ,以此类推。
以 为例, ,将 , 暂存
,4 - 1 * 3 = 1, ,一共减去了 个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;};
复杂度分析
时间复杂度:
空间复杂度:
给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。
如果小数部分为循环小数,则将循环的部分括在括号内。
示例
输入: numerator = 1, denominator = 2输出: "0.5"输入: numerator = 2, denominator = 3输出: "0.(6)"
解这道题只需要数学的基本知识长除法
的运算规则。长除法的流程如下图:
由图中可知当余数出现循环的时候,对应的商也会循环,所以,当同一个余数出现两次时,我们就找到了循环位置
但是在计算过程中有诸多细节问题需要注意:
分母denominator
为 0 时,应当抛出异常,这里为了简单起见不考虑
分子numerator
为 0 时,结果为 0
分母denominator
和 分子numerator
中存在一个负数时,结果为负数
思路
用递归的方法实现。
维护一个记录余数的数组和记录余数第一次出现的位置的map,如果map中存在当前循环计算出的余数,则表示结果开始进入循环部分
详解
先进行边界判断
分别计算出整数和余数部分
对余数部分使用长除法
计算出新的余数
若map中存在新计算出的余数,则说明出现循环,合并计算结果
若map中不存在新计算出的余数,则将计算出的余数记录下来
重复第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;};
复杂度分析
时间复杂度:
计算量与结果长度成正比,是线性的。
空间复杂度:
该解法中,申请了常数个变量,因此,空间复杂度为。
思路
使用迭代方法实现
维护一个记录以{remainder: position}形式记录每一个余数出现的位置的哈希对象, 如果存在当前循环计算出的余数,则表示结果开始进入循环部分
详解
先进行边界判断
分别计算出整数和余数部分
对余数部分使用长除法
计算出新的余数
若remainders
中存在新计算出的余数,则说明出现循环,合并计算结果
若remainders
中不存在新计算出的余数,则将计算出的余数和改余数出现的位置记录下来
重复第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;};
复杂度分析
时间复杂度:
空间复杂度:
该解法中,申请了常数个变量,因此,空间复杂度为。
实现 int sqrt(int x) 函数。即计算并返回 x 的平方根,其中 x 是非负整数,由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例1
输入: 4输出: 2
示例2
输入: 8输出: 2解释: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
思路
解题思路:从数字1开始找,一旦找到平方值等于x的数字i,直接返回i。如果找到平方值大于x的数字i,需要返回i - 1。
详解
对于任一给定数字 x ,我们进行循环;
对于每次循环的数字 i , 将 i * i 与 x 的值进行比较;
如果前者大于后者,则说明 i 比我们需要的值大,又因为需要返回的是整数,所以 i-1 就是我们要找的值;
如果两者值正好相等,那么 i 就是我们要找的值;
如果前者小于后者,说明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;}
复杂度分析
时间复杂度:
对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,故需要耗费 的时间。
空间复杂度:
上述解法不需要申请额外的空间,故空间复杂度为 。
思路
解题思路: 采用二分查找
的思想,因为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]取中间值再判断.
详解
设置 3 个变量分别为 start 、 mid 、 end,并将 start赋值为1,end 赋值为所求目标 x 的一半的最正整数;
因为存在0,这样的特殊情况,开始时循环条件就不成立,我们直接返回 end 即可;
只要start 不大于 end,就进行循环操作,同时 给 mid 赋值 ,这样把划分区间分为3部分 [(start,mid),mid,(mid,end)];
计算mid与自身的乘积 并且与 x 进行比较,前者大于后者时,则需要为 end 重新赋值;
如果前者小于后者,我们需要更改最小值,则需要为 start 重新赋值;
这样不断地缩小取值的范围,如果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};
复杂度分析
时间复杂度:
二分法的时间复杂度是对数级别的,故时间复杂度为 。
空间复杂度:
使用了常数个数的辅助空间用于存储和比较,不需要申请额外的空间,故空间复杂度为 。