Biweekly Contest 149

欢迎大家加QQ群：623375442，可以方便群里面交流。春节期间刷题，也是真爱了。幸好这周也不算很难。

100552. Find Valid Pair of Adjacent Digits in String

给你一个只包含数字的字符串 s 。如果 s 中两个 相邻 的数字满足以下条件，我们称它们是 合法的 ：

• 前面的数字 不等于 第二个数字。
• 两个数字在 s 中出现的次数 恰好 分别等于这个数字本身。

请你从左到右遍历字符串 s ，并返回最先找到的 合法 相邻数字。如果这样的相邻数字不存在，请你返回一个空字符串。

测试样例：

输入：s = "2523533"

输出："23"

解释：数字 '2' 出现 2 次，数字 '3' 出现 3 次。"23" 中每个数字在 s 中出现的次数都恰好分别等于数字本身。所以输出 "23" 。

解答：暴力运算。

class Solution {
    public String findValidPair(String s) {
        int[] count = new int[10];
        for (int i = 0; i < s.length(); ++i) {
            count[s.charAt(i) - '0'] += 1;
        }
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i - 1) != s.charAt(i) && count[s.charAt(i - 1) - '0'] == s.charAt(i - 1) - '0' && count[s.charAt(i) - '0'] == s.charAt(i) - '0') {
                return s.substring(i - 1, i + 1);
            }
        }
        return "";
    }
}

100558. Reschedule Meetings for Maximum Free Time I

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

测试样例：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]

输出：2

解释：将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

解答：尽量把k个会议一起进行，这样可以空出最大的实践。

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int[] prefixCount = new int[startTime.length + 1];
        for (int i = 0; i < startTime.length; ++i) {
            prefixCount[i + 1] = prefixCount[i] + endTime[i] - startTime[i];
        }
        int best = 0;
        for (int i = 0; i + k <= startTime.length; ++i) {
            int left = i == 0 ? 0 : endTime[i - 1];
            int right = i + k < startTime.length ? startTime[i + k] : eventTime;
            // k个会议一起进行
            best = Math.max(best, right - left - prefixCount[i + k] + prefixCount[i]);
        }
        return best;
    }
}

100556. Reschedule Meetings for Maximum Free Time II

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 一个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外，且会议之间需要保持互不重叠。

注意：重新安排会议以后，会议之间的顺序可以发生改变。

测试样例：

输入：eventTime = 5, startTime = [1,3], endTime = [2,5]

输出：2

解释：将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

解答：主要难点是，会议可能会被移去别的空档。利用topThree来记录最大的三个空档（每次最多删除2个空档，这个时候性能较好）。

class Solution {
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int[] topThree = new int[3];
        int l = startTime.length - 1;
        updateTopThree(topThree, startTime[0]);
        updateTopThree(topThree, eventTime - endTime[l]);
        for (int i = 1; i <= l; ++i) {
            updateTopThree(topThree, startTime[i] - endTime[i - 1]);
        }
        int res = 0;
        int left = 0;
        for (int i = 0; i <= l; ++i) {
            int right = i == l ? eventTime : startTime[i + 1];
            res = Math.max(res, topAfterRemove(topThree, startTime[i] - left, right - endTime[i]) >= endTime[i] - startTime[i]
                    ? (right - left) : (right - left - endTime[i] + startTime[i]));
            left = endTime[i];
        }
        return res;
    }

    private void updateTopThree(int[] topThree, int val) {
        for (int i = 2; i >= 0; --i) {
            if (topThree[i] <= val) {
                for (int j = 0; j < i; ++j) {
                    topThree[j] = topThree[j + 1];
                }
                topThree[i] = val;
                break;
            }
        }
    }

    private int topAfterRemove(int[] topThree, int val1, int val2) {
        for (int i = 2; i >= 0; --i) {
            if (topThree[i] == val1) {
                val1 = -1;
            } else if (topThree[i] == val2) {
                val2 = -1;
            } else {
                return topThree[i];
            }
        }
        return -1;
    }
}

100524. Minimum Cost Good Caption

给你一个长度为 n 的字符串 caption 。如果字符串中 每一个 字符都位于连续出现 至少 3 次 的组中，那么我们称这个字符串是 好 标题。

比方说：

• "aaabbb" 和 "aaaaccc" 都是 好 标题。
• "aabbb" 和 "ccccd" 都 不是 好标题。

你可以对字符串执行以下操作 任意 次：

选择一个下标 i（其中 0 <= i < n ）然后将该下标处的字符变为：

• 该字符在字母表中 前 一个字母（前提是 caption[i] != 'a' ）
• 该字符在字母表中 后 一个字母（caption[i] != 'z' ）

你的任务是用 最少 操作次数将 caption 变为 好 标题。如果存在 多种 好标题，请返回它们中 字典序最小 的一个。如果 无法 得到好标题，请你返回一个空字符串 "" 。

在字符串 a 和 b 中，如果两个字符串第一个不同的字符处，字符串 a 的字母比 b 的字母在字母表里出现的顺序更早，那么我们称字符串 a 的 字典序 比 b 小 。如果两个字符串前 min(a.length, b.length) 个字符都相同，那么较短的一个字符串字典序比另一个字符串小。

测试样例：

输入：caption = "cdcd"

输出："cccc"

解释：无法用少于 2 个操作将字符串变为好标题。2 次操作得到好标题的方案包括：

• "dddd" ：将 caption[0] 和 caption[2] 变为它们后一个字符 'd' 。
• "cccc" ：将 caption[1] 和 caption[3] 变为它们前一个字符 'c' 。

由于 "cccc" 字典序比 "dddd" 小，所以返回 "cccc" 。

解答：典型的动态规划。规划计算当前字段开始，连续1，2，3这三种情况下，最小的支出。

class Solution {
    private static final int MAX = Integer.MAX_VALUE / 2;

    public String minCostGoodCaption(String caption) {
        if (caption.length() <= 2) return "";
        int[][][] dp = new int[caption.length()][26][3];
        int min = MAX;
        for (int i = caption.length() - 1; i  >= 0; --i) {
            initialArr(dp[i]);
            if (i == caption.length() - 1) {
                for (int j = 0; j < 26; ++j) {
                    dp[i][j][0] = Math.abs(caption.charAt(i) - 'a' - j);
                }
            } else {
                int nextMin = MAX;
                for (int j = 0; j < 26; ++j) {
                    // 连续1，2，3这三种情况下，最小的支出。
                    int diff = Math.abs(caption.charAt(i) - 'a' - j);
                    dp[i][j][0] = Math.min(min + diff, MAX);
                    dp[i][j][1] = Math.min(Math.min(dp[i + 1][j][0], Math.min(dp[i + 1][j][1], dp[i + 1][j][2])) + diff, MAX);
                    dp[i][j][2] = Math.min(Math.min(dp[i + 1][j][1], dp[i + 1][j][2]) + diff, MAX);

                    nextMin = Math.min(nextMin, dp[i][j][2]);
                }
                min = nextMin;
            }
        }
        StringBuilder sb = new StringBuilder();
        int lastCons = 0, lastPos = -1;
        for (int i = 0; i < caption.length(); ++i) {
            // 逆反寻找的时候比较特殊，如果连续字符串没到达3，那么直接重复之前位置。
            if (lastCons <= 2) {
                if (lastPos == -1) {
                    lastPos = findBest(dp[i]);
                }
                ++lastCons;
                sb.append((char) (lastPos + 'a'));
            } else {
                int tmp = findBest(dp[i]);
                int curMin = Math.min(dp[i][lastPos][0], Math.min(dp[i][lastPos][1], dp[i][lastPos][2]));
                // 如果连续重复到达3个，为了最小字典序列，查看是否有更好的单词。
                if (dp[i][tmp][2] < curMin || (dp[i][tmp][2] == curMin && tmp < lastPos)) {
                    lastPos = tmp;
                    lastCons = 1;
                }
                sb.append((char) (lastPos + 'a'));
            }
        }
        return sb.toString();
    }

    private int findBest(int[][] dp) {
        int res = 0;
        for (int j = 0; j < 26; ++j) {
            if (dp[j][2] < dp[res][2]) {
                res = j;
            }
        }
        return res;
    }

    private void initialArr(int[][] row) {
        for (int i = 0; i < row.length; ++i) {
            Arrays.fill(row[i], Integer.MAX_VALUE >> 1);
        }
    }
}

补充一个Rust版本

impl Solution {
    pub fn min_cost_good_caption(caption: String) -> String {
        if caption.len() <= 2 {
            return String::new();
        }
        let caption_arr = caption.as_bytes();
        let mut dp = vec![[[std::i32::MAX / 2;3];26] ; caption.len()];
        let mut min: i32 = std::i32::MAX / 2;
        for i in (0..caption.len()).rev() {
            let offset = (caption_arr[i] - 97) as i32;
            let mut cur_min = std::i32::MAX / 2;
            if i == caption_arr.len() - 1 {
                for j in 0..26 {
                    dp[i][j][0] = (j as i32 - offset).abs();
                }
            } else {
                for j in 0..26 {
                    let diff = (j - offset).abs();
                    let j_u = j as usize;
                    dp[i][j_u][0] = dp[i][j_u][0].min(min + diff);
                    dp[i][j_u][1] = dp[i][j_u][1].min(dp[i + 1][j_u][0] + diff).min(dp[i + 1][j_u][1] + diff).min(dp[i + 1][j_u][2] + diff);
                    dp[i][j_u][2] = dp[i][j_u][2].min(dp[i + 1][j_u][1] + diff).min(dp[i + 1][j_u][2] + diff);
                    cur_min = cur_min.min(dp[i][j_u][2]);
                }
            }
            min = cur_min;
        }
        let mut res: String = String::new();
        let mut last_char = 100;
        let mut last_len = 0;
        for i in 0..caption_arr.len() {
            if last_len <= 2 {
                if last_char == 100 {
                    last_char = Self::find_min_offset(&dp[i]);
                }
                res.push(std::char::from_u32(last_char as u32 + 97).unwrap());
            } else {
                let tmp = Self::find_min_offset(&dp[i]);
                let last_cur_min = dp[i][last_char][0].min(dp[i][last_char][1]).min(dp[i][last_char][2]);
                if dp[i][tmp][2] < last_cur_min || (dp[i][tmp][2] == last_cur_min && tmp < last_char) {
                    last_char = tmp;
                    last_len = 0;
                }
                res.push(std::char::from_u32(last_char as u32 + 97).unwrap());
            }
            last_len += 1;
        }
        res
    }

    fn find_min_offset(dp: &[[i32;3];26]) -> usize {
        let mut res: usize = 0;
        for i in 0..26 {
            if dp[i][2] < dp[res][2] {
                res = i;
            }
        }
        res
    }
}