题目不是很难，但是有点小问题还是要说说的

T1 5843. 作为子字符串出现在单词中的字符串数目

题目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：patterns = [“a”,“abc”,“bc”,“d”], word = “abc”
输出：3
解释：

  • “a” 是 “abc” 的子字符串。
  • “abc” 是 “abc” 的子字符串。
  • “bc” 是 “abc” 的子字符串。
  • “d” 不是 “abc” 的子字符串。
    patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = [“a”,“b”,“c”], word = “aaaaabbbbb”
输出：2
解释：

  • “a” 是 “aaaaabbbbb” 的子字符串。
  • “b” 是 “aaaaabbbbb” 的子字符串。
  • “c” 不是 “aaaaabbbbb” 的字符串。
    patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = [“a”,“a”,“a”], word = “ab”
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word “ab” 中。

提示：

1≤patterns.length≤1001 \leq patterns.length \leq 100
1≤patterns[i].length≤1001 \leq patterns[i].length \leq 100
1≤word.length≤1001 \leq word.length \leq 100
patterns[i]patterns[i] 和 wordword 由小写英文字母组成

题解

典型API题，别动脑子，写就完事了～

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int len = patterns.length;
        int cnt = 0;
        for(int i = 0; i < len; i++){
            if(word.indexOf(patterns[i]) != -1) cnt++;
        }
        return cnt;
    }
}

T2 5832. 构造元素不等于两相邻元素平均值的数组

题目

给你一个 下标从 0 开始 的数组 nums ，数组由若干 互不相同的 整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都 不等于 其两侧相邻元素的 平均值 。

更公式化的说法是，重新排列的数组应当满足这一属性：对于范围 1 <= i < nums.length - 1 中的每个 i ，(nums[i-1] + nums[i+1]) / 2 不等于 nums[i] 均成立 。

返回满足题意的任一重排结果。

示例 1：

输入：nums = [1,2,3,4,5]
输出：[1,2,4,5,3]
解释：
i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5

示例 2：

输入：nums = [6,2,0,9,7]
输出：[9,7,6,2,0]
解释：
i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3

提示：

3≤nums.length≤1053 \leq nums.length \leq 10^5
0≤nums[i]≤1050 \leq nums[i] \leq 10^5

题解

初看好像没啥想法，但是凭借我们丰富的刷题经验，我们想到了一个非常匹配的数列特征（锯齿数列）

只要保证一高一低，一高一低，相邻的两数平均值必不可能与当前数字相等

代码如下，我们可以通过排序加奇偶排列的方式来保证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] rearrangeArray(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        Arrays.sort(nums);
        int t = 0;
        for(int i = 0; i < len; i += 2){
            res[i] = nums[t++];
        }
        for(int i = 1; i < len; i += 2){
            res[i] = nums[t++];
        }
        return res;
    }
}

T3 5844. 数组元素的最小非零乘积

题目

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1,2p−1][1, 2^p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：

从 nums 中选择两个元素 x 和 y 。
选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。
比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109+710^9 + 7 取余 后返回。

注意：答案应为取余 之前 的最小值。

示例 1：

输入：p = 1
输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。

示例 2：

输入：p = 2
输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。

示例 3：

输入：p = 3
输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]

  • 第一次操作中，我们交换第二个和第五个元素最左边的数位。
    • 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
  • 第二次操作中，我们交换第三个和第四个元素中间的数位。
    • 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
      数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。

提示：

1≤p≤601 \leq p \leq 60

题解

也许有同学已经通过样例2和3感觉出什么情况来了，好像我们的最终结果必然是一个最大值2p−12^p - 1，剩余的所有位置平分11和2p−22^p - 2，这样的情况是最优的。

这里借用灵茶山艾府大佬的题解，先暂时贴一下：

首先，两个交换的比特必须是不同的，否则交换无影响。

不失一般性，假设 x 参与交换的比特为 0，y 参与交换的比特为 1，交换的位置为第 k 位。

记 y=y′+2ky = y' + 2^k ，则交换前，两数的乘积为x∗y=x∗(y′+2k)=x∗y′+x∗2kx * y = x * (y' + 2^k) = x * y' + x * 2^k

交换后，两数的乘积为

(x+2k)(y−2k)=(x+2k)∗y′=x∗y′+y′∗2k(x + 2^k)(y - 2^k) = (x + 2^k) * y' = x * y' + y' * 2^k

对比两个等式可知，要使交换后乘积变小，需要满足x>y′x > y'

这一不等式表明，对于一个数 y，如果我们不断地将其二进制中的 1 与另一个满足该不等式的数交换，就可以将乘积不断减小。由于题目要求计算最小非零乘积，我们可以先将 y 减小至 0，然后再寻找一个最低位为 1 的数进行交换，从而让 y 变成 1。

由于 nums 包含了 [1,2p−1][1, 2^p - 1] 内的所有整数，我们可以将其分为两组，小于 2p−12^{p-1}的为一组，记作 A，其余的为另一组，记作 B。则 B 组中除了 2p−12^p-1之外，其余的数均可以和 A 组中的数一一配对，要求配对的两个数之和为 2p−12^p-1。每对配对的数就可以按照上述交换流程交换，交换后的结果为 1 和 2p−22^p-2。

交换后，每一对的乘积为 2p−22^p-2，这一共有 2p−1−12^{p-1}-1对，再算上不参与配对的 2p−12^p-1，得到最小乘积为

(2p−1)∗(2p−2)2p−1−1(2^p - 1) * (2^p - 2)^{2^{p - 1} - 1}

具体代码如下：

注意到快速幂很容易发生溢出，请格外小心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    static final long MOD = 1000000007;
    public int minNonZeroProduct(int p) {
        long a = (1L << p) - 1L;
        long b = a - 1L;
        long c = b / 2L;
        long ans = ((a % MOD) * pow(b % MOD, c)) % MOD;
        
        return (int) ans;
    }
    
    public long pow (long b, long c) {
        long ans = 1;
        while (c > 0) {
            if ((c & 1) == 1) {
                ans = (ans * b) % MOD;
            }
            c >>= 1;
            b = (b * b) % MOD;
        }
        return ans;
    }
}

T4 5845. 你能穿过矩阵的最后一天

题目

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成 水域 （也就是 0 变成 1 ）。

你想知道从矩阵最 上面 一行走到最 下面 一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发，到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。

示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

提示：

2≤row,col≤2∗1042 \leq row, col \leq 2 * 10^4
4≤row∗col≤2∗1044 \leq row * col \leq 2 * 10^4
cells.length==row∗colcells.length == row * col
1≤ri≤row1 \leq ri \leq row
1≤ci≤col1 \leq ci \leq col
cells 中的所有格子坐标都是 唯一 的。

题解

在做这道题前，不知道同学有没有勾起你做《算法第四版》课后习题时，我们遇到了一道Percolation的题目，链接如下，有兴趣的同学可以去看看：

Write a program to estimate the value of the percolation threshold via Monte Carlo simulation.

这个开放性问题大概要求为验证一个大致阈值，当全部方格中随机开启的方块数占比小于阈值时就大概率导致上下无法联通。这道题目是通过并查集来实现的。

可以渗滤无法渗滤

大致阈值分布

好了废话不多说，我们现在先来看这道题目。很自然的我们也能想到并查集的做法，那么如何表示上下联通呢，这个问题也很简单，我们使用两个额外的节点直接将上下边界沟通起来，如图所示：

首先，很好理解的是如果有两个相邻的格子同为0，那么我们就认为他们是联通的，也就是进行merge操作

为了表示上下联通的关系情况，我们选择将一个HEAD节点和上层所有节点相连，将BOTTOM节点和底层一行所有节点相连，这样的话只要HEAD和BOTTOM同属一个集合，我们就认为上下联通。

鉴于并查集并不适合删除断连操作，我们决定进行反向操作，从数组的尾部向前进行遍历，从最支离破碎的情形开始，然后一块方块一块方块的拼上去，若有相邻的0方块，则合并，直到上下联通为止也就是BOTTOM和TOP同集合。

代码如下，其中row * col号节点是我们的BOTTOM节点，row * col + 1号节点是我们的TOP节点，：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    class UF{
        int[] parent;
        public UF(int n){
            parent = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
            }
        }
        public int find(int x){
            if(x == parent[x]) return x;
            else return parent[x] = find(parent[x]);
        }
        public void merge(int a, int b){
            int ap = find(a), bp = find(b);
            if(ap == bp) return;
            else parent[ap] = bp;
        }
    }
    public int latestDayToCross(int row, int col, int[][] cells) {
        UF uf = new UF(row * col + 2);
        for(int i = 0; i < col; i++) uf.merge(row * col, (row - 1) * col + i);//BOTTOM节点与最后一行合并
        for(int i = 0; i < col; i++) uf.merge(row * col + 1, i);//TOP节点与第一行合并
        int len = cells.length;
        int[] dir = new int[]{-1, 0, 1, 0, -1};
      //初始化操作
        int[][] arr = new int[row][col];
        for(int i = 0; i < len; i++){
            arr[cells[i][0] - 1][cells[i][1] - 1] = 1;
        }
      //将支离破碎的情况先进行merge合并，该联通的选择联通
        for(int i = 1; i < row - 1; i++){
            for(int j = 1; j < col - 1; j++){
                for(int t = 0; t < 4; t++){
                    int nx = i + dir[t], ny = j + dir[t + 1];
                    if(arr[nx][ny] == 0) uf.merge(col * i + j, col * nx + ny);
                }
            }
        }
      //从后向前遍历数组，一块一块拼
        for(int i = len - 1; i >= 0; i--){
            int x = cells[i][0] - 1, y = cells[i][1] - 1;
            arr[x][y] = 0;
            for(int t = 0; t < 4; t++){
                int nx = x + dir[t], ny = y + dir[t + 1];
                if(nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
                if(arr[nx][ny] == 0) uf.merge(col * x + y, col * nx + ny);
                if(uf.find(row * col) == uf.find(row * col + 1)) return i; 
              //如果拼完了，上下联通了，即为结果
            }
        }
        return 0;
    }
}