算法周赛笔记（8月第2周）— LeetCode 第254场周赛

迷南。 2022-09-05 05:25 151阅读 0赞

### 文章目录 ###

*   *  小结
     *  题目
     *   *  1967
         *  1968
         *  1969
         *  1970

## 小结 ##

本周只参加了一场LeetCode周赛

还是先说战绩：2道题。/(ㄒoㄒ)/~~

**本周题目考察的知识点**：

*  字符串匹配
 *  快速幂
 *  并查集

## 题目 ##

### 1967 ###

[作为子字符串出现在单词中的字符串数目][Link 1]

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

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

**示例1**：

> 输入：patterns = \[“a”,“abc”,“bc”,“d”\], word = “abc”  
> 输出：3  
> 解释：
> 
>  *  “a” 是 “abc” 的子字符串。
>  *  “abc” 是 “abc” 的子字符串。
>  *  “bc” 是 “abc” 的子字符串。
>  *  “d” 不是 “abc” 的子字符串。
> 
> patterns 中有 3 个字符串作为子字符串出现在 word 中。

**题解**（Java）

解法一：调API

class Solution { 
        public int numOfStrings(String[] patterns, String word) { 
    		int ans = 0;
    		for (String p : patterns) { 
    			if (word.contains(p)) ans++;
    		}
    		return ans;
    	}
    }

解法二：暴力匹配

class Solution { 
        public int numOfStrings(String[] patterns, String word) { 
    		int ans = 0;
    		for (String p : patterns) { 
    			if (check(p, word)) ans++;
    		}
    		return ans;
    	}
    
    	private boolean check(String p, String s) { 
    		int i, j;
    		// 注意结束位置, 防止越界
    		for (i = 0; i < s.length() - p.length() + 1; i++) { 
    			for (j = 0; j < p.length(); j++) { 
    				if (s.charAt(i + j) != p.charAt(j)) break;
    			}
    			if (j == p.length()) return true;
    		}
    		return false;
    	}
    }

解法三：KMP

KMP代码模板参考 [一文看懂KMP算法][KMP]

class Solution { 
        public int numOfStrings(String[] patterns, String word) { 
    		int ans = 0;
    		for (String p : patterns) { 
    			if (check(p, word)) ans++;
    		}
    		return ans;
    	}
    
    	private boolean check(String p, String s) { 
    		// 求解 next 数组
    		int[] next = new int[p.length()];
    		next[0] = -1;
            // 从第二个位置开始匹配
    		for (int i = 1, j = -1; i < p.length(); i++) { 
    			while (j >= 0 && p.charAt(i) != p.charAt(j + 1)) j = next[j];
    			if (p.charAt(i) == p.charAt(j + 1)) j++;
    			next[i] = j;
    		}
    
    		// 进行匹配
    		for (int i = 0, j = -1; i < s.length(); i++) { 
    			while (j >= 0 && s.charAt(i) != p.charAt(j + 1)) j = next[j];
    			if (s.charAt(i) == p.charAt(j + 1)) j++;
    			if (j == p.length() - 1) return true;
    		}
    		return false;
    	}
    }

### 1968 ###

[构造元素不等于两相邻元素平均值的数组][Link 2]

给你一个 **下标从 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

**题解**：

这是一道找规律的题目。由题干可知，数组中的每个数都**互不相同**，那么，对于一个数`a`，假设其左侧的数是`b`，右侧的数是`c`，若要满足`a`等于其左右两侧的数的平均值，则`b`，`c`这两个数中，一定有一个大于`a`，另一个小于`a`。

即，对于 `[b, a, c]`，若`a`恰好等于两侧数的平均值，则必然有

`b < a < c`，或者`b > a > c`

那么，若要打破这一条件，只需要`a`两侧的数，都比`a`大，或者都比`a`小（当然，也可以有其他的方式，比如将`a`，`b`，`c`其中的任意一个，与其他任意一个数交换，由于每个数都不相同，则这个等式一定会被打破，但这种方式不具有可操作性）。只要保证`a`两侧的数，都比它大，或者都比它小，那么一定是可以打破`a = (b + c) / 2`这个条件的。

于是，我们可以将数组先排序，然后从中间切开，把数组分为较小的一半，和较大的一半，然后将较大部分中的数，依次插入到较小部分的数之间的空隙（或者反之），即可构造完毕。（较大的数的两侧，都是来自左半部分的较小的数，较小的数的两侧，都是来自右半部分较大的数）。

例如，对于示例1，排序后的数组是 `1,2,3,4,5`，从中间切开，左侧较小的部分为`1,2,3`，右侧较大的部分为`4,5`，只需要将一部分插入到另一部分的空隙中，即可构造出满足条件的答案，如下

`1 2 3`

`4 5`

结果为：`1,4,2,5,3`

对于示例2，排序后为`0,2,6,7,9`，从中间切开，左侧为`0,2,6`，右侧为`7,9`，进行插入

`0 2 6`

`7 9`

结果为：`0,7,2,9,6`

Java代码

class Solution { 
        public int[] rearrangeArray(int[] nums) { 
    		Arrays.sort(nums);
    		int[] ans = new int[nums.length];
    		int j = 0;
    		int low, high, mid;
    		low = 0;
    		mid = high = (nums.length + 1) / 2;
    		while (low < mid && high < nums.length) { 
    			ans[j++] = nums[low++];
    			ans[j++] = nums[high++];
    		}
    		if (low < mid) ans[j] = nums[low];
    		return ans;
    	}
    }

### 1969 ###

[数组元素的最小非零乘积][Link 3]

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

*  从 `nums` 中选择两个元素 `x` 和`y` 。
 *  选择 `x` 中的一位与 `y` 对应位置的位交换。对应位置指的是两个整数 **相同位置** 的二进制位。

比方说，如果 `x = 1101` 且 `y = 0011` ，交换右边数起第 `2` 位后，我们得到 `x = 1111` 和 `y = 0001` 。

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

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

**题解**：

这样考虑：我们选择交换`x`和`y`的某一个二进制位，当`x`和`y`的二进制位相同时，交换无意义。

所以只需要考虑`0`和`1`的交换。

我们不妨设交换的是`x`的第`k`个（假设下标从`0`开始）二进制位`0`，与`y`的第`k`个二进制位`1`

其实做的就是将`x`减掉2k ，将`y`加上2k ，可以注意到：`x`和`y`的总和是不变的。

容易得到这样一个结论：**当两数之和固定时，两数的乘积在两数相等时取得最大值，两数相差越大，乘积越小。**

比如`x + y = 6`，我们可以枚举所有可能的`{x,y}`：`1 × 5 = 6`，`2 × 4 = 8`，`3 × 3 = 9`。

更一般的，我们可以绘制 `x + y = c`（`c`是个固定值）时，`x × y` 的函数图像。

假设`c = 10`，即`x + y = 10`，则`x × y = x × (10 - x) = -x^2 + 10x`

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][]

可得知，在`x=5`时（即`x=y`时），乘积取得最大值，越往两边走（`x`与`y`相差越大），乘积越小。

对于一个数`p`，数组`nums`包含了`[1, 2^p - 1]`区间内的所有数。我们先随便观察一下输入数据。

`p=2`，则数组`nums`全部的数如下（二进制表示）

`01`

`10`

`11`

`p=3`，则数组`nums`如下

`001`

`010`

`011`

`100`

`101`

`110`

`111`

容易知道，`nums`中的数一共有`2^p - 1`个，且在第`2^(p-1)`的位置（二进制首位为`1`，后续位全为`0`的这个数的位置），可以将整个`nums`数组一分为二。

根据我们上面的分析，执行交换操作，并不会改变整个`nums`数组的和。而要使得整个`nums`数组的乘积最小，那么需要尽可能地将数组中的数进行**两极分化**，由于要求乘积**非零**。则我们两极分化的极限：就是将某一个数拉到最小值`1`，而将另一个是拉到最大值`2^p - 2`。这个在接下来进行说明：

根据上面，我们可以将`nums`数组，划分为两部分：小于`2^(p-1)`的部分，大于等于`2^(p-1)`的部分。我们观察可知，在两部分的数中，我们可以进行配对，除了`1111`这个最大的数本身，总是能够找到两个数，他们的加和等于`2^p-1`（即所有位都全为`1`）。

比如对于`p=2`，我们有`001`和`110`，有`010`和`101`，有`011`和`100`。这些数之间，都是按位取反的关系。我们可以通过交换，将其中一个数变为`111`，将另一个数变为`000`，然后分一个最低位的`1`过去，就形成了相差最大的两个数`001`和`110`。于是我们可以对所有的数进行这样的配对，总共能得到若干个`001`和`110`，以及一个`111`。最终的答案就是，若干个`110`和一个`111`的乘积。

那么一共能凑出多少个`110`呢？我们观察可知，除了`111`这一个数，我们可以将其他所有数，进行两两配对。

所以总共能凑出的`110`这样的数的个数，就等于`(2^p-2)/2` （`nums`的总个数为`2^p-1`，总个数减去一（排除全`1`的那个数），然后两两配对（除以2））

由于`110`这样的数（第二大的数），可以表示为`2^p-2`，一共有`(2^p-2)/2`这么多个`110`这样的数。

所以最小乘积的答案就是： ( 2 p − 2 ) 2 p − 2 2 × ( 2 p − 1 ) (2^p-2)^\{\\frac\{2^p-2\}\{2\}\} \\times (2^p-1) (2p−2)22p−2×(2p−1)

所以这道题，其实就是求幂。我们可以用**快速幂**算法来进行求解。

快速幂在这篇笔记中有提及 -> [Acwing - 算法基础课 （十一）][Acwing - _]

Java代码如下

class Solution { 
        
       final int MOD = 1000000007;
    
    	public int minNonZeroProduct(int p) { 
    		long _2_p = (1L << p); // 2^p
    		long a = _2_p - 2;  // 2^p - 2
    		long b = (_2_p >> 1) - 1;  // 2^(p - 1) - 1
    		long res = qmi(a % MOD, b);
    		return (int) (res * ((_2_p - 1) % MOD) % MOD);
    	}
    	
        // 快速幂算法
    	private long qmi(long a, long b) { 
    		long res = 1;
    		while (b > 0) { 
    			int u = (int) (b & 1);
    			if (u == 1) res = (res * a) % MOD;
    			b = b >> 1;
    			a = a * a % MOD;
    		}
    		return res;
    	}
    }

### 1970 ###

[你能穿过矩阵的最后一天][Link 4]

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

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

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

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

**示例1**：

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

**示例2**：

> 输入：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 天。

**题解**：

判断的是连通性，可以想到用**并查集**，并查集的内容，参考这篇笔记 [Acwing - 算法基础课 - 笔记（五）][Acwing - _ -]

**思路一：反向并查集**

第一天，能够从第一行走到最后一行，即第一行到最后一行是**连通**的。随着时间的推移，陆地逐渐被水淹没，总有那么一天，无法再从第一行走到最后一行，即从**某一天**开始，第一行和最后一行是**不连通**的。

由于题目求解的是能够从第一行走到最后一行的**最后一天**。即，找到第一行和最后一行**能够连通**的最后一天。

我们让时光倒流，倒着看，从最后一天开始往前，则是找到第一行和最后一行能够连通的**第一天**。

为了方便描述，我们将一个坐标，称为一块**土地**，一块土地可能是**陆地**，也可能是**水域**。

从最后一天往前，每一天都有一块土地，由**水域**变成**陆地**。并且最后一天全是**水域**，**陆地**的数量是从**零**开始增长的。

所以，我们可以这样考虑，从最后一天开始，每天都有一块土地变成**陆地**（称这块土地为`A`），我们尝试将这块土地往外扩展（总共可能扩展的方向是：上，下，左，右4个方向），如果`A`的相邻4块土地中，有陆地，则将其连通（并查集的集合合并）。

并且我们新增两个虚拟土地，分别表示**第一行整体**和**最后一行整体**。

当从后往前，处理到某一天时，若发现第一行和最后一行是连通的，则表明这一天就是第一行和最后一行连通的**第一天**。也就是正向来看的，**最后一天**。

Java代码如下

class Solution { 
       /** * 并查集代码模板 * **/
       private int find(int[] parent, int i) { 
           if (parent[i] != i) parent[i] = find(parent, parent[i]);
           return parent[i];
       }
    
        public int latestDayToCross(int row, int col, int[][] cells) { 
            /** * 时光倒流 + 并查集 * 判断连通性 * **/
            // 并查集 + 初始化
            int size = row * col;
            int[] parent = new int[size + 2]; // 用多2个超级节点, 分别表示第一行和最后一行
            for (int i = 0; i < parent.length; i++) parent[i] = i;
            // 新增的2个超级节点下标
            int firstLine = size, lastLine = size + 1;
            // 是否是陆地, 初始值全是false, 全都不是陆地, 即全是水
            boolean[] isLand = new boolean[size];
            // 每次看上下左右共4个地方
            int[] dx = { 1, -1, 0, 0};
            int[] dy = { 0, 0, 1, -1};
            // 从最后一天往前, 每天都有一块水域变成一块陆地
            for (int i = size - 1; i >= 0 ; i--) { 
                int r = cells[i][0] - 1, c = cells[i][1] - 1; //起始坐标从1变为0, 需要多减1
                int pos = r * col + c; // 映射为一维坐标
                isLand[pos] = true; // 这个坐标变为陆地
                // 判断是否是第一行或者最后一行, 若是, 将该节点与超级节点连通
                if (r == 0) parent[find(parent, pos)] = find(parent, firstLine);
                if (r == row - 1) parent[find(parent, pos)] = find(parent, lastLine);
                // 尝试向4个方向走
                for (int j = 0; j < 4; j++) { 
                    int nr = r + dy[j]; // 新的行
                    int nc = c + dx[j]; // 新的列
                    int nPos = nr * col + nc; // 新的一维坐标
                    // 当坐标超出范围, 或者坐标位置不是陆地时, 跳过
                    if (nr < 0 || nr > row - 1 || nc < 0 || nc > col - 1 || !isLand[nPos]) continue;
                    // 坐标有效, 且是陆地, 则连通, 并查集合并
                    parent[find(parent, nPos)] = find(parent, pos);
                    // 检查第一行和最后一行是否连通
                    if (find(parent, firstLine) == find(parent, lastLine)) return i; //其实应该是 i - 1 + 1
                }
            }
            return 1;
        }
    }

**思路二：正向并查集**

一定要倒着做吗？正着做可不可以？答案是可以的。

换一种思路，从第一天开始往后，**水域**逐渐变多。当某一天，**水域**恰好能够**横穿**（横向连通）整个地图，将**陆地**的**上下两部分**切割开，此时就就无法从第一行走到最后一行了，陆地也就不是**纵向连通**的了。

所以，我们可以对**水域**进行连通性判断，当水域**横向连通**整个地图时，就等价于陆地**纵向不连通**。

代码大体上和前一种方法一样。但是**需要特别注意**，一块水域，向外扩展，需要扩展**8个方向**（上下左右，左上，右上，左下，右下）。因为**水域**斜着走，也能够将陆地纵向切断。

Java代码如下

class Solution { 
       /** * 并查集代码模板 * **/
       private int find(int[] parent, int i) { 
           if (parent[i] != i) parent[i] = find(parent, parent[i]);
           return parent[i];
       }
    
        public int latestDayToCross(int row, int col, int[][] cells) { 
            int size = row * col;
            int[] parent = new int[size + 2];
            for (int i = 0; i < parent.length; i++) parent[i] = i;
            // 第一列, 最后一列 
            int firstColumn = size, lastColumn = size + 1;
            boolean[] isWater = new boolean[size];
            // 8 个相邻位置
            int[] dx = { 1, -1, 0, 0, 1, -1, 1, -1};
            int[] dy = { 0, 0, 1, -1, 1, -1, -1, 1};
            // 从第一天开始, 往后遍历
            for (int i = 0; i < size; i++) { 
                int r = cells[i][0] - 1, c = cells[i][1] - 1;
                int pos = r * col + c;
                // 若是第一列 or 最后一列, 就与两个超级节点连通
                if (c == 0) parent[find(parent, pos)] = find(parent, firstColumn);
                if (c == col - 1) parent[find(parent, pos)] = find(parent, lastColumn);
                // 该块土地变成水域
                isWater[pos] = true;
                for (int j = 0; j < 8; j++) { 
                    int nr = r + dy[j];
                    int nc = c + dx[j];
                    int nPos = nr * col + nc;
                    if (nr < 0 || nr > row - 1 || nc < 0 || nc > col - 1 || !isWater[nPos]) continue;
                    // 相邻的坐标有效, 且是水域, 则连通之
                    parent[find(parent, nPos)] = find(parent, pos);
                    if (find(parent, firstColumn) == find(parent, lastColumn)) return i;
                }
            }
            return 1;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/number-of-strings-that-appear-as-substrings-in-word/
[KMP]: https://blog.csdn.net/vcj1009784814/article/details/116662859
[Link 2]: https://leetcode-cn.com/problems/array-with-elements-not-equal-to-average-of-neighbors/
[Link 3]: https://leetcode-cn.com/problems/minimum-non-zero-product-of-the-array-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20220829/fcef5679a87442618f77a30f3552b8a2.png
[Acwing - _]: https://blog.csdn.net/vcj1009784814/article/details/119035186
[Link 4]: https://leetcode-cn.com/problems/last-day-where-you-can-still-cross/
[Acwing - _ -]: https://blog.csdn.net/vcj1009784814/article/details/117811949