Leetcode - 周赛434
目录
- 一、3432. 统计元素和差值为偶数的分区方案
- 二、3433. 统计用户被提及情况
- 三、3434. 子数组操作后的最大频率
- 四、3435. 最短公共超序列的字母出现频率
一、3432. 统计元素和差值为偶数的分区方案
题目链接
本题可以直接模拟，这里再介绍一个数学做法，假设
n
u
m
s
[
:
i
]
nums[:i]
nums[:i] 的和为
L
L
L，
n
u
m
s
[
:
]
nums[:]
nums[:] 的和为
S
S
S，那么
n
u
m
s
[
i
+
1
:
]
nums[i+1:]
nums[i+1:] 的和为
S
−
L
S-L
S−L，题目要求满足
a
b
s
(
L
−
(
S
−
L
)
)
abs(L-(S-L))
abs(L−(S−L)) 为偶数，化简一下得到
2
∗
L
−
S
2*L-S
2∗L−S，可以发现差值是否为偶数和怎么划分无关，只和
S
S
S 有关，而
S
S
S 是固定的（数组的和），所以只要
S
S
S 为偶数，那么方案数为
l
e
n
(
n
u
m
s
)
−
1
len(nums)-1
len(nums)−1，否则方案数为
0
0
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. 子数组操作后的最大频率
题目链接
本题可以将
n
u
m
s
nums
nums 数组分成三个部分：被修改的子数组的左边，被修改的子数组，被修改的子数组的右边，考虑将
n
u
m
s
nums
nums 中等于
t
a
r
g
e
t
target
target 的元素变成
k
k
k，我们可以定义以下三种状态：
- f [ i + 1 ] [ 0 ] f[i+1][0] f[i+1][0]：表示被修改的子数组的左边，即统计 n u m s [ : i ] nums[:i] nums[:i] 中等于 k k k 的元素个数。
- f [ i + 1 ] [ 1 ] f[i+1][1] f[i+1][1]：表示被修改的子数组 + 左边，即被修改的子数组以 i i i 结尾时 k k k 出现的最大频率。
- f [ i + 1 ] [ 2 ] f[i+1][2] f[i+1][2]：表示被修改的子数组 + 左边 + 右边，即被修改的子数组以 < i < i <i 的下标结尾时 k k k 出现的最大频率。
- 注：这三种状态都表示 n u m s [ : i ] nums[:i] nums[:i] 中 k k k 出现的最大频率，只不过表示的范围不同！！！
- 显然，假设被修改子数组的范围是 [ i , j ] [i,j] [i,j]， j j j 当然可以是 n − 1 n-1 n−1，也可以是 < n − 1 < n-1 <n−1，所以 a n s = m a x ( a n s , f [ n ] [ 1 ] , f [ n ] [ 2 ] ) ans=max(ans,f[n][1],f[n][2]) ans=max(ans,f[n][1],f[n][2])
从左到右遍历 n u m s nums nums，设 x = n u m s [ i ] x = nums[i] x=nums[i]，考虑转移来源：
- 【左】只能从【左】转移过来， f [ i + 1 ] [ 0 ] f[i+1][0] f[i+1][0] 只能从 f [ i ] [ 0 ] f[i][0] f[i][0] 转移过来，即 f [ i + 1 ] [ 0 ] = f [ i ] [ 0 ] + ( x = = k ? 1 : 0 ) f[i+1][0] = f[i][0]+(x==k?1:0) f[i+1][0]=f[i][0]+(x==k?1:0)，（PS：实际上就是计算 k k k 的出现次数，可以使用一个变量来表示）
- 【左 + 中】可以从【左】或者【左 + 中】转移过来，如果 x = = t a r g e t x == target x==target， f [ i + 1 ] [ 1 ] = m a x ( f [ i ] [ 0 ] , f [ i ] [ 1 ] ) + 1 f[i+1][1]=max(f[i][0],f[i][1])+1 f[i+1][1]=max(f[i][0],f[i][1])+1，此时如果从 f [ i ] [ 0 ] f[i][0] f[i][0] 转移过来表示被修改子数组从 i i i 位置开始；如果从 f [ i ] [ 1 ] f[i][1] f[i][1] 转移过来表示 n u m s [ i − 1 ] nums[i-1] nums[i−1] 也在被修改子数组中。如果 x ! = t a r g e t x != target x!=target， f [ i + 1 ] [ 1 ] = m a x ( f [ i ] [ 0 ] , f [ i ] [ 1 ] ) f[i+1][1]=max(f[i][0],f[i][1]) f[i+1][1]=max(f[i][0],f[i][1])
- 【左 + 中 + 右】可以从【左 + 中】或者【左 + 中 + 右】转移过来，如果 x = = k x == k x==k， f [ i + 1 ] [ 1 ] = m a x ( f [ i ] [ 1 ] , f [ i ] [ 2 ] ) + 1 f[i+1][1]=max(f[i][1],f[i][2])+1 f[i+1][1]=max(f[i][1],f[i][2])+1，此时如果从 f [ i ] [ 1 ] f[i][1] f[i][1] 转移过来表示 n u m s [ i − 1 ] nums[i-1] nums[i−1] 是被修改子数组的最后一个元素；如果从 f [ i ] [ 2 ] f[i][2] f[i][2] 转移过来表示被修改子数组的最后下标 < i − 1 <i-1 <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. 最短公共超序列的字母出现频率
题目链接
举一个例子
w
o
r
d
s
=
[
a
a
,
a
b
,
a
c
,
a
d
,
b
a
,
c
a
]
words=[aa,ab,ac,ad,ba,ca]
words=[aa,ab,ac,ad,ba,ca]，至少需要几个
a
a
a 才能满足所有排列，答案是两个，只需要将
a
a
a 放在两端，我们就可以直接得出
a
∗
a*
a∗，
a
a
aa
aa，
∗
a
*a
∗a，（即关于
a
a
a 的所有排列），对于其它字符也是同理，可以得出一个结论：对于
w
o
r
d
s
words
words 中出现的字符，它要么出现一次，要么出现两次。又因为本题在一个
w
o
r
d
s
words
words 中至多出现16个不同字符，所以可以暴力枚举
w
o
r
d
s
words
words 中不同字符出现的次数来解决这道题。
接下来问题就变成了如何判断这些字符是否有一种排列能满足 w o r d s words words 中的所有字符串是它的子序列：
- 由上述的推导可知，如果一个字符出现了 2 次，只要放在两端一定可以得到关于它的任意排列，所以这里只需要考虑出现 1 次的字符。
- 对于只出现 1 次的字符，比如说 abcd 四个字符各出现了一次，如果 w o r d s words 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;
}
}