目录
一,3110. 字符串的分数
二,3111. 覆盖所有点的最少矩形数目
三,3112. 访问消失节点的最少时间编辑
写法一:朴素 Dijkstra(适用于稠密图,即边比较多的图)
写法二:堆优化 Dijkstra(适用于稀疏图,即边比较少的图)
四,3113. 边界元素是最大值的子数组数目
一,3110. 字符串的分数
本题就是求相邻字符差值绝对值的和,从下标1开始遍历,计算 i 和 i-1 的差值绝对值,将其加起来就是答案。
代码如下:
class Solution {
public int scoreOfString(String s) {
int ans = 0;
for(int i=1; i<s.length(); i++){
ans += Math.abs(s.charAt(i)-s.charAt(i-1));
}
return ans;
}
}
二,3111. 覆盖所有点的最少矩形数目
仔细读题可以发现,其实这题与纵坐标没有关系,只需要关注横坐标就行了,所以题目就变成了在 x2 - x1 <= w 的情况下,最少需要几个线段才能覆盖所有横坐标。
该题需要对横坐标进行排序,再遍历横坐标,用一个变量 r 来统计在以 x 为左端点时最大的右端点,即 r = x + w,当有 xi > r 时,就说明需要添加一个线段ans++,跟新 r = xi + w,直到跳出循环,返回ans
代码如下:
class Solution {
public int minRectanglesToCoverPoints(int[][] points, int w) {
Arrays.sort(points, (x,y)->x[0]-y[0]);//排序
int ans = 0;
int r = -1;
for(int i=0; i<points.length; i++){
if(r < points[i][0]){//跟新右端点和ans
r = points[i][0] + w;
ans++;
}
}
return ans;
}
}
三,3112. 访问消失节点的最少时间
本题求点到点最短路径,一道标准的 djstra算法题(注:该算法不适用于有负权重的图),简单说一下djstra算法的思路:从初始点出发,选出与初始点相邻且距离最近的点,再从初始点和选出的点出发,选出相邻且距离最近的点。(注:每次选出一个点,且该点不是之前选过的点)
这么说有点抽象,画个图理解一下:
可以发现,每次都会找到一个A -> ? 的最短路径,也就是说只要循环 n-1 次,就可以找到A点到其他所有点的最短路径。而在代码实现过程中需要两个数组,一个数组来统计该点是否被访问过,一个数组统计 A->? 的最短路径。
这里先介绍两种写法:
模板一:朴素 Dijkstra(适用于稠密图,即边比较多的图)
class Solution { public int moban(int n, int[][] edges) { //稠密图建图推荐使用数组建图 //注:根据题目建图,这里建的是无向图 int[][] g = new int[n][n]; for(int i=0; i<n; i++) Arrays.fill(g[i], Integer.MAX_VALUE/2); for(int[] e : edges){ int x = e[0], y = e[1], w = e[2]; g[x][y] = w; g[y][x] = w; } int[] dis = new int[n];//存储从0->i节点的最短路径 Arrays.fill(dis, Integer.MAX_VALUE/2);//防溢出 dis[0] = 0;//0->0路径为0 boolean[] vis = new boolean[n];//统计i点是否已经选择过 for(int i=0; i<n-1; i++){ int x = -1; for(int j=0; j<n; j++){//找出未访问过的距离A点最近的点 if(!vis[j]&&(x==-1 || dis[j]<dis[x])){ x = j; } } vis[x] = true;//该路径即为0->x的最短路径 for(int y=0; y<n; y++){//更新0->y的最短路径 dis[y] = Math.min(dis[y], dis[x]+g[x][y]); //注:虽然会遍历到已经访问过的点,但是不会对结果造成影响 } } return dis; } }
模板二:堆优化 Dijkstra(适用于稀疏图,即边比较少的图)
class Solution { public int[] moban(int n, int[][] edges) { //稀疏图建议使用链表建图 //注:根据题目建图,这里是无向图 List<int[]>[] g = new ArrayList[n]; Arrays.setAll(g, e->new ArrayList<>()); for(int[] e : edges){ int x = e[0], y = e[1], w = e[2]; g[x].add(new int[]{y, w}); g[y].add(new int[]{x, w}); } int[] dis = new int[n];//0->i的最短路径 Arrays.fill(dis, -1); dis[0] = 0; PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[0]-y[0]);//小根堆 que.offer(new int[]{0, 0});//(t,j)->t:路径,j:节点 while(!que.isEmpty()){ int[] poll = que.poll(); int dx = poll[0]; int x = poll[1]; if(dx > dis[x])//堆的懒删除 continue; for(int[] y : g[x]){ int newDis = dis[x] + y[1]; if(dis[y[0]]==-1 || newDis < dis[y[0]]){//更新与x点相邻的点的最短路径 dis[y[0]] = newDis; que.offer(new int[]{newDis, y[0]}); } } } return dis; } }
本题代码如下:
class Solution {
public int[] minimumTime(int n, int[][] edges, int[] disappear) {
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edges){
int x = e[0], y = e[1], w = e[2];
g[x].add(new int[]{y, w});
g[y].add(new int[]{x, w});
}
int[] dis = new int[n];
Arrays.fill(dis, -1);
dis[0] = 0;
PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[0]-y[0]);
que.offer(new int[]{0, 0});//(t,j)->t:时间,j:节点
while(!que.isEmpty()){
int[] poll = que.poll();
int dx = poll[0];
int x = poll[1];
if(dx > dis[x])
continue;
for(int[] y : g[x]){
int newDis = dis[x] + y[1];
//本题多了一个条件,所以这里多了个判断
if(newDis < disappear[y[0]] && (dis[y[0]]==-1 || newDis < dis[y[0]])){
dis[y[0]] = newDis;
que.offer(new int[]{newDis, y[0]});
}
}
}
return dis;
}
}
四,3113. 边界元素是最大值的子数组数目
本题本质上还是一道单调栈的题,画个图理解一下:
从左往右依次遍历:
- [1]时,有[1]成立
- [1,4]时,多出[4]成立,这时候1就成了垃圾数据,因为如果包含1,那么这个数组不可能满足题意。删去1
- [4,3]时,多出[3]成立,这时4不能删去,因为右端可能出现一个4,使其满足题意
- [4,3,2]时,多出[2]成立,这时2不能删去,因为右端可能出现一个2,使其满足题意
- [4,3,2,3]时,多出[3][3,2,3]成立,这时2就成了垃圾数据,因为如果包含2,那么这个数组不可能满足题意。删去2
- [4,3,3,1]时,多出[1]
可以发现[4,3,3,1]是单调减的,所以可以使用单调栈来解决该问题。
代码如下:
class Solution {
public long numberOfSubarrays(int[] nums) {
long ans = 0;
Deque<int[]> que = new ArrayDeque<>();
que.add(new int[]{Integer.MAX_VALUE, 0});//防止que为空
for(int num : nums){
while(que.getLast()[0]<num){
que.removeLast();
}
if(que.getLast()[0] == num)
que.addLast(new int[]{num, que.getLast()[1]+1});
else
que.addLast(new int[]{num, 1});
ans += que.getLast()[1];
}
return ans;
}
}