【 NO.1 作为子字符串出现在单词中的字符串数目】
解题思路
签到题，枚举、统计即可。
代码展示
class Solution {
public int numOfStrings(String[] patterns, String word) {
int cnt = 0;
for (String p : patterns) {
if (word.contains(p)) {
cnt++;
}
}
return cnt;
}
}
【 NO.2 构造元素不等于两相邻元素平均值的数组】
解题思路
按照一大一小的顺序重排数组即可，这样一个数字相邻的数字要么都比它大，要么都比它小。
代码展示
class Solution {
public int[] rearrangeArray(int[] nums) {
Arrays.sort(nums);
LinkedList list = new LinkedList<>();
for (int num : nums) {
list.add(num);
}
int[] res = new int[nums.length];
for (int i = 0; i < res.length; i++) {
if (i % 2 == 0) {
res[i] = list.pollFirst();
} else {
res[i] = list.pollLast();
}
}
return res;
}
}
【 NO.3 数组元素的最小非零乘积】
解题思路
最终一定是若干个 1、1 个 $2^p - 1$、若干个 $2^p - 2$，并且 $2^p - 2$ 的数量和 1 的数量相等。
即最终结果是 $(2^p - 2)^{(2^{p-1} - 1)} * (2^p - 1)$
使用快速幂计算即可。
代码展示
class Solution {
public int minNonZeroProduct(int p) {
if (p == 1) {
return 1;
}
// 2^(p-1) - 1 个 1
// (2^p - 2)^(2^(p-1) - 1) * (2^p - 1)
long mod = (long) 1e9 + 7;
long a = (pow(2, p, mod) + mod - 2) % mod;
a = pow2(a, 2, p - 1, 1, mod);
long c = (pow(2, p, mod) + mod - 1) % mod;
return (int) (a * c % mod);
}
private long pow2(long a, long x, long y, long z, long mod) {
// calc a^(x^y - z) % mod
// x = 2, z = 1 or 0
if (y <= 2) {
long p = pow(x, y, mod) - z;
return pow(a, p, mod);
}
if (z == 0) {
return pow(pow2(a, x, y - 1, z, mod), 2, mod);
} else {
long t = pow2(a, x, y - 1, z, mod);
long t2 = pow2(a, x, y - 1, z - 1, mod);
return t * t2 % mod;
}
}
long pow(long a, long b, long p) {
if (b == 0) {
return 1;
}
if (b == 1) {
return a % p;
}
long t = pow(a, b / 2, p);
t = t * t % p;
if (b % 2 == 0) {
return t;
}
return t * a % p;
}
}
【 NO.4 你能穿过矩阵的最后一天】
解题思路
二分答案，然后 BFS 判断可达性。
代码展示
class Solution {
public int latestDayToCross(int row, int col, int[][] cells) {
int l = 0, r = cells.length;
while (l + 1 < r) {
int m = (l + r) / 2;
if (check(row, col, cells, m)) {
l = m;
} else {
r = m;
}
}
return check(row, col, cells, r) ? r : l;
}
private boolean check(int row, int col, int[][] cells, int m) {
final int[] dx = {0, 0, 1, -1};
final int[] dy = {1, -1, 0, 0};
boolean[][] mp = new boolean[row][col];
for (int i = 0; i < m; i++) {
int[] cell = cells[i];
mp[cell[0] - 1][cell[1] - 1] = true;
}
boolean[][] vis = new boolean[row][col];
Queue queue = new LinkedList<>();
for (int i = 0; i < col; i++) {
if (!mp[0][i]) {
queue.add(0);
queue.add(i);
vis[0][i] = true;
}
}
while (!queue.isEmpty()) {
int x = queue.poll();
int y = queue.poll();
if (x == row - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= row || ny >= col || mp[nx][ny] || vis[nx][ny]) {
continue;
}
vis[nx][ny] = true;
queue.add(nx);
queue.add(ny);
}
}
return false;
}
}
杭州上岸算法网络科技有限公司
上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。
创作新主题