第 108 场双周赛
2765. 最长交替子序列
分段
class Solution {
public int alternatingSubarray(int[] nums) {
int res = -1, n = nums.length;
for (int i = 1; i < n; i++) {
// 找每一段第一个
if (nums[i] - nums[i - 1] == 1) {
int left = i - 1, x = nums[left];
while (i < n - 1 && nums[i + 1] == x + (i - left + 1) % 2) i++;
res = Math.max(res, i - left + 1);
}
}
return res;
}
}
2766. 重新放置石块
class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Set<Integer> s = Arrays.stream(nums).boxed().collect(Collectors.toSet());
for (int i = 0; i < moveFrom.length; ++i) {
s.remove(moveFrom[i]);
s.add(moveTo[i]);
}
return s.stream().sorted().toList();
}
}
2767. 将字符串分割为最少的美丽子字符串
class Solution {
String s;
int INF = 0x3f3f3f3f;
static Set<String> set = new HashSet<>();
// 预处理所有 5 的幂的 二进制 表示
static {
for(int i = 0; i < 8; i++){
set.add(Integer.toBinaryString((int)Math.pow(5, i)));
}
}
int[] cache;
public int minimumBeautifulSubstrings(String s) {
this.s = s;
int n = s.length();
cache = new int[n + 1];
Arrays.fill(cache, -1);
int res = backtrack(n);
return res == INF ? -1 : res;
}
// 定义 backtrack(i) 表示分割 s[i:] 的最少数目
public int backtrack(int i){
if(i == 0) return 0;
if(cache[i] >= 0) return cache[i];
int res = INF;
// 遍历集合，从右向左扩展，set 可以是 list
for (String t : set) {
int m = t.length();
if (i >= m && t.equals(s.substring(i - m, i))) {
res = Math.min(res, backtrack(i - m) + 1);
}
}
// for(int j = i - 1; j >= 0; j--){
// if(s.charAt(j) != '0' && set.contains(s.substring(j, i))){
// res = Math.min(res, backtrack(j) + 1);
// }
// }
return cache[i] = res;
}
}
class Solution {
public int minimumBeautifulSubstrings(String s) {
// 预处理所有 5 的幂的 二进制 表示
// List<String> list = new ArrayList<>();
Set<String> set = new HashSet();
for(int i = 0; i < 8; i++){
set.add(Integer.toBinaryString((int)Math.pow(5, i)));
}
int n = s.length(), INF = 0x3f3f3f3f;
int[] f = new int[n + 1];
Arrays.fill(f, INF);
f[0] = 0;
for(int i = 0; i <= n; i++){ // f 的下标
if (f[i] == INF) continue;
// 向右扩展
for (String t : set) {
int j = t.length() + i;
if (j <= n && t.equals(s.substring(i, j)))
f[j] = Math.min(f[j], f[i] + 1);
}
}
// for(int i = 1; i <= n; i++){ // f 的下标
// if (s.charAt(i - 1) == '0') continue; // 剪枝
// // 当前 i 向左试着找
// for(int j = i - 1; j >= 0; j--){
// if(s.charAt(j) == '1' && set.contains(s.substring(j, i)))
// f[i] = Math.min(f[i], f[j] + 1);
// }
// }
return f[n] == INF ? -1 : f[n];
}
}
2768. 黑格子的数目
块定义为网格图中 2 x 2 的一个子矩阵。对于 左上角格子为 [x, y] 的块，其中 0 <= x < m - 1 且 0 <= y < n - 1 ，包含坐标为 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。
任意一个点 (x, y)，包含它的块为 [x-1, y-1], [x-1, y], [x, y-1], [x, y]，其中坐标不能越界。
class Solution {
public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
int[][] DIRS = {{-1,-1},{-1,0},{0,-1},{0,0}};
Map<Integer, Integer> map = new HashMap<>();
for (int[] coor : coordinates) {
for (int[] dir : DIRS) {
int x = coor[0] + dir [0];
int y = coor[1] + dir [1];
if (x < 0 || y < 0 || x >= m - 1 || y >= n - 1) continue;
int index = x * n + y;
map.merge(index, 1, Integer::sum);
}
}
long[] res = new long[5];
for(int value : map.values())
res[value]++;
res[0] = 1L * (m - 1) * (n - 1) - map.size();
return res;
}
}
第 107 场双周赛
2744. 最大字符串配对数目
class Solution {
public int maximumNumberOfStringPairs(String[] words) {
int res = 0;
Set<String> vis = new HashSet();
for (String s : words) {
if (vis.contains(s)) res++;
else vis.add(new StringBuffer(s).reverse().toString());
}
return res;
}
}
2746. 字符串连接删减字母
class Solution {
int n;
int[][] arr;
int[][][] memo;
public int minimizeConcatenatedLength(String[] words) {
int res = Arrays.stream(words).mapToInt(String::length).sum();
n = words.length;
// 只需要首尾两个字符
arr = new int[n][2];
for (int i = 0; i < n; i++) {
String w = words[i];
arr[i] = new int[]{w.charAt(0) - 'a', w.charAt(w.length() - 1) - 'a'};
}
memo = new int[n][26][26];
for (int[][] a : memo) for (int[] b : a) Arrays.fill(b, 1);
return res + dfs(1, arr[0][0], arr[0][1]);
}
// 最多可以减少的字符
int dfs(int i, int b, int a) {
if (i == n) return 0;
int u = arr[i][0];
int v = arr[i][1];
if (memo[i][b][a] < 1) return memo[i][b][a];
// 接前、接后
return memo[i][b][a] = Math.min(dfs(i + 1, u, a) + (v == b ? -1 : 0), dfs(i + 1, b, v) + (u == a ? -1 : 0));
}
}
2747. 统计没有收到请求的服务器数目
class Solution {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
int nq = queries.length;
var id = new Integer[nq];
Arrays.setAll(id, i -> i);
Arrays.sort(id, (i, j) -> queries[i] - queries[j]);
int m = logs.length;
Arrays.sort(logs, (a, b) -> a[1] - b[1]); // 按照 time 排序
int[] res = new int[nq], cnt = new int[n + 1];
int outOfRange = n, left = 0, right = 0;
for (int i : id) {
// 进入窗口
for (; right < m && logs[right][1] <= queries[i]; cnt[logs[right++][0]]++)
if(cnt[logs[right][0]] == 0) outOfRange--;
// 离开窗口
for (; left < m && logs[left][1] < queries[i] - x; cnt[logs[left++][0]]--)
if (cnt[logs[left][0]] == 1) outOfRange++;
res[i] = outOfRange;
}
return res;
}
}
第 103 场双周赛
BFS / DFS, 树状数组
2658. 网格图中鱼的最大数目
// class Solution {
// int[] dirs = {1,0,-1,0,1};
// public int findMaxFish(int[][] grid) {
// int m = grid.length, n = grid[0].length;
// int res = 0;
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// if (grid[i][j] > 0)
// res = Math.max(res, bfs(grid, i, j));
// }
// }
// return res;
// }
// int bfs(int[][] grid, int i, int j) {
// int res = 0;
// Deque<int[]> q = new LinkedList();
// q.offer(new int[]{i, j});
// while (!q.isEmpty()) {
// i = q.peek()[0]; j = q.poll()[1];
// res += grid[i][j];
// grid[i][j] = 0;
// for (int k = 0; k < 4; k ++) {
// int x = i + dirs[k], y = j + dirs[k + 1];
// if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) continue;
// q.offer(new int[]{x, y});
// }
// }
// return res;
// }
// }
class Solution {
private final static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m, n;
public int findMaxFish(int[][] grid) {
m = grid.length; n = grid[0].length;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(grid, i, j));
return ans;
}
private int dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
return 0;
int sum = grid[x][y];
grid[x][y] = 0; // 标记成访问过
for (var d : DIRS) // 四方向移动
sum += dfs(grid, x + d[0], y + d[1]);
return sum;
}
}
2659. 将数组清空
方法一：树状数组
query(i, j) 表示在 [i, j] 中的被删除的元素个数。
上一个被删除的位置为 pre（初始为 1），当前需要删除的位置为 i。
假设现在共删除了 k 个数，从 pre 到 i 的移动次数 step：
s
t
e
p
=
{
i
−
p
r
e
−
q
u
e
r
y
(
p
r
e
,
i
)
p
r
e
≤
i
n
−
(
p
r
e
−
i
)
−
（
k
−
q
u
e
r
y
(
i
,
p
r
e
−
1
)
)
i
<
p
r
e
step=\begin{cases} i − pre − query(pre, i) & pre ≤ i \\ n − (pre − i) - （k - query(i, pre - 1)) & i < pre \\ \end{cases}
step={i−pre−query(pre,i)n−(pre−i)−（k−query(i,pre−1))pre≤ii<pre
class Solution {
public long countOperationsToEmptyArray(int[] nums) {
int n = nums.length;
var id = new Integer[n];
Arrays.setAll(id, i -> i);
Arrays.sort(id, (i, j) -> nums[i] - nums[j]);
long ans = n; // 先把 n 计入答案
var t = new BIT(n + 1); // 下标从 1 开始
int pre = 1; // 上一个最小值的位置，初始为 1
for (int k = 0; k < n; ++k) {
int i = id[k] + 1; // 下标从 1 开始
if (i >= pre) // 从 pre 移动到 i，跳过已经删除的数
ans += i - pre - t.query(pre, i);
else // 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数
ans += n - pre + i - k + t.query(i, pre - 1);
t.inc(i); // 删除 i
pre = i;
}
return ans;
}
}
// 树状数组模板
class BIT {
private final int[] tree;
public BIT(int n) {
tree = new int[n];
}
// 将下标 i 上的数加一
public void inc(int i) {
while (i < tree.length) {
++tree[i];
i += i & -i;
}
}
// 返回闭区间 [1, i] 的元素和
public int sum(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
// 返回闭区间 [left, right] 的元素和
public int query(int left, int right) {
return sum(right) - sum(left - 1);
}
}
方法二：
如果第 k 次要删除的元素在第 k−1 次要删除的元素的左侧，那么必须多走一整圈，移动次数为 n−k。累加，即为总的移动次数。
最后如果剩下若干递增元素，直接一股脑删除，无需任何移动次数。
class Solution {
public long countOperationsToEmptyArray(int[] nums) {
int n = nums.length;
var id = new Integer[n];
Arrays.setAll(id, i -> i);
Arrays.sort(id, (i, j) -> nums[i] - nums[j]);
long ans = n; // 先把 n 计入答案
for (int k = 1; k < n; ++k)
if (id[k] < id[k - 1]) // 必须多走一整圈
ans += n - k; // 减去前面删除的元素个数
return ans;
}
}
第 102 场双周赛
2642. 设计可以求最短路径的图类
方法一：Dijkstra
定义 start 为起点，dis[i] 表示从 start 到 i 的最短路的长度。初始时 dis[start] = 0，其余 dis[i] 为 ∞。
首先，从 start 出发，更新邻居的最短路。
下一步，寻找除去 start 的 dis 的最小值，设这个点为 x，那么 dis[x] 就已经是从 start 到 x 的最短路的长度了。
由于在寻找 dis 的最小值时，需要排除在前面的循环中找到的 x（因为已经更新 x 到其它点的最短路了，无需反复更新），可以用一个vis 数组标记这些 x。
以上，通过数学归纳法，可以证明每次找到的未被标记的 dis 的最小值就是最短路。
由于输入的图最坏是稠密图，所以采用邻接矩阵实现。
class Graph {
private static final int INF = Integer.MAX_VALUE / 2; // 防止更新最短路时加法溢出
private int[][] g;
public Graph(int n, int[][] edges) {
g = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
for (int i = 0; i < n; ++i)
Arrays.fill(g[i], INF);
for (var e : edges)
g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边）
}
public void addEdge(int[] e) {
g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证这条边之前不存在）
}
// 朴素 Dijkstra 算法
public int shortestPath(int start, int end) {
int n = g.length;
var dis = new int[n]; // 从 start 出发，到各个点的最短路，如果不存在则为无穷大
Arrays.fill(dis, INF);
dis[start] = 0;
var vis = new boolean[n];
for (;;) {
// 找到当前最短路，去更新它的邻居的最短路
// 根据数学归纳法，dis[x] 一定是最短路长度
int x = -1;
for (int i = 0; i < n; ++i)
if (!vis[i] && (x < 0 || dis[i] < dis[x]))
x = i;
if (x < 0 || dis[x] == INF) // 所有从 start 能到达的点都被更新了
return -1;
if (x == end) // 找到终点，提前退出
return dis[x];
vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
for (int y = 0; y < n; ++y)
dis[y] = Math.min(dis[y], dis[x] + g[x][y]); // 更新最短路长度
}
}
}
方法二：Floyd
Floyd 本质是动态规划。由于这个动态规划的状态定义不是很好想出来，所以我就直接描述算法了：
定义 d[k][i][j] 表示从 i 到 j 的最短路长度，并且从 i 到 j 的路径上的中间节点（不含 i 和 j）的编号至多为 k。
分类讨论：
如果 i 到 j 的路径上的节点编号没有 k，那么按照定义 d[k][i][j] = d[k-1][i][j]。
如果 i 到 j 的路径上的节点编号有 k，那么可以视作先从 i 到 k，再从 k 到 j。由于 i 到 k 和 k 到 j 的中间节点都没有 k，所以有 d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]。
取最小值，得
d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])
初始值 d[0][i][j] 为原图中 i 到 j 的边长，如果不存在则为 ∞。最终 i 到 j 的最短路长度为 d[k-1][i][j]。
代码实现时，第一个维度可以优化掉，即
d[i][j]=min(d[[i][j],d[i][k]+d[k][j])
对于 addEdge 操作，记 x=from,y=to 如果 edgeCode≥d[x][y]，则无法更新任何点对的最短路。否则枚举所有 d[i][j]，尝试看看能否更新成更小，即 i—x-y—j 是否更短：
d[i][j]=min(d[i][j],d[i][x]+edgeCode+d[y][j])文章来源：https://www.toymoban.com/news/detail-527835.html
由于当 i=x 或 j=y 时，需要用到 d[i][i] 这样的值，所以初始化的时候，d[i][i] 要置为 0。文章来源地址https://www.toymoban.com/news/detail-527835.html
class Graph {
private static final int INF = Integer.MAX_VALUE / 3; // 防止更新最短路时加法溢出
private int[][] d;
public Graph(int n, int[][] edges) {
d = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
for (int i = 0; i < n; ++i) {
Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (var e : edges)
d[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边和自环）
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
public void addEdge(int[] e) {
int x = e[0], y = e[1], w = e[2], n = d.length;
if (w >= d[x][y]) // 无需更新
return;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
d[i][j] = Math.min(d[i][j], d[i][x] + w + d[y][j]);
}
public int shortestPath(int start, int end) {
int ans = d[start][end];
return ans < INF / 3 ? ans : -1;
}
}
到了这里，关于竞赛 双周赛的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
