Leetcode - 149双周赛

一、3438. 找到字符串中合法的相邻数字

题目链接

本题有两个条件：

• 相邻数字互不相同
• 两个数字的的出现次数等于数字本身

先预处理字符串 $s$ 中每个字符的出现次数，再从左往右两两枚举，返回第一个满足上述条件的相邻数字，没有返回空字符串。

代码如下：

class Solution {public String findValidPair(String s) {int[] cnt = new int[10];for(char c : s.toCharArray()){cnt[c-'0']++;}for(int i=1; i<s.length(); i++){int x = s.charAt(i) - '0';int y = s.charAt(i-1) - '0';if(x == y) continue;if(cnt[x] == x && cnt[y] == y)return s.substring(i-1, i+1);}return "";}
}

二、3439. 重新安排会议得到最多空余时间 I

题目链接

题目求至多平移 $k$ 个会议后，可以获得的最大空余时间，与会议本身的时间无关，可以预处理出会议之间的空余时间（注：不要忘记第一个会议开始前和最后一个会议结束后的空余时间），贪心的想，平移的会议越多，可以获得的空余时间越大，此时题目变成了平移 $k$ 个会议后，可以获得的最大空余时间，讨论 $k$ 的大小：

• $k=1$，对于 $1$ 个会议来说，无论它往前移还是往后移，它会使得连续的 $2$ 段空余时间合并.
• $k=2$，对于 $2$ 个会议来说，无论它们往前移还是往后移，它会使得连续的 $3$ 段空余时间合并.
• …
• 对于 $k$ 个会议来说，无论它们往前移还是往后移，它会使得连续的 $k+1$ 段空余时间合并.

也就是说它其实是一个滑动窗口题，就是维护连续 $k+1$ 段空余时间的最大值。

代码如下：

class Solution {public int maxFreeTime(int event, int k, int[] start, int[] end) {int n = start.length;int[] t = new int[n+1];t[0] = start[0];t[n] = event - end[n-1];for(int i=1; i<n; i++){t[i] = start[i] - end[i-1];}int ans = 0, res = 0;for(int l=0,r=0; r<n+1; r++){res += t[r];if(r-l+1 > k + 1){res -= t[l];l++;}ans = Math.max(ans, res);}return ans;}
}

三、3440. 重新安排会议得到最多空余时间 II

题目链接

本题与 T2 的区别在于只能移动 1 个会议，且会议之间的顺序可以发生改变，这将会导致一个新的情况，如果会议 $i$ 可以移动到会议 $i-1$ 前面的空余时间或者会议 $i+1$ 后面的空余时间中（即会议 $i$ 的大小 <= 空余时间），那么当前的空余时间 = 会议 $i$ 与 会议 $i-1$ 的空余时间 + 会议 $i$ 与 会议 $i+1$ 的空余时间 + 会议 $i$ 本身的时间。否则与 T2 情况相同，当前的空余时间 = 会议 $i$ 与 会议 $i-1$ 的空余时间 + 会议 $i$ 与 会议 $i+1$ 的空余时间

接下来就是如何判断会议 $i$ 可以移动到后面或前面，这里可以使用前后缀分解的做法来预处理 $[0,i-1]$ 的最大空余时间，和 $[i+1，n-1]$ 的最大空余时间。

代码如下：

class Solution {public int maxFreeTime(int event, int[] start, int[] end) {int n = start.length;int[] t = new int[n+1];t[0] = start[0];t[n] = event - end[n-1];int ans = Math.max(t[0], t[n]);int[] pre = new int[n+1];//前缀最大值pre[0] = t[0];for(int i=1; i<n; i++){t[i] = start[i] - end[i-1];pre[i] = Math.max(pre[i-1], t[i]);}int[] suf = new int[n+1];//后缀最大值suf[n] = t[n];for(int i=n-1; i>=0; i--){suf[i] = Math.max(suf[i+1], t[i]);}int res = 0;for(int l=0,r=1; r<n+1; l++,r++){int len = end[l] - start[l];//判断当前 会议l 能否移动到前面/后面if(l>0 && pre[l-1] >= len || l+2<n+1 && suf[l+2] >= len)ans = Math.max(ans, t[r] + t[l] + len);else ans = Math.max(ans, t[l] + t[r]);}return ans;}
}

四、3441. 变成好标题的最少代价

题目链接

对于本题来说，它返回的好标题需要满足两个条件，操作次数最少且字典序最小，可以先使用 $dfs$ 计算出得到好标题的最小操作次数，定义 $dfs(i,j):$ 第 $i$ 个位置变成 $j$ 时，$[i+1,n-1]$ 变成好标题的最小操作次数，然后转成 $dp$，此时可以使用数组记录每个状态的转移来源，最后逆推得到操作次数最小的最小的字典序。

代码如下：

class Solution {public String minCostGoodCaption(String caption) {int n = caption.length();if(n < 3) return "";int res = Integer.MAX_VALUE;char[] s = caption.toCharArray();int[][] f = new int[n+1][26];int[][] nxt = new int[n+1][26];int[] minJ = new int[n+1];for(int i=n-1; i>=0; i--){int mn = Integer.MAX_VALUE;for(int j=0; j<26; j++){int res1 = f[i+1][j] + Math.abs(s[i] - 'a' - j);int res2 = i <= n - 6 ? f[i+3][minJ[i+3]] + Math.abs(s[i] - 'a' - j) + Math.abs(s[i+1] - 'a' - j) + Math.abs(s[i+2] - 'a' - j) : Integer.MAX_VALUE;if(res1 > res2 || res1 == res2 && minJ[i+3] < j){res1 = res2;nxt[i][j] = minJ[i+3];}else{nxt[i][j] = j;}f[i][j] = res1;if(res1 < mn){mn = res1;minJ[i] = j;}}}char[] ans = new char[n];int i = 0, j = minJ[0];while(i < n){ans[i] = (char)(j + 'a');int k = nxt[i][j];if(k == j){i++;}else{ans[i+2] = ans[i+1] = ans[i];i += 3;j = k;}}return new String(ans);}
}