当前位置：首页 > news >正文

Swift 解题：LeetCode 372 超级次方（Super Pow）

news 2025/9/6 9:54:37

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 代码解析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

在算法题里，有一些问题看似“简单”，比如算一个幂次方，但一旦放大规模就完全不同了。LeetCode 372 超级次方就是这样的题目。普通的幂运算没什么难度，但当指数 b 是一个用数组表示的上千位数字时，直接计算会导致溢出或者运行缓慢。本文会结合 Swift 给出可运行的解题方案，并分析其原理和实际应用场景。

描述

题目的要求是：
计算 a^b % 1337，其中：

a 是一个正整数（范围在 1 到 2³¹-1 之间）
b 是一个非常大的正整数，并且用数组形式存储（数组每一位是 b 的十进制数字）。

举几个例子：

a = 2, b = [3] → 2^3 % 1337 = 8
a = 2, b = [1,0] → 2^10 % 1337 = 1024
a = 1, b = [4,3,3,8,5,2] → 无论怎么幂次，结果都是 1
a = 2147483647, b = [2,0,0] → 结果 1198

核心难点：

b 太大了，不能直接转成整数再做幂运算。
普通幂运算会溢出，需要用模幂运算（modular exponentiation）。
幂运算的拆分技巧：
- a^(b1b2...bn) = ((a^(b1b2...bn-1))^10 * a^bn) % mod

题解答案

这题的关键在于“分治 + 快速幂 + 模运算”。
我们要不断从 b 的最后一位往前处理，把指数拆分为小块，然后应用公式：

a^1234 = ((a^123)^10) * a^4

这样我们就能一位一位处理 b，避免溢出。

题解代码分析

下面是 Swift 的解法：

import Foundationclass Solution {private let MOD = 1337func superPow(_ a: Int, _ b: [Int]) -> Int {return helper(a % MOD, b)}private func helper(_ a: Int, _ b: [Int]) -> Int {if b.isEmpty { return 1 }// 取出最后一位var newB = blet lastDigit = newB.removeLast()// 计算 (a^lastDigit % MOD)let part1 = modPow(a, lastDigit)// 计算 ((a^rest)^10 % MOD)let part2 = modPow(helper(a, newB), 10)return (part1 * part2) % MOD}// 快速幂取模private func modPow(_ base: Int, _ power: Int) -> Int {var result = 1var b = base % MODvar p = powerwhile p > 0 {if p % 2 == 1 {result = (result * b) % MOD}b = (b * b) % MODp /= 2}return result}
}

代码解析

superPow：入口函数，先对 a 取模，避免不必要的大数计算。
helper：递归函数，把数组 b 的最后一位拿出来处理。
- part1 = a^lastDigit % MOD
- part2 = (a^rest)^10 % MOD
- 然后组合结果 (part1 * part2) % MOD
modPow：快速幂函数，通过二分法计算 (base^power) % MOD，避免指数过大。

这种写法巧妙地利用了指数展开公式和快速幂，既避免了大数溢出，也保证了运行效率。

示例测试及结果

我们用几个例子跑一下：

let solution = Solution()print(solution.superPow(2, [3]))              // 输出: 8
print(solution.superPow(2, [1,0]))           // 输出: 1024
print(solution.superPow(1, [4,3,3,8,5,2]))   // 输出: 1
print(solution.superPow(2147483647, [2,0,0])) // 输出: 1198