总结第206场周赛和第35场双周赛。共计7道题目。
- 1583.统计不开心的朋友
- 1584.连接所有点的最小费用(最小连通树)
- 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串(思路)
- 1588.所有奇数长度的子串和(低复杂度)
- 1589.所有排列中的最大和(差分数组)
- 1590.使数组和能被P整除
- 1591.奇怪的打印机II(拓扑排序)
1583.统计不开心的朋友
比较暴力的方法,主要考察的还是数据结构。
1 | class Solution { |
1584.连接所有点的最小费用(最小连通树)
经典最小连通树的问题,注意一下这里的Java版本的写法和优化。这里的图是一个稠密图,也就是说点少边多。比较适合prim算法。
- Prim算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public int minCostConnectPoints(int[][] points) {
return Prim(points);
}
public int Prim(int[][] points) {
int n=points.length;
// 需要一个距离表,一个标记表
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
boolean[] added=new boolean[n];。
int ans=0;
for(int i=0; i<n; i++){
int min=0;
// 循环1: 寻找不在联通图中,且距离最近的点
for(int j=0; j<n; j++){
if(!added[j]&&dist[j]<dist[min]){
min=j;
}
}
added[min]=true;
if(dist[min]!=Integer.MAX_VALUE) ans+=dist[min];
// 循环2:更新距离表
for(int j=0; j<n; j++){
if(!added[j]){
// 更新在新的点进入之后,连通图到各个点的距离。
dist[j]=Math.min(dist[j], mdist(points[min], points[j]));
}
}
}
return ans;
}
int mdist(int[] x, int[] y){
return Math.abs(x[0]-y[0])+Math.abs(x[1]-y[1]);
}
} - Kruskal算法:利用并查集,每次查找最近的两个点,判断是否已经相连,若没则连接。
1 | class Solution { |
1585. 检查字符串是否可以通过排序子字符串得到另一个字符串(思路)
是一道思路题算法题,我觉着还是挺妙的。但是我很难找到通用的思路。坑神有一个思路,是说每次只是在两个元素之间进行调换。但是这里就有一个问题了,如果该数a
的后面还有一个比他大的数字a+n
,此时的调换是无法实现的。
因此我们可以从后往前数,如果当前需要a
,但是比它大的数字b
是存在的且在原数组中是在其后方,这时无论如何调换,都是无法实现的。
1 | class Solution { |
1588.所有奇数长度的子串和(低复杂度)
虽然是一道简单题目,但是可以用更低的复杂度算法。这个方法也是有点前缀和的意思。
1 | class Solution { |
1589.所有排列中的最大和(差分数组)
是一类比较有特点的题目,主要是利用差分统计区间的覆盖频次问题。维护了一个差分数组,对于每次的覆盖区间,区间头位置+1,区间结尾+1的位置-1。最后在进行累加,这样数组每个位置就对应了相应位置的频次。真的很妙了。
1 | class Solution { |
1590.使数组和能被P整除
也是一道好题,利用了取模,和前缀和。由于我们要求得到前缀和除P之后的余数,因此我们可以利用hashmap存储一下。然后每次查找最近的符合要求的位置,计算得到长度。尤其注意大数的处理。一定小心一切可能爆整数的存在。
1 | class Solution { |
1591.奇怪的打印机II(拓扑排序)
又是一道很好的题,这周的周赛真是好题啊。一道转换为拓扑排序的题目。看似是涂色,其实可以构建起颜色转换之间的有向连接。当颜色1需要覆盖在颜色2上,可以得到一个从2指向1的标志,并且1的限制条件+1。如果某个颜色的限制条件为0,就可以揭开。和选课问题一样.
1 | class Solution { |