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);
    }
}