❌

阅读视图

发现新文章，点击刷新页面。

[Python3/Java/C++/Go/TypeScript] 一题一解：脑筋急转弯（清晰题解）

✇LeetCode 每日一题题解
lcbin

方法一：脑筋急转弯

由于编号为 $0$ 的计算机密码已经被解锁，那么对于其他计算机 $i$，如果存在 $\text{complexity}[i] \leq \text{complexity}[0]$，则无法解锁计算机 $i$，因此返回 $0$。否则，排列可以是任意的，一共有 $(n - 1)!$ 种排列方式。

###python

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        mod = 10**9 + 7
        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 = (int) 1e9 + 7;
        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 = 1e9 + 7;
        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 {
mod := int64(1e9 + 7)
ans := int64(1)
for i := 1; i < len(complexity); i++ {
if complexity[i] <= complexity[0] {
return 0
}
ans = ans * int64(i) % mod
}
return int(ans)
}

###ts

function countPermutations(complexity: number[]): number {
    const mod = 1e9 + 7;
    let ans = 1;
    for (let i = 1; i < complexity.length; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        ans = (ans * i) % mod;
    }
    return ans;
}

###rust

impl Solution {
    pub fn count_permutations(complexity: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut ans = 1i64;
        for i in 1..complexity.len() {
            if complexity[i] <= complexity[0] {
                return 0;
            }
            ans = ans * i as i64 % MOD;
        }
        ans as i32
    }
}

时间复杂度 $O(n)$，其中 $n$ 是数组 $\text{complexity}$ 的长度。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

每日一题-统计计算机解锁顺序排列数🟡

✇LeetCode 每日一题题解

给你一个长度为 n 的数组 complexity。

在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。

编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：

  • 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
  • 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。

求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。

由于答案可能很大，返回结果需要对 109 + 7 取余数。

注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。

排列 是一个数组中所有元素的重新排列。

 

示例 1：

输入： complexity = [1,2,3]

输出： 2

解释：

有效的排列有：

  • [0, 1, 2]
    • 首先使用根密码解锁计算机 0。
    • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。
    • 使用计算机 1 的密码解锁计算机 2，因为 complexity[1] < complexity[2]。
  • [0, 2, 1]
    • 首先使用根密码解锁计算机 0。
    • 使用计算机 0 的密码解锁计算机 2，因为 complexity[0] < complexity[2]。
    • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。

示例 2：

输入： complexity = [3,3,3,4,4,4]

输出： 0

解释：

没有任何排列能够解锁所有计算机。

 

提示：

  • 2 <= complexity.length <= 105
  • 1 <= complexity[i] <= 109

3577. 统计计算机解锁顺序排列数

✇LeetCode 每日一题题解
stormsunshine

解法

思路和算法

使用已解锁的计算机密码将未解锁的计算机解锁的条件是：已解锁的计算机的编号和密码复杂度分别小于未解锁的计算机的编号和密码复杂度。由于初始时只有编号为 $0$ 的计算机密码已解锁，编号 $0$ 是最小编号，因此对于其他任意编号 $i$，是否可以使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机的情况如下。

  • 当 $\textit{complexity}[i] > \textit{complexity}[0]$ 时，可以使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机。

  • 当 $\textit{complexity}[i] \le \textit{complexity}[0]$ 时，不能使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机。

如果存在 $1 \le i < n$ 的整数 $i$ 满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，则对于任意可以被编号为 $0$ 的计算机密码解锁的计算机的编号 $j$，必有 $\textit{complexity}[j] > \textit{complexity}[0]$，因此 $\textit{complexity}[j] > \textit{complexity}[i]$，即编号为 $j$ 的计算机密码不能解锁编号为 $i$ 的计算机。因此，编号为 $i$ 的计算机无法被解锁，此时无法解锁所有计算机。

如果 $1 \le i < n$ 的所有整数 $i$ 都满足 $\textit{complexity}[i] > \textit{complexity}[0]$，则所有计算机都能被编号为 $0$ 的计算机密码解锁。由于初始时编号为 $0$ 的计算机密码已解锁，因此其余 $n - 1$ 台计算机可以按任意顺序解锁，排列数是 $(n - 1)!$。

代码

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int countPermutations(int[] complexity) {
        long permutations = 1;
        int n = complexity.length;
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return (int) permutations;
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int CountPermutations(int[] complexity) {
        long permutations = 1;
        int n = complexity.Length;
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return (int) permutations;
    }
}

###C++

const int MODULO = 1000000007;

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        long long permutations = 1;
        int n = complexity.size();
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return permutations;
    }
};

###Python

MODULO = 1000000007

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

###C

const int MODULO = 1000000007;

int countPermutations(int* complexity, int complexitySize) {
    long long permutations = 1;
    for (int i = 1; i < complexitySize; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
}

###Go

const MODULO = 1000000007

func countPermutations(complexity []int) int {
    permutations := 1
    n := len(complexity)
    for i := 1; i < n; i++ {
        if complexity[i] <= complexity[0] {
            return 0
        }
        permutations = permutations * i % MODULO
    }
    return permutations
}

###JavaScript

const MODULO = 1000000007;

var countPermutations = function(complexity) {
    let permutations = 1;
    let n = complexity.length;
    for (let i = 1; i < n; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
};

###TypeScript

const MODULO = 1000000007;

function countPermutations(complexity: number[]): number {
    let permutations = 1;
    let n = complexity.length;
    for (let i = 1; i < n; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{complexity}$ 的长度。需要遍历数组一次。

  • 空间复杂度：$O(1)$。

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

✇LeetCode 每日一题题解
endlesscheng

题目说：用计算机 $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 脑筋急转弯」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

分类讨论

✇LeetCode 每日一题题解
tsreaper

解法：分类讨论

因为只能用小 complexity 解锁大 complexity，所以后续解锁的电脑一定满足 complexity[i] > complexity[0]。

换句话说，如果存在 i > 0，使得 complexity[i] <= complexity[0]，那就无法解锁该电脑，答案为 $0$。

否则，所有电脑都能通过电脑 $0$ 解锁，因此后续编号可以任意排列，答案为 $(n - 1)!$。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        int n = complexity.size();

        // 检查是否有无法解锁的电脑
        for (int i = 1; i < n; i++) if (complexity[i] <= complexity[0]) return 0;

        // 计算 (n - 1)!
        const int MOD = 1e9 + 7;
        long long ans = 1;
        for (int i = 1; i < n; i++) ans = ans * i % MOD;
        return ans;
    }
};
❌