1.找出被包含的子字符串个数：
https://leetcode.com/problems/number-of-strings-that-appear-as-substrings-in-word
用内置字符串函数判断即可。
// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Number of Strings That Appear as Substrings in Word.
// Memory Usage: 39.1 MB, less than 75.00% of Java online submissions for Number of Strings That Appear as Substrings in Word.
// .
// T:O(n), S:O(1)
//
class Solution {
public int numOfStrings(String[] patterns, String word) {
int ret = 0;
for (String str: patterns) {
if (word.contains(str)) {
ret++;
}
}
return ret;
}
}
2.移动数组使之任意元素不等于左右相邻元素之平均值：
https://leetcode.com/problems/array-with-elements-not-equal-to-average-of-neighbors
注意题目所说，数组所有元素不相同，要满足这点的答案会有很多种。
我这里直接 shuffle 然后再判断，最小复杂度 O(n)， 平均复杂度 O((k / (k - 1)) * n), k 为 （左右相邻等于自身均值的数组）/ (所有排列数)， 可想而之这个 k 不会太大，所以这个解法能 pass。
// AC:Runtime: 33 ms, faster than 21.43% of Java online submissions for Array With Elements Not Equal to Average of Neighbors.
// Memory Usage: 63.5 MB, less than 21.43% of Java online submissions for Array With Elements Not Equal to Average of Neighbors.
// .
// T:O(n) ~ O(n^2), S:O(n)
//
class Solution {
public int[] rearrangeArray(int[] nums) {
int size = nums.length;
List<Integer> temp = new ArrayList<>(size);
for (int i: nums) {
temp.add(i);
}
while (!check(temp)) {
Collections.shuffle(temp);
}
int[] ret = new int[size];
for (int i = 0; i < temp.size(); i++) {
ret[i] = temp.get(i);
}
return ret;
}
private boolean check(List<Integer> nums) {
for (int i = 1; i < nums.size() - 1; i++) {
if (nums.get(i) * 2 == nums.get(i - 1) + nums.get(i + 1)) {
return false;
}
}
return true;
}
}
3.变换数组内任意两数字的二进制位，使数组整体乘积的非 0 可能值最小：
https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements
这里我没有想出严格的正推思路，竞赛中只能靠观察规律试试。
发现除了 2^p - 1 这个最大值外，每一组最大值和最小值，比如 (2^p - 2, 1), (2^p - 3, 2), 可以通过移动一个 bit，使之全部变为 (2^p - 2, 1) 的乘积对。
这样的移动方式可能就是正确解，验证下 p = 3, 4 没啥问题。可以试试,
这样问题变成了求解：(2^p - 1) * pow((2^p - 2), (2^p - 2) / 2) ，最后结果 mod (1e9 + 7)
代码如下：
// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Non-Zero Product of the Array Elements.
// Memory Usage: 35.4 MB, less than 100.00% of Java online submissions for Minimum Non-Zero Product of the Array Elements.
// 思路：观察规律可以猜测，最小乘积时，除了 2^p - 1 外，剩下的最大值和最小值两两配对，形成 2^p - 2, 共 (2^p - 2) / 2 对。再计算 pow(x, y), 递归计算，复杂度降为 O(n), n 为原指数
// T:O(n), S:O(1)
//
class Solution {
public int minNonZeroProduct(int p) {
long mod = 1000_000_000 + 7, divider = (1L << p) - 1;
long powResult = myPow(divider - 1, (divider - 1) / 2, mod);
int ret = (int) (((divider % mod) * powResult) % mod);
return ret;
}
private long myPow(long x, long y, long mod) {
if (y == 0) {
return 1;
}
long temp = myPow(x, y / 2, mod);
long p = (temp * temp) % mod;
return y % 2 == 1 ? (p * (x % mod)) % mod : p;
}
}
4.求最晚的天数，使得能从水塘的第一行走没水的格子到达最后一行：
https://leetcode.com/problems/last-day-where-you-can-still-cross
图算法题，这块需要补充相关知识，现场碰到有点束手无策。。
答案来源社区讨论帖，可去翻找。
思路：二分查找 + BFS 检查是否满足条件：
// AC: Runtime: 81 ms, faster than 33.33% of Java online submissions for Last Day Where You Can Still Cross.
// Memory Usage: 48 MB, less than 100.00% of Java online submissions for Last Day Where You Can Still Cross.
// binary search & bfs search of graph
// T:(nlogn), S:O(n), n = row * col
//
class Solution {
public int latestDayToCross(int row, int col, int[][] cells) {
int left = 0, right = row * col - 1, ret = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(cells, row, col, mid)) {
ret = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ret;
}
private boolean check(int[][] cells, int row, int col, int day) {
int[][] grid = new int[row][col];
for (int i = 0; i < day; i++) {
grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
}
Queue<int[]> bfs = new ArrayDeque<>();
for (int i = 0; i < col; i++) {
if (grid[0][i] == 0) {
bfs.offer(new int[]{0, i});
grid[0][i] = 1;
}
}
int[] dir = new int[]{0, 1, 0, -1, 0};
while (!bfs.isEmpty()) {
int[] curPoint = bfs.poll();
int curRow = curPoint[0], curCol = curPoint[1];
if (curRow == row - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
int tempRow = curRow + dir[i], tempCol = curCol + dir[i + 1];
if (tempRow < 0 || tempRow >= row || tempCol < 0 || tempCol >= col || grid[tempRow][tempCol] == 1) {
continue;
}
grid[tempRow][tempCol] = 1;
bfs.offer(new int[]{tempRow, tempCol});
}
}
return false;
}
}