Leetcode Weekly Contest Round 247

t4组合数知识盲区，找个时间补一下，还行

T1 5797. 两个数对之间的最大乘积差

题目

两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。
例如，(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。
给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。
返回以这种方式取得的乘积差中的 最大值 。

示例 1：
输入：nums = [5,6,2,7,4]
输出：34
解释：可以选出下标为 1 和 3 的元素构成第一个数对 (6, 7) 以及下标 2 和 4 构成第二个数对 (2, 4)
乘积差是 (6 * 7) - (2 * 4) = 34

示例 2：
输入：nums = [4,2,5,9,7,4,8]
输出：64
解释：可以选出下标为 3 和 6 的元素构成第一个数对 (9, 8) 以及下标 1 和 5 构成第二个数对 (2, 4)
乘积差是 (9 * 8) - (2 * 4) = 64

提示：
4 <= nums.length <= 10^4
1 <= nums[i] <= 10^4

题解

典型贪心，最大的一组减去最小的一组即可

class Solution {
    public int maxProductDifference(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return nums[len - 1] * nums[len - 2] - nums[0] * nums[1];
    }
}

T2 5798. 循环轮转矩阵

题目

给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是偶数；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：

返回执行 k 次循环轮转操作后的矩阵。

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

提示：
m == grid.length
n == grid[i].length
2 <= m, n <= 50
m 和 n 都是偶数
1 <= grid[i][j] <= 5000
1 <= k <= 10^9

题解

骚年，你做过螺旋打印矩阵的题目没？
类似的思路，我们先把一圈的数紫按顺序写入一个ArrayList，再依次延后k个位置，对原数组进行覆盖

k如果太大了，可以预先对本圈大小进行取模
ez~

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int rows = grid.length;
        int cols = grid[0].length;
        int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
        while(top < bottom && left < right){
            List<Integer> list = new ArrayList<>();
            for(int i = left; i < right; i++){
                list.add(grid[top][i]);
            }
            for(int i = top; i < bottom; i++){
                list.add(grid[i][right]);
            }
            for(int i = right; i > left; i--){
                list.add(grid[bottom][i]);
            }
            for(int i = bottom; i > top; i--){
                list.add(grid[i][left]);
            }
            int size = list.size();
            int tmp = k % size;
            int cnt = tmp;
            for(int i = left; i < right; i++){
                grid[top][i] = list.get(cnt);
                cnt = (cnt + 1) % size;
            }
            for(int i = top; i < bottom; i++){
                grid[i][right] = list.get(cnt);
                cnt = (cnt + 1) % size;
            }
            for(int i = right; i > left; i--){
                grid[bottom][i] = list.get(cnt);
                cnt = (cnt + 1) % size;
            }
            for(int i = bottom; i > top; i--){
                grid[i][left] = list.get(cnt);
                cnt = (cnt + 1) % size;
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        return grid;
    }
}

T3 5799. 最美子字符串的数目

题目

如果某个字符串中 至多一个 字母出现奇数次，则称其为最美字符串。

例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。
子字符串 是字符串中的一个连续字符序列。

示例 1：
输入：word = “aba”
输出：4
解释：4 个最美子字符串如下所示：
“aba” -> “a”
“aba” -> “b”
“aba” -> “a”
“aba” -> “aba”

示例 2：

输入：word = “aabb”
输出：9
解释：9 个最美子字符串如下所示：
“aabb” -> “a”
“aabb” -> “aa”
“aabb” -> “aab”
“aabb” -> “aabb”
“aabb” -> “a”
“aabb” -> “abb”
“aabb” -> “b”
“aabb” -> “bb”
“aabb” -> “b”

示例 3：
输入：word = “he”
输出：2
解释：2 个最美子字符串如下所示：
“he” -> “h”
“he” -> “e”

提示：
$1 <= word.length <= 10^5$
word 由从 ‘a’ 到 ‘j’ 的小写英文字母组成

题解

初看题目我们会想到是不是前缀和+二分进行暴力遍历，构造一个int[len][10]数组，枚举各个位置的各字母总数
但是当我们看到word.length达到 $10^5$ 我们就知道这样做会导致TLE，因为复杂度为 $O(n^2)$

继续看，我们发现其实各位置各个字母的个数并不完全是有效信息，我们只需要获取某个区间内字母的数量是奇数还是偶数即可。所以我们构造前缀和时也考虑到这点，每个位置只保存对应字母的奇偶信息
例如，本题中，我采用一个10位的二进制数表示a-j的各位的奇偶。0表示偶数，1表示奇数
我们都知道：

偶数 - 偶数 = 偶数
奇数 - 奇数 = 偶数
偶数 - 奇数 = 奇数
奇数 - 偶数 = 奇数
对于一个状态s，我们去搜索满足这个状态的前继的状态变量t，有两种情况：
s == t，这样子的话，s和t的各字母总数均同奇偶，减出来得到的中间区间必然各字母全偶数，满足条件
s 与 t 的二进制中有一位不同，这样子我们在求解区间时，其余位数相减均为偶，而奇偶不同的该位进行相减得奇数，区间只有一个字母为奇数个
那么如何查询t的个数呢，我们可以构造一个HashMap<Integer, Integer>，之前每个位置每次计算出的前缀和状态和数量信息都计入Map中即可
代码如下：

class Solution {
    public long wonderfulSubstrings(String word) {
        int len = word.length();
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int[] arr = new int[len];
        long res = 0l;
        for(int i = 0; i < len; i++){
            arr[i] = i > 0 ? arr[i - 1]: 0;
            arr[i] ^= (1 << (int)(word.charAt(i) - 'a'));
            if(map.containsKey(arr[i])) res += (long) map.get(arr[i]);
            for(int k = 0; k < 10; k++){
                if((arr[i] >> k) % 2 == 0){
                    int tmp = arr[i] + (1 << k);
                    if(map.containsKey(tmp)) res += (long)map.get(tmp);
                }
                else{
                    int tmp = arr[i] - (1 << k);
                    if(map.containsKey(tmp)) res += (long)map.get(tmp);
                }
            }
            
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        return res;
    }
}

其实状态总共也只有 $2^{10}$ ，共1024种情况，不用HashMap也可以用数组代替

T4 1916. 统计为蚁群构筑房间的不同顺序

题目

你是一只蚂蚁，负责为蚁群构筑 n 间编号从 0 到 n-1 的新房间。给你一个 下标从 0 开始 且长度为 n 的整数数组 prevRoom 作为扩建计划。其中，prevRoom[i] 表示在构筑房间 i 之前，你必须先构筑房间 prevRoom[i] ，并且这两个房间必须直接相连。房间 0 已经构筑完成，所以 prevRoom[0] = -1 。扩建计划中还有一条硬性要求，在完成所有房间的构筑之后，从房间 0 可以访问到每个房间。
你一次只能构筑一个房间。你可以在 已经构筑好的 房间之间自由穿行，只要这些房间是 相连的 。如果房间 prevRoom[i] 已经构筑完成，那么你就可以构筑房间 i。
返回你构筑所有房间的 不同顺序的数目 。由于答案可能很大，请返回对 $10^9 + 7$ 取余的结果。

示例 1：

输入：prevRoom = [-1,0,1]
输出：1
解释：仅有一种方案可以完成所有房间的构筑：0 → 1 → 2

示例 2：

输入：prevRoom = [-1,0,0,1,2]
输出：6
解释：
有 6 种不同顺序：
0 → 1 → 3 → 2 → 4
0 → 2 → 4 → 1 → 3
0 → 1 → 2 → 3 → 4
0 → 1 → 2 → 4 → 3
0 → 2 → 1 → 3 → 4
0 → 2 → 1 → 4 → 3

提示：
$n == prevRoom.length$
$2 <= n <= 10^5$
$prevRoom[0] == -1$
对于所有的 $1 <= i < n$ ，都有 $0 <= prevRoom[i] < n$
题目保证所有房间都构筑完成后，从房间 0 可以访问到每个房间

题解

高中排列组合数学没学好。。。递归子问题找到了却连方程都列不对

设 f[i] 表示以节点 i 为根的子树的拓扑排序方案数，那么
任意一种拓扑排序中的第一个节点一定是节点 ii；

假设节点 i 有子节点ch0, ch1, … chk,这 k+1 棵子树，它们均有若干种拓扑排序的方案。如果我们希望把这些子树的拓扑排序方案「简单地」合并到一起，可以使用乘法原理，即方案数为：
f[ch0] * f[ch1] * .... * f[chk]

但是简单相乘只能表示树的最终结构和自身顺序，事实上组成这k+1棵树的方法还要细分，例如，我先拓展ch0上的节点，再拓展chk的节点，再拓展别的节点…（顺序不定还能产生多种方法）。

简单的排列数学：
排列数计算。假设有 a0个物品 0，a1个物品 1，…，an−1个物品 n-1，我们需要将它们排成一排，那么方案数为 $\frac{(a_0 + a_1 + .. + a_{n-1})!}{a_0! * a_1! * ... * a_{n-1}!}$

对于已经被确定结构和自身顺序的ch0, ch1,…, chk子树，类似的，我们确定每棵树的节点个数cnt[ch1] cnt[ch2] … cnt[chk]，（注意这是在每棵树的结构和自身顺序已经被确定的前提下），我们得到排列的种数为 $\frac{(cnt[i] - 1)!}{cnt[ch_0]! * cnt[ch_1]! * ... * cnt[ch_k]!}$

所以我们要把两个公式乘起来就是i节点的总解数了

而当我们处理大数相乘时，如本题，会由于数据过大无法计算
因而使用了乘法逆元和费马小定理

乘法逆元：如果需要计算 $\frac{b}{a}$ 对 m 取模的值，b 和 a 均为表达式（例如上面排列数的分子与分母）并且它们实际的值非常大，无法直接进行计算，那么我们可以求出 a 在模 m 意义下的乘法逆元 $a^{-1}$

费马小定理：
当 m 为质数时，
$a^{m−1} ≡1 (mod m) \Longrightarrow a^{m−2} ≡ a^{-1} (mod m)$
即 $a^{-1}$ 就等于 $a^{m-2}$ 对 m 取模的结果
题中 $m = 1000000007$ 满足条件

代码如下：

class Solution {

    private static final int BASE = 1000000007;

    private Map<Integer, Set<Integer>> neighbors = new HashMap<>();

    public int waysToBuildRooms(int[] prevRoom) {
        int n = prevRoom.length;
        int[] deg = new int[n];
        for(int i = 0; i < n; i++) {
            if(prevRoom[i] < 0) continue;
            Set<Integer> set = neighbors.computeIfAbsent(prevRoom[i], k -> new HashSet<>());
            set.add(i);
            deg[prevRoom[i]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] dp = new int[n];
        int[] sizes = new int[n];
        Arrays.fill(sizes, 1);
        for(int i = 0; i < n; i++) {
            if(deg[i] == 0) {
                queue.offer(i);
            }
        }
        int[] fac = new int[n + 1];
        Arrays.fill(fac, 1);
        int[] ifac = new int[n + 1];
        Arrays.fill(ifac, 1);
        for(int i =2; i <= n; i++) {
            fac[i] = (int)((long) i * fac[i - 1] % BASE);
        }
        for(int i = 2; i <= n; i++) {
            ifac[i] = power(fac[i], BASE - 2);
        }
        while(!queue.isEmpty()) {
            int u = queue.poll();
            int p = prevRoom[u];
            if(p >= 0) {
                sizes[p] += sizes[u];
                if(--deg[p] == 0) {
                    queue.offer(p);
                }
            }
            int cnt = fac[sizes[u] - 1];
            Set<Integer> childSet = neighbors.get(u);
            if(childSet != null) {
                for(int v : childSet) {
                    cnt = (int)((long)cnt * ifac[sizes[v]] % BASE);
                    cnt = (int)((long)cnt * dp[v] % BASE);
                }
            }
            dp[u] = cnt;
        }
        return dp[0];
    }

    private int power(int x, int n) {
        long res = 1;
        for(int i = n; i > 0; i /= 2) {
            if(i % 2 == 1) res = res * x % BASE;
            x = (int)(1L *x * x % BASE);
        }
        return (int)res;
    }
}