第 108 場(chǎng)雙周賽
2765. 最長(zhǎng)交替子序列
分段
class Solution {
public int alternatingSubarray(int[] nums) {
int res = -1, n = nums.length;
for (int i = 1; i < n; i++) {
// 找每一段第一個(gè)
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<>();
// 預(yù)處理所有 5 的冪的 二進(jìn)制 表示
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:] 的最少數(shù)目
public int backtrack(int i){
if(i == 0) return 0;
if(cache[i] >= 0) return cache[i];
int res = INF;
// 遍歷集合，從右向左擴(kuò)展，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) {
// 預(yù)處理所有 5 的冪的 二進(jìn)制 表示
// 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 的下標(biāo)
if (f[i] == INF) continue;
// 向右擴(kuò)展
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 的下標(biāo)
// if (s.charAt(i - 1) == '0') continue; // 剪枝
// // 當(dāng)前 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. 黑格子的數(shù)目
塊定義為網(wǎng)格圖中 2 x 2 的一個(gè)子矩陣。對(duì)于 左上角格子為 [x, y] 的塊，其中 0 <= x < m - 1 且 0 <= y < n - 1 ，包含坐標(biāo)為 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。
任意一個(gè)點(diǎn) (x, y)，包含它的塊為 [x-1, y-1], [x-1, y], [x, y-1], [x, y]，其中坐標(biāo)不能越界。
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 場(chǎng)雙周賽
2744. 最大字符串配對(duì)數(shù)目
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;
// 只需要首尾兩個(gè)字符
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. 統(tǒng)計(jì)沒(méi)有收到請(qǐng)求的服務(wù)器數(shù)目
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) {
// 進(jìn)入窗口
for (; right < m && logs[right][1] <= queries[i]; cnt[logs[right++][0]]++)
if(cnt[logs[right][0]] == 0) outOfRange--;
// 離開(kāi)窗口
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 場(chǎng)雙周賽
BFS / DFS, 樹(shù)狀數(shù)組
2658. 網(wǎng)格圖中魚(yú)的最大數(shù)目
// 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; // 標(biāo)記成訪問(wèn)過(guò)
for (var d : DIRS) // 四方向移動(dòng)
sum += dfs(grid, x + d[0], y + d[1]);
return sum;
}
}
2659. 將數(shù)組清空
方法一：樹(shù)狀數(shù)組
query(i, j) 表示在 [i, j] 中的被刪除的元素個(gè)數(shù)。
上一個(gè)被刪除的位置為 pre（初始為 1），當(dāng)前需要?jiǎng)h除的位置為 i。
假設(shè)現(xiàn)在共刪除了 k 個(gè)數(shù)，從 pre 到 i 的移動(dòng)次數(shù) 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 計(jì)入答案
var t = new BIT(n + 1); // 下標(biāo)從 1 開(kāi)始
int pre = 1; // 上一個(gè)最小值的位置，初始為 1
for (int k = 0; k < n; ++k) {
int i = id[k] + 1; // 下標(biāo)從 1 開(kāi)始
if (i >= pre) // 從 pre 移動(dòng)到 i，跳過(guò)已經(jīng)刪除的數(shù)
ans += i - pre - t.query(pre, i);
else // 從 pre 移動(dòng)到 n，再?gòu)?1 移動(dòng)到 i，跳過(guò)已經(jīng)刪除的數(shù)
ans += n - pre + i - k + t.query(i, pre - 1);
t.inc(i); // 刪除 i
pre = i;
}
return ans;
}
}
// 樹(shù)狀數(shù)組模板
class BIT {
private final int[] tree;
public BIT(int n) {
tree = new int[n];
}
// 將下標(biāo) i 上的數(shù)加一
public void inc(int i) {
while (i < tree.length) {
++tree[i];
i += i & -i;
}
}
// 返回閉區(qū)間 [1, i] 的元素和
public int sum(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
// 返回閉區(qū)間 [left, right] 的元素和
public int query(int left, int right) {
return sum(right) - sum(left - 1);
}
}
方法二：
如果第 k 次要?jiǎng)h除的元素在第 k?1 次要?jiǎng)h除的元素的左側(cè)，那么必須多走一整圈，移動(dòng)次數(shù)為 n?k。累加，即為總的移動(dòng)次數(shù)。
最后如果剩下若干遞增元素，直接一股腦刪除，無(wú)需任何移動(dòng)次數(shù)。
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 計(jì)入答案
for (int k = 1; k < n; ++k)
if (id[k] < id[k - 1]) // 必須多走一整圈
ans += n - k; // 減去前面刪除的元素個(gè)數(shù)
return ans;
}
}
第 102 場(chǎng)雙周賽
2642. 設(shè)計(jì)可以求最短路徑的圖類
方法一：Dijkstra
定義 start 為起點(diǎn)，dis[i] 表示從 start 到 i 的最短路的長(zhǎng)度。初始時(shí) dis[start] = 0，其余 dis[i] 為 ∞。
首先，從 start 出發(fā)，更新鄰居的最短路。
下一步，尋找除去 start 的 dis 的最小值，設(shè)這個(gè)點(diǎn)為 x，那么 dis[x] 就已經(jīng)是從 start 到 x 的最短路的長(zhǎng)度了。
由于在尋找 dis 的最小值時(shí)，需要排除在前面的循環(huán)中找到的 x（因?yàn)橐呀?jīng)更新 x 到其它點(diǎn)的最短路了，無(wú)需反復(fù)更新），可以用一個(gè)vis 數(shù)組標(biāo)記這些 x。
以上，通過(guò)數(shù)學(xué)歸納法，可以證明每次找到的未被標(biāo)記的 dis 的最小值就是最短路。
由于輸入的圖最壞是稠密圖，所以采用鄰接矩陣實(shí)現(xiàn)。
class Graph {
private static final int INF = Integer.MAX_VALUE / 2; // 防止更新最短路時(shí)加法溢出
private int[][] g;
public Graph(int n, int[][] edges) {
g = new int[n][n]; // 鄰接矩陣（初始化為無(wú)窮大，表示 i 到 j 沒(méi)有邊）
for (int i = 0; i < n; ++i)
Arrays.fill(g[i], INF);
for (var e : edges)
g[e[0]][e[1]] = e[2]; // 添加一條邊（輸入保證沒(méi)有重邊）
}
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 出發(fā)，到各個(gè)點(diǎn)的最短路，如果不存在則為無(wú)窮大
Arrays.fill(dis, INF);
dis[start] = 0;
var vis = new boolean[n];
for (;;) {
// 找到當(dāng)前最短路，去更新它的鄰居的最短路
// 根據(jù)數(shù)學(xué)歸納法，dis[x] 一定是最短路長(zhǎng)度
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 能到達(dá)的點(diǎn)都被更新了
return -1;
if (x == end) // 找到終點(diǎn)，提前退出
return dis[x];
vis[x] = true; // 標(biāo)記，在后續(xù)的循環(huán)中無(wú)需反復(fù)更新 x 到其余點(diǎn)的最短路長(zhǎng)度
for (int y = 0; y < n; ++y)
dis[y] = Math.min(dis[y], dis[x] + g[x][y]); // 更新最短路長(zhǎng)度
}
}
}
方法二：Floyd
Floyd 本質(zhì)是動(dòng)態(tài)規(guī)劃。由于這個(gè)動(dòng)態(tài)規(guī)劃的狀態(tài)定義不是很好想出來(lái)，所以我就直接描述算法了：
定義 d[k][i][j] 表示從 i 到 j 的最短路長(zhǎng)度，并且從 i 到 j 的路徑上的中間節(jié)點(diǎn)（不含 i 和 j）的編號(hào)至多為 k。
分類討論：
如果 i 到 j 的路徑上的節(jié)點(diǎn)編號(hào)沒(méi)有 k，那么按照定義 d[k][i][j] = d[k-1][i][j]。
如果 i 到 j 的路徑上的節(jié)點(diǎn)編號(hào)有 k，那么可以視作先從 i 到 k，再?gòu)?k 到 j。由于 i 到 k 和 k 到 j 的中間節(jié)點(diǎn)都沒(méi)有 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 的邊長(zhǎng)，如果不存在則為 ∞。最終 i 到 j 的最短路長(zhǎng)度為 d[k-1][i][j]。
代碼實(shí)現(xiàn)時(shí)，第一個(gè)維度可以優(yōu)化掉，即
d[i][j]=min(d[[i][j],d[i][k]+d[k][j])
對(duì)于 addEdge 操作，記 x=from,y=to 如果 edgeCode≥d[x][y]，則無(wú)法更新任何點(diǎn)對(duì)的最短路。否則枚舉所有 d[i][j]，嘗試看看能否更新成更小，即 i—x-y—j 是否更短：
d[i][j]=min(d[i][j],d[i][x]+edgeCode+d[y][j])文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-527835.html
由于當(dāng) i=x 或 j=y 時(shí)，需要用到 d[i][i] 這樣的值，所以初始化的時(shí)候，d[i][i] 要置為 0。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-527835.html
class Graph {
private static final int INF = Integer.MAX_VALUE / 3; // 防止更新最短路時(shí)加法溢出
private int[][] d;
public Graph(int n, int[][] edges) {
d = new int[n][n]; // 鄰接矩陣（初始化為無(wú)窮大，表示 i 到 j 沒(méi)有邊）
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]; // 添加一條邊（輸入保證沒(méi)有重邊和自環(huán)）
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]) // 無(wú)需更新
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;
}
}
到了這里，關(guān)于競(jìng)賽 雙周賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
