力扣第254场周赛
题一 作为子字符串出现在单词中的字符串数目
描述
给你一个字符串数组 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 <= 100 1 <= patterns[i].length <= 100 1 <= word.length <= 100 patterns[i] 和 word 由小写英文字母组成
思路
直接遍历判断。
代码
/**
* @author mikusugar
*/
public class N1 {
public int numOfStrings(String[] patterns, String word) {
int res = 0;
for (String str : patterns) {
if (word.contains(str)) res++;
}
return res;
}
}
题二 构造元素不等于两相邻元素平均值的数组
描述
给你一个 下标从 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
思路
乱搞过了，感觉有问题
代码
/**
* @author mikusugar
*/
public class N2 {
public int[] rearrangeArray(int[] nums) {
for (int i=1;i<nums.length-1;i++){
if(check(i,nums))continue;
for (int k= nums.length-1;k>=i+1;k--){
swap(i,k,nums);
if(check(i,nums)&&check(i-1,nums))break;
swap(i,k,nums);
}
if(check(i,nums))continue;
for (int k=0;k<=i-1;k++){
swap(k,i,nums);
if(check(k-1,nums)&&check(k,nums)&&check(k+1,nums)&&check(i,nums)&&check(i-1,nums))break;
swap(k,i,nums);
}
}
return nums;
}
private void swap(int i,int j,int[] nums){
int tar= nums[i];
nums[i]=nums[j];
nums[j]=tar;
}
private boolean check(int i, int[] nums) {
if(i<=0||i>= nums.length-1)return true;
return nums[i]*1.0!=(nums[i-1]+nums[i+1])/2.0;
}
}
题三 数组元素的最小非零乘积
描述
给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：
从 nums 中选择两个元素 x 和 y 。 选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。 比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。
请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 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 <= 60
思路
最后一个数不变，把剩下的数一半变成1，一半变成11...110
不知道怎么证明。。。直觉。
具体求解用快速冥。
注意溢出
代码
/**
* @author mikusugar
*/
public class N3 {
private final static int MOD = (int) (1e9 + 7);
public int minNonZeroProduct(int p) {
long res = fastPow(2, p, MOD) - 1;
long res1 = fastPow(fastPow(2, p, MOD) - 2, (fastPow(2, p) - 2) / 2, MOD);
return (int) (res * res1 % MOD);
}
private long fastPow(long a, long b) {
if (b == 0) return 1;
long res = fastPow(a, b / 2);
if (b % 2 == 1) return res * res * a;
return res * res;
}
private long fastPow(long a, long b, long m) {
if (b == 0) return 1;
long res = fastPow(a, b / 2, m) % m;
if (b % 2 == 1) return res * res % m * a % m;
return res * res % m;
}
}
题四 你能穿过矩阵的最后一天
描述
给你一个下标从 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 * 10^4 4 <= row * col <= 2 * 10^4 cells.length == row * col 1 <= ri <= row 1 <= ci <= col cells 中的所有格子坐标都是 唯一 的。
思路
一开始的思路是 动态规划，想错了🙅♂️，推不出公式来。
题目意思也理解错了，我一开始以为移动一次要一天。。。
正确思路：
二分+BFS
以后看到这种求最值的问题要想想二分能不能用。
代码
/**
* @author mikusugar
*/
public class N4 {
public int latestDayToCross(int row, int col, int[][] cells) {
int[][] book = new int[row + 2][col + 2];
for (int i = 0; i < cells.length; i++) {
book[cells[i][0]][cells[i][1]] = i + 1;
}
int left = 0, right = cells.length - 1;
int res = 0;
while (left <= right) {
int day = (left + right) / 2;
if (check(day, book, row, col)) {
left = day + 1;
res = day;
} else right = day - 1;
}
return res;
}
private boolean check(int day, int[][] book, int row, int col) {
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] been = new boolean[book.length][book[0].length];
for (int i = 1; i <= col; i++) {
if (book[1][i] <= day) continue;
queue.add(new int[]{1, i});
been[1][i]=true;
}
while (!queue.isEmpty()) {
final int[] cur = queue.poll();
if (cur[0] == row) return true;
for (int[] next : NEXTS) {
int i = cur[0] + next[0];
int j = cur[1] + next[1];
if (i < 1 || i > row || j < 1 || j > col || day >= book[i][j] || been[i][j])
continue;
been[i][j]=true;
queue.add(new int[]{i, j});
}
}
return false;
}
private final static int[][] NEXTS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
}