Open sl1673495 opened 4 years ago
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
https://leetcode-cn.com/problems/powx-n
这题的第一反应是一步步去用x * x暴力计算,但是这种解法会超时。
x * x
所以用一种快速幂计算的方式,也就是把 x 的 n 次方转化为 x * x 的 n / 2 次方。
快速幂
比如求 2 的 10 次方可以转为 4 的 5 次方,这时候遇到奇数次方了,就转化为 4* (4 的 4 次方)。
然后对于 4 的 4 次方,再进一步转化为 16 的 2 次方,最后转为 256 的 1 次方 * 4,就得出最终解 1024。
/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function (x, n) { if (n === 0) return 1; if (n === 1) return x; let abs = Math.abs(n); let isMinus = abs !== n; let res = abs % 2 === 0 ? myPow(x * x, abs / 2) : x * myPow(x, abs - 1); return isMinus ? 1 / res : res; };
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
https://leetcode-cn.com/problems/powx-n
思路
这题的第一反应是一步步去用
x * x
暴力计算,但是这种解法会超时。所以用一种
快速幂
计算的方式,也就是把 x 的 n 次方转化为 x * x 的 n / 2 次方。比如求 2 的 10 次方可以转为 4 的 5 次方,这时候遇到奇数次方了,就转化为 4* (4 的 4 次方)。
然后对于 4 的 4 次方,再进一步转化为 16 的 2 次方,最后转为 256 的 1 次方 * 4,就得出最终解 1024。