LeetCode 题解工作台
猴子碰撞的方法数
现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。 每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是： 顺时针方向的顶点 (i + 1) % n ，或 逆时针方向的顶点 (i - 1…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数学·递归
答案摘要
根据题目描述，每一只猴子都有两种移动方式，即顺时针或逆时针。因此，一共有 种移动方式。不碰撞的移动方式只有两种，即所有猴子都顺时针移动或所有猴子都逆时针移动。因此，碰撞的移动方式有 $2^n - 2$ 种。 我们可以用快速幂求出 的值，然后用 $2^n - 2$ 求出碰撞的移动方式数，最后对 $10^9 + 7$ 取余即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·递归 题型思路
题目描述
现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。
每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：
- 顺时针方向的顶点
(i + 1) % n，或 - 逆时针方向的顶点
(i - 1 + n) % n。
如果移动后至少有两只猴子停留在同一个顶点上或者相交在一条边上，则会发生 碰撞 。
返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。
注意，每只猴子只能移动一次。
示例 1：
输入：n = 3 输出：6 解释：共计 8 种移动方式。 下面列出两种会发生碰撞的方式： - 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。 - 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。 可以证明，有 6 种让猴子碰撞的方法。
示例 2：
输入：n = 4 输出：14 解释：可以证明，有 14 种让猴子碰撞的方法。
提示：
3 <= n <= 109
解题思路
方法一：数学（快速幂）
根据题目描述，每一只猴子都有两种移动方式，即顺时针或逆时针。因此，一共有 种移动方式。不碰撞的移动方式只有两种，即所有猴子都顺时针移动或所有猴子都逆时针移动。因此，碰撞的移动方式有 种。
我们可以用快速幂求出 的值，然后用 求出碰撞的移动方式数，最后对 取余即可。
时间复杂度 ，其中 为猴子的数量。空间复杂度 。
class Solution:
def monkeyMove(self, n: int) -> int:
mod = 10**9 + 7
return (pow(2, n, mod) - 2) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the recursive method used. Direct enumeration is exponential, but dynamic programming or combinatorial formulas reduce it to O(n) space and O(n) time. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasizes counting with recursion and modular arithmetic.
- question_mark
Checks if candidate recognizes collisions on edges as well as vertices.
- question_mark
Wants efficient handling for very large n using math patterns.
常见陷阱
外企场景- error
Forgetting edge collisions between monkeys.
- error
Attempting to enumerate all 2^n configurations for large n.
- error
Incorrect modulo operations causing overflow.
进阶变体
外企场景- arrow_right_alt
Compute collisions on a circular track instead of polygon vertices.
- arrow_right_alt
Count configurations where exactly k collisions occur.
- arrow_right_alt
Handle polygons with some fixed vertices blocked.