脑筋急转弯（Python/Java/C++/Go）

LeetCode 每日一题题解

endlesscheng

2025年6月8日 12:06

题目说：用计算机 $j$ 解锁计算机 $i$ 的前提是 $j<i$ 且 $\textit{complexity}[j] < \textit{complexity}[i]$。

观察：

一开始就解锁的只有计算机 $0$。
第一轮，被 $0$ 解锁的计算机（记作集合 $A$），密码复杂度比 $\textit{complexity}[0]$ 大。
第二轮，被集合 $A$ 中的计算机解锁的计算机（记作集合 $B$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
第三轮，被集合 $B$ 中的计算机解锁的计算机（记作集合 $C$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
依此类推，所有被解锁的计算机的密码复杂度都要比 $\textit{complexity}[0]$ 大。

定理：当且仅当计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，才能解锁所有计算机。

充分性：如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，根据题意，仅用计算机 $0$ 便可解锁所有计算机。

必要性：如果可以解锁所有的计算机，那么计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大。考虑其逆否命题，即如果在计算机 $0$ 的右边存在计算机 $A$，满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，那么不可能解锁计算机 $A$，更不可能解锁所有计算机。为了解锁计算机 $A$，我们需要在其左边找比 $\textit{complexity}[i]$ 更小的计算机。不断往左找，计算机的密码复杂度只会更小，直到找到一台被计算机 $0$ 解锁的计算机 $B$。$B$ 的密码复杂度必须比 $\textit{complexity}[0]$ 大，但为了能解锁计算机 $A$，$B$ 的密码复杂度又要 $< \textit{complexity}[i] \le \textit{complexity}[0]$，矛盾，所以不可能解锁计算机 $A$。

根据定理，如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，那么我们可以按照任意顺序解锁这 $n-1$ 台计算机，方案数为 $n-1$ 个不同物品的全排列个数，即

$$
(n-1)!
$$

注意取模。关于模运算的知识点，见模运算的世界：当加减乘除遇上取模。

###py

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        MOD = 1_000_000_007
        ans = 1
        for i in range(1, len(complexity)):
            if complexity[i] <= complexity[0]:
                return 0
            ans = ans * i % MOD
        return ans

###java

class Solution {
    public int countPermutations(int[] complexity) {
        final int MOD = 1_000_000_007;
        long ans = 1;
        for (int i = 1; i < complexity.length; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % MOD;
        }
        return (int) ans;
    }
}

###cpp

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        const int MOD = 1'000'000'007;
        long long ans = 1;
        for (int i = 1; i < complexity.size(); i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % MOD;
        }
        return ans;
    }
};

###go

func countPermutations(complexity []int) int {
const mod = 1_000_000_007
ans := 1
for i := 1; i < len(complexity); i++ {
if complexity[i] <= complexity[0] {
return 0
}
ans = ans * i % mod
}
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{complexity}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。

更多相似题目，见下面思维题单的「§5.2 脑筋急转弯」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

阅读视图

复杂度分析

分类题单