LeetCode Contest 434

欢迎大家加QQ群：623375442，可以方便群里面交流。居然第三题不会做，泪目了。

100526. Count Partitions with Even Sum Difference

给你一个长度为 n 的整数数组 nums 。

分区 是指将数组按照下标 i （0 <= i < n - 1）划分成两个 非空 子数组，其中：

• 左子数组包含区间 [0, i] 内的所有下标。
• 右子数组包含区间 [i + 1, n - 1] 内的所有下标。

对左子数组和右子数组先求元素 和 再做 差 ，统计并返回差值为 偶数 的 分区 方案数。

测试样例：

输入：nums = [10,10,3,7,6]

输出：4

解释：共有 4 个满足题意的分区方案：

• [10]、[10, 3, 7, 6] 元素和的差值为 10 - 26 = -16 ，是偶数。
• [10, 10]、[3, 7, 6] 元素和的差值为 20 - 16 = 4，是偶数。
• [10, 10, 3]、[7, 6] 元素和的差值为 23 - 13 = 10，是偶数。
• [10, 10, 3, 7]、[6] 元素和的差值为 30 - 6 = 24，是偶数。

解答：按照题意，暴力计算。

class Solution {
    public int countPartitions(int[] nums) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        int left = 0, res = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            left += nums[i];
            int right = sum - left;
            if (Math.abs(left - right) % 2 == 0) ++res;
        }
        return res;
    }
}

100539. Count Mentions Per User

给你一个整数 numberOfUsers 表示用户总数，另有一个大小为 n x 3 的数组 events 。

每个 events[i] 都属于下述两种类型之一：

• 消息事件（Message Event）：["MESSAGE", "timestampi", "mentions_stringi"]
  • 事件表示在 timestampi 时，一组用户被消息提及。
  • mentions_stringi 字符串包含下述标识符之一：
    • id：其中 是一个区间 [0,numberOfUsers - 1] 内的整数。可以用单个空格分隔 多个 id ，并且 id 可能重复。此外，这种形式可以提及离线用户。
    • ALL：提及 所有 用户。
    • HERE：提及所有 在线 用户。
• 离线事件（Offline Event）：["OFFLINE", "timestampi", "idi"]
  • 事件表示用户 idi 在 timestampi 时变为离线状态 60 个单位时间。用户会在 timestampi + 60 时自动再次上线。

返回数组 mentions ，其中 mentions[i] 表示 id 为 i 的用户在所有 MESSAGE 事件中被提及的次数。

最初所有用户都处于在线状态，并且如果某个用户离线并在此上线，其对应的状态变更将会在所有相同时间发生的消息事件之前进行处理和同步。

注意 在单条消息中，同一个用户可能会被提及多次。每次提及都需要被 分别 统计。

测试样例：

输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]

输出：[2,2]

解释：最初，所有用户都在线。时间戳 10 ，id1 和 id0 被提及，mentions = [1,1]。时间戳 11 ，id0 离线 。时间戳 71 ，id0 再次 上线 并且 "HERE" 被提及，mentions = [2,2]

解答：先对event排序一下（注意offline的排在message前面），然后按照题意计算消息传播。

class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        events.sort(new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                int t1 = Integer.parseInt(o1.get(1)), t2 = Integer.parseInt(o2.get(1));
                if (t1 != t2) {
                    return Integer.compare(t1, t2);
                }
                t1 = o1.get(0).equals("MESSAGE") ? 1 : 0;
                t2 = o2.get(0).equals("MESSAGE") ? 1 : 0;
                return Integer.compare(t1, t2);
            }
        });
        PriorityQueue<int[]> offline = new PriorityQueue<>((a, b) -> (Integer.compare(a[1], b[1])));
        int[] res = new int[numberOfUsers];
        boolean[] isOffline = new boolean[numberOfUsers];
        for (List<String> event : events) {
            int curTime = Integer.parseInt(event.get(1));
            while (!offline.isEmpty() && offline.peek()[1] <= curTime) {
                isOffline[offline.poll()[0]] = false;
            }
            if (event.get(0).equals("OFFLINE")) {
                int tmp = Integer.parseInt(event.get(2));
                isOffline[tmp] = true;
                offline.add(new int[]{tmp, curTime + 60});
            } else {
                if (event.get(2).equals("ALL")) {
                    for (int i = 0; i < numberOfUsers; ++i) {
                        res[i] += 1;
                    }
                } else if (event.get(2).equals("HERE")) {
                    for (int i = 0; i < numberOfUsers; ++i) {
                        if (!isOffline[i]) res[i] += 1;
                    }
                } else {
                    String[] split = event.get(2).split(" ");
                    for (String t : split) {
                        res[Integer.parseInt(t.substring(2))] += 1;
                    }
                }
            }
        }
        return res;
    }
}

100564. Maximum Frequency After Subarray Operation

给你一个长度为 n 的数组 nums ，同时给你一个整数 k 。

你可以对 nums 执行以下操作 一次 ：

• 选择一个子数组 nums[i..j] ，其中 0 <= i <= j <= n - 1 。
• 选择一个整数 x 并将 nums[i..j] 中 所有 元素都增加 x 。

请你返回执行以上操作以后数组中 k 出现的 最大 频率。

子数组 是一个数组中一段连续 非空 的元素序列。

测试样例：

输入：nums = [1,2,3,4,5,6], k = 1

输出：2

解释：将 nums[2..5] 增加 -5 后，1 在数组 [1, 2, -2, -1, 0, 1] 中的频率为最大值 2 。

解答：竞赛的时候没想到怎么做。原来用前缀和+最长子序列就行了。。。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        int m = 51;
        int[][] pre = new int[n + 1][m];
        int[] min = new int[m];
        int max = 0;
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Arrays.copyOf(pre[i], m);
            if (nums[i] == k) {
                for (int j = 1; j < m; j++) {
                    if (j != k) pre[i + 1][j]--;
                }
                pre[i + 1][k]++;
            } else {
                pre[i + 1][nums[i]]++;
            }
            for (int j = 1; j < m; j++) {
                if (j == k) continue;
                max = Math.max(pre[i + 1][j] - min[j], max);
                min[j] = Math.min(min[j], pre[i + 1][j]);
            }
        }
        max = Math.max(max, 0) + pre[n][k];
        return max;
    }
}

100533. Frequencies of Shortest Supersequences

给你一个字符串数组 words 。请你找到 words 所有 最短公共超序列 ，且确保它们互相之间无法通过排列得到。

最短公共超序列 指的是一个字符串，words 中所有字符串都是它的子序列，且它的长度 最短 。

请你返回一个二维整数数组 freqs ，表示所有的最短公共超序列，其中 freqs[i] 是一个长度为 26 的数组，它依次表示一个最短公共超序列的所有小写英文字母的出现频率。你可以以任意顺序返回这个频率数组。

排列 指的是一个字符串中所有字母重新安排顺序以后得到的字符串。

一个 子序列 是从一个字符串中删除一些（也可以不删除）字符后，剩余字符不改变顺序连接得到的 非空 字符串。

测试样例：

输入：words = ["ab","ba"]

输出：[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

解释：两个最短公共超序列分别是 "aba" 和 "bab" 。输出分别是两者的字母出现频率。

解答：需要注意到，words[i].length == 2。如果一个字符我们决定让它在公共超序列中出现2次。假如字符是a，那么a...a这种形式必然能保证所有与a相关的组合都出现。又因为words 中所有字符串都包含不超过 16 个互不相同的小写英文字母。我们只要枚举所有出现1次字符的可能性，就能计算结果了。

class Solution {
    public List<List<Integer>> supersequences(String[] words) {
        boolean[][] pairAppear = new boolean[26][26];
        boolean[] charAppear = new boolean[26];
        for (String w : words) {
            pairAppear[w.charAt(0) - 'a'][w.charAt(1) - 'a'] = true;
            charAppear[w.charAt(0) - 'a'] = true;
            charAppear[w.charAt(1) - 'a'] = true;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 26; ++i) {
            if (charAppear[i]) {
                list.add(i);
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        int maxSearch = 1 << list.size(), maxLen = 2 * list.size();
        // 枚举只出现一次的字符
        for (int i = 0; i < maxSearch; ++i) {
            List<Integer> single = new ArrayList<>();
            for (int j = 0; j < list.size(); ++j) {
                int tmp = (i >> j) & 1;
                if (tmp == 0) {
                    single.add(list.get(j));
                }
            }
            if (maxLen < 2 * list.size() - single.size()) {
                continue;
            }
            // 关键是是否出现环。比如bc,cd,db这种环出现，则当前单一字符无法成立。
            if (!isCycle(pairAppear, single)) {
                if (maxLen >= 2 * list.size() - single.size()) {
                    if (maxLen > 2 * list.size() - single.size()) {
                        res = new ArrayList<>();
                    }
                    maxLen = 2 * list.size() - single.size();
                    List<Integer> add = new ArrayList<>();
                    for (int j = 0; j < 26; ++j) {
                        if (charAppear[j]) add.add(2);
                        else add.add(0);
                    }
                    for (int j : single) {
                        add.set(j, 1);
                    }
                    res.add(add);
                }
            }
        }
        return res;
    }

    private boolean isCycle(boolean[][] pairAppear, List<Integer> single) {
        boolean[] cycleVisited = new boolean[26];
        boolean[] appeared = new boolean[26];
        for (int n : single) {
            appeared[n] = true;
        }
        for (int n : single) {
            if (!cycleVisited[n]) {
                boolean[] currentCycle = new boolean[26];
                boolean bfsResult = dfs(n, currentCycle, appeared, pairAppear, cycleVisited);
                if (bfsResult) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int cur, boolean[] isVisited, boolean[] appeared, boolean[][] pairAppear, boolean[] cycleVisited) {
        if (isVisited[cur]) return true;
        cycleVisited[cur] = true;
        isVisited[cur] = true;
        for (int i = 0; i < 26; ++i) {
            if (pairAppear[cur][i] && appeared[i] && dfs(i, isVisited, appeared, pairAppear, cycleVisited)) {
                return true;
            }
        }
        isVisited[cur] = false;
        return false;
    }
}

最近还在学习Rust中补一个Rust的写法。

impl Solution {
    pub fn supersequences(words: Vec<String>) -> Vec<Vec<i32>> {
        let mut pair_appear = vec![vec![false;26];26];
        let mut char_appear = vec![false;26];
        let mut list: Vec<i32> = Vec::new();
        for word in &words {
            let first_letter_offset = word.chars().nth(0).unwrap() as i32 - 'a' as i32;
            let second_letter_offset = word.chars().nth(1).unwrap() as i32 - 'a' as i32;
            pair_appear[first_letter_offset as usize][second_letter_offset as usize] = true;
            if !char_appear[first_letter_offset as usize] {
                list.push(first_letter_offset);
                char_appear[first_letter_offset as usize] = true;
            }
            if !char_appear[second_letter_offset as usize] {
                list.push(second_letter_offset);
                char_appear[second_letter_offset as usize] = true;
            }
        }
        let max_possibility = 1 << list.len();
        let mut max_len = 2 * list.len();
        let mut res: Vec<Vec<i32>> = Vec::new();
        for key in 0..max_possibility {
            let mut single: Vec<i32> = Vec::new();
            for i in 0..list.len() {
                let tmp = (key >> i) & 1;
                if tmp == 0 {
                    single.push(*list.get(i).unwrap());
                }
            }
            if Solution::no_cycle(&single, &pair_appear) {
                let total = 2 * list.len() - single.len();
                if total < max_len {
                    max_len = total;
                    res = Vec::new();
                }
                if total == max_len {
                    let mut add_list = vec![0;26];
                    for i in 0..26 {
                        if char_appear[i as usize] {
                            add_list[i as usize] = 2;
                        }
                    }
                    for i in &single {
                        add_list[*i as usize] = 1;
                    }
                    res.push(add_list);
                }
            }
        }
        res
    }

    fn no_cycle(single: &Vec<i32>, pair_appear: &Vec<Vec<bool>>) -> bool {
        let mut current_appear = vec![false;26];
        for i in single {
            current_appear[*i as usize] = true;
        }

        let mut is_visited = vec![false;26];
        for i in single {
            if !is_visited[*i as usize] {
                let mut current_round = vec![false;26];
                if !Solution::dfs(*i as usize, &current_appear, &mut is_visited, &mut current_round, &pair_appear) {
                    return false;
                }
            }
        }
        true
    }

    fn dfs(id: usize, char_appear: &Vec<bool>, is_visited: &mut Vec<bool>, current_round: &mut Vec<bool>, pair_appear: &Vec<Vec<bool>>) -> bool {
        if current_round[id] {
            return false;
        }
        is_visited[id] = true;
        current_round[id] = true;
        for next in 0..26 {
            if pair_appear[id][next as usize] && char_appear[next as usize] && !Solution::dfs(next as usize, char_appear, is_visited, current_round, pair_appear) {
                return false;
            }
        }
        current_round[id] = false;
        true
    }
}