Leetcode - 周赛434

一、3432. 统计元素和差值为偶数的分区方案

题目链接

本题可以直接模拟，这里再介绍一个数学做法，假设 $nums[:i]$ 的和为 $L$，$nums[:]$ 的和为 $S$，那么 $nums[i+1:]$ 的和为 $S-L$，题目要求满足 $abs(L-(S-L))$ 为偶数，化简一下得到 $2\ast L-S$，可以发现差值是否为偶数和怎么划分无关，只和 $S$ 有关，而 $S$ 是固定的（数组的和），所以只要 $S$ 为偶数，那么方案数为 $len(nums)-1$，否则方案数为 $0$。

代码如下：

class Solution {public int countPartitions(int[] nums) {int s = 0;for(int x : nums){s += x;}return s%2 == 0 ? nums.length-1 : 0;}
}
//模拟做法
class Solution {public int countPartitions(int[] nums) {int n = nums.length;int s = 0;for(int x : nums){s += x;}int ans = 0;int p = 0;for(int i=0; i<n-1; i++){int x = nums[i];p += x;if((s-p-p)%2 == 0)ans++;}return ans;}
}

二、3433. 统计用户被提及情况

题目链接

本题就是一道模拟题，唯一要注意的就是在排序的时候，如果离线事件和消息时间同时发生，优先处理离线事件。

代码如下：

class Solution {public int[] countMentions(int n, List<List<String>> events) {int[] ans = new int[n];Collections.sort(events, (x, y)->{int t = Integer.parseInt(x.get(1))-Integer.parseInt(y.get(1));return t==0?y.get(0).compareTo(x.get(0)):t;    });//使用time数组记录每个用户下一次上线的时间int[] time = new int[n];for(List<String> x : events){String s = x.get(0);int t = Integer.parseInt(x.get(1));String y = x.get(2);if(s.equals("MESSAGE")){if(y.equals("ALL")){for(int i=0; i<n; i++){ans[i]++;}}else if(y.equals("HERE")){for(int i=0; i<n; i++){if(time[i] <= t){ans[i]++;}}}else{for(String c : y.split(" ")){int j = Integer.parseInt(c.substring(2));ans[j]++;}}}else{for(String c : y.split(" ")){int j = Integer.parseInt(c);time[j] = t + 60;}}}return ans;}
}

三、3434. 子数组操作后的最大频率

题目链接

本题可以将 $nums$ 数组分成三个部分：被修改的子数组的左边，被修改的子数组，被修改的子数组的右边，考虑将 $nums$ 中等于 $target$ 的元素变成 $k$，我们可以定义以下三种状态：

• $f[i+1][0]$：表示被修改的子数组的左边，即统计 $nums[:i]$ 中等于 $k$ 的元素个数。
• $f[i+1][1]$：表示被修改的子数组 + 左边，即被修改的子数组以 $i$ 结尾时 $k$ 出现的最大频率。
• $f[i+1][2]$：表示被修改的子数组 + 左边 + 右边，即被修改的子数组以 $<i$ 的下标结尾时 $k$ 出现的最大频率。
• 注：这三种状态都表示 $nums[:i]$ 中 $k$ 出现的最大频率，只不过表示的范围不同！！！
• 显然，假设被修改子数组的范围是 $[i,j]$，$j$ 当然可以是 $n-1$，也可以是 $<n-1$，所以 $ans=max(ans,f[n][1],f[n][2])$

从左到右遍历 $nums$，设$x=nums[i]$，考虑转移来源：

• 【左】只能从【左】转移过来，$f[i+1][0]$ 只能从 $f[i][0]$ 转移过来，即 $f[i+1][0]=f[i][0]+(x==k?1:0)$，（PS：实际上就是计算 $k$ 的出现次数，可以使用一个变量来表示）
• 【左 + 中】可以从【左】或者【左 + 中】转移过来，如果 $x==target$，$f[i+1][1]=max(f[i][0],f[i][1])+1$，此时如果从 $f[i][0]$ 转移过来表示被修改子数组从 $i$ 位置开始；如果从 $f[i][1]$ 转移过来表示 $nums[i-1]$ 也在被修改子数组中。如果 $x!=target$，$f[i+1][1]=max(f[i][0],f[i][1])$
• 【左 + 中 + 右】可以从【左 + 中】或者【左 + 中 + 右】转移过来，如果 $x==k$，$f[i+1][1]=max(f[i][1],f[i][2])+1$，此时如果从 $f[i][1]$ 转移过来表示 $nums[i-1]$ 是被修改子数组的最后一个元素；如果从 $f[i][2]$ 转移过来表示被修改子数组的最后下标$<i-1$。

代码如下：

class Solution {public int maxFrequency(int[] nums, int k) {Set<Integer> set = new HashSet<>();for(int x : nums) set.add(x);int n = nums.length;int ans = 0;for(int tar : set){int[][] f = new int[n+1][3];for(int i=0; i<n; i++){int x = nums[i];f[i+1][0] = f[i][0] + (x == k ? 1 : 0);f[i+1][1] = Math.max(f[i][0], f[i][1]) + (x == tar ? 1 : 0);f[i+1][2] = Math.max(f[i][1], f[i][2]) + (x == k ? 1 : 0);}ans = Math.max(ans, Math.max(f[n][1], f[n][2]));}return ans;}
}
//化简之后
class Solution {public int maxFrequency(int[] nums, int k) {Set<Integer> set = new HashSet<>();for(int x : nums) set.add(x);int n = nums.length;int ans = 0;for(int tar : set){int f0 = 0, f1 = 0, f2 = 0;for(int x : nums){f2 = Math.max(f1, f2) + (x == k ? 1 : 0);f1 = Math.max(f0, f1) + (x == tar ? 1 : 0);f0 = f0 + (x == k ? 1 : 0);}ans = Math.max(ans, Math.max(f1, f2));}return ans;}
}

四、3435. 最短公共超序列的字母出现频率

题目链接

举一个例子 $words=[aa,ab,ac,ad,ba,ca]$，至少需要几个 $a$ 才能满足所有排列，答案是两个，只需要将 $a$ 放在两端，我们就可以直接得出 $a\ast$，$aa$，$\ast a$，（即关于 $a$ 的所有排列），对于其它字符也是同理，可以得出一个结论：对于 $words$ 中出现的字符，它要么出现一次，要么出现两次。又因为本题在一个 $words$ 中至多出现16个不同字符，所以可以暴力枚举 $words$ 中不同字符出现的次数来解决这道题。

接下来问题就变成了如何判断这些字符是否有一种排列能满足 $words$ 中的所有字符串是它的子序列：

• 由上述的推导可知，如果一个字符出现了 2 次，只要放在两端一定可以得到关于它的任意排列，所以这里只需要考虑出现 1 次的字符。
• 对于只出现 1 次的字符，比如说 abcd 四个字符各出现了一次，如果 $words$ 中有 ab 和 ba，那么不管怎么排列都不可能满足条件，如果把它当成一个有向图，a -> b -> a，也就是说对于只出现 1 次的字符不能出现环，如果出现环，就说明这个字符需要出现 2 次才能满足条件。
• 判断有向图是否有环可以有两种做法：拓扑排序、三色标记法

代码如下：

//拓扑排序
class Solution {public List<List<Integer>> supersequences(String[] words) {int all = 0;//统计出现了那些字符for(String s : words){int x = s.charAt(0) - 'a';int y = s.charAt(1) - 'a';all |= 1 << x | 1 << y;}Set<Integer> set = new HashSet<>();int minSize = Integer.MAX_VALUE;int sub = all;//枚举哪些字符出现2次do{int size = Integer.bitCount(sub);if(size <= minSize && !hasCycle(sub, words)){if(size < minSize){minSize = size;set.clear();}set.add(sub);}sub = (sub - 1) & all;}while(sub != all);List<List<Integer>> ans = new ArrayList<>(set.size());for(int s : set){List<Integer> cnt = new ArrayList<>();for(int i=0; i<26; i++){cnt.add((all>>i&1)+(s>>i&1));}ans.add(cnt);}return ans;}private boolean hasCycle(int sub, String[] words){List<Integer>[] g = new ArrayList[26];Arrays.setAll(g, e->new ArrayList<>());int[] cnt = new int[26];for(String s : words){int x = s.charAt(0) - 'a';int y = s.charAt(1) - 'a';if((sub>>x&1)==0 && (sub>>y&1)==0){g[x].add(y);cnt[y]++;}}Queue<Integer> que = new LinkedList<>();for(int i=0; i<26; i++){if(cnt[i] == 0) que.add(i);}while(!que.isEmpty()){int poll = que.poll();for(int x : g[poll]){if(--cnt[x] == 0)que.add(x);}}for(int x : cnt){if(x > 0) return true;}return false;}
}
//三色标记法
class Solution {public List<List<Integer>> supersequences(String[] words) {int all = 0;List<Integer>[] g = new ArrayList[26];Arrays.setAll(g, e->new ArrayList<>());for(String s : words){int x = s.charAt(0) - 'a';int y = s.charAt(1) - 'a';all |= 1 << x | 1 << y;g[x].add(y);}Set<Integer> set = new HashSet<>();int minSize = Integer.MAX_VALUE;int sub = all;do{int size = Integer.bitCount(sub);if(size <= minSize && !hasCycle(sub, g)){if(size < minSize){minSize = size;set.clear();}set.add(sub);}sub = (sub - 1) & all;}while(sub != all);List<List<Integer>> ans = new ArrayList<>(set.size());for(int s : set){List<Integer> cnt = new ArrayList<>();for(int i=0; i<26; i++){cnt.add((all>>i&1)+(s>>i&1));}ans.add(cnt);}return ans;}private boolean hasCycle(int sub, List<Integer>[] g){int[] color = new int[26];for(int i=0; i<26; i++){if(color[i]==0&&(sub>>i&1)==0&&dfs(i, color, g, sub)){return true;}}return false;}private boolean dfs(int x, int[] color, List<Integer>[] g, int sub){color[x] = 1;for(int y : g[x]){if((sub>>y&1)!=0){continue;}if(color[y]==1 || color[y]==0 && dfs(y, color, g, sub)){return true;}}color[x] = 2;return false;}
}