快速幂:O(log n) 计算 m 的 n 次方
哪些公司问过
答案要点
- 把指数按二进制拆分,m^n 等于若干 m^(2^k) 的乘积
- 迭代:n 最低位为 1 时结果乘上底数,然后底数平方、n 右移一位
- 时间复杂度 O(log n),迭代写法空间 O(1)
- 边界:n 为 0 返回 1;n 为负取倒数,注意 int 最小值取反溢出
- 大数结果每次乘法后取模,中间结果用 long 防止溢出
易错点
- 负指数直接取反,int 最小值时溢出
- 中间乘积用 int 存储导致溢出
- 只在最后取模,中间过程已经溢出
面试官常见追问
- 快速幂还能用在哪里?
- 为什么取模不影响乘法结果的正确性?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。