千问 LeetCode 50. Pow(x, n) TypeScript实现

在 TypeScript 中实现 LeetCode 50. Pow(x, n)核心思路依然是快速幂算法二分求幂。这道题在 TypeScript以及整个 JavaScript 生态中有一个非常经典的“坑”题目给定的 n 范围是 [-2^31, 2^31 - 1]。如果 n -2^31直接对其取反 -n 得到的值超出了 32 位有符号整数的正数范围。虽然 JS/TS 的 number 类型底层是双精度浮点数不会像 C/Rust 那样发生整数溢出 Panic但在某些严格的位运算或类型转换场景下直接处理 n -2^31 依然容易引发逻辑错误。因此最安全的做法是将 n 转换为 BigInt或者在循环条件上做特殊处理。下面为你提供两种 TypeScript 的实现方式解法一递归实现最直观体现分治思想function myPow(x: number, n: number): number {// 1. 处理负指数的情况if (n 0) {// 将 n 转为 BigInt 再取反完美规避 -2^31 的边界问题return 1.0 / quickPow(x, BigInt(-n));}return quickPow(x, BigInt(n));}// 使用 BigInt 作为指数类型确保绝对安全function quickPow(x: number, n: bigint): number {// 2. 递归终止条件if (n 0n) {return 1.0;}// 3. 分治先计算 x^(n/2) const half quickPow(x, n / 2n); // 4. 合并结果根据 n 的奇偶性决定是否需要多乘一个 x if (n % 2n 0n) { return half * half; } else { return half * half * x; }}解法二迭代实现最优避免递归栈开销利用位运算来检查 n 的最低位在循环中完成快速幂。同样使用 BigInt 处理指数。function myPow(x: number, n: number): number {// 1. 将 n 转为 BigInt防止 -2^31 取反时的潜在问题let N BigInt(n);let currentX x;// 2. 处理负指数 if (N 0n) { currentX 1.0 / currentX; N -N; } let result 1.0; let currentProduct currentX; // 3. 循环直到 N 变为 0 while (N 0n) { // 如果 N 的最低位是 1说明需要乘上当前的 currentProduct if (N 1n) { result * currentProduct; } // 将 x 平方对应指数减半 currentProduct * currentProduct; // N 右移一位相当于 N / 2 N 1n; } return result;} TypeScript 核心要点解析BigInt 的降维打击在 TS 中普通的 number 进行位运算如 n 1时引擎会先将数字截断为 32 位有符号整数。如果 n -2^31直接进行位运算可能会产生不可预期的结果。使用 BigInt字面量后加 n如 1n, 0n可以完全摆脱 32 位整数的限制让逻辑绝对安全。分治降维无论是递归还是迭代核心都是把 O(n) 的乘法次数降到了 O(log n)。例如计算 x^{10}只需要计算 x^2 rightarrow x^4 rightarrow x^8再组合即可。位运算的妙用在迭代法中N 1n 等价于 N % 2n ! 0nN 1n 等价于 N / 2n。位运算在底层执行效率更高且语义上更贴合“二进制分解”的快速幂本质。复杂度分析时间复杂度O(log n)循环或递归的次数等于 n 的二进制位数。空间复杂度递归法为 O(log n)系统调用栈迭代法为 O(1)。如果你刚做完这道题强烈建议去体验一下 LeetCode 372. 超级次方它结合了快速幂和模运算是对这道题思想的绝佳进阶