Leetcode - 128双周赛

目录

一,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;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547755.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

海思Hi3519 DV500 部署yolov5并加速优化

本项目代码已开源&#xff0c;见文末 导出onnx模型 yolov5官方地址 利用官方命令导出python export.py --weights yolov5n.pt --include onnx 或者自写代码导出 import os import sys os.chdir(sys.path[0]) import onnx import torch sys.path.append(..) from models.co…

Maui 显示当前时间

1、MainPage.xaml.cs 代码 using System.Threading;namespace Mauitime {public partial class MainPage : ContentPage{private Timer _timer;public MainPage(){InitializeComponent();_timer new Timer(_ > UpdateCurrentTime(), null, 0, 1000);}// 在页面显示时更新当…

CMC学习系列 (10):CMC计算方法介绍

CMC计算方法介绍 0. 引言1. 主要贡献2. 方法2.1 普通CMC2.2 小波CMC2.3 其余方法2.4 预处理增强型CMC 3. 总结欢迎来稿 论文地址&#xff1a;https://www.frontiersin.org/articles/10.3389/fnhum.2019.00100/full 论文题目&#xff1a;Corticomuscular Coherence and Its Appl…

基于springboot的高校教师教学质量评价系统

基于springboot的高校教师教学质量评价系统 前言 随着社会的发展&#xff0c;高校教师教学质量评价系统的管理形势越来越严峻。越来越多的用户利用互联网获得信息&#xff0c;但高校教师教学质量评价系统信息鱼龙混杂&#xff0c;信息真假难以辨别。为了方便用户更好的获得高…

2.SG90舵机模块

当我们输出一段脉冲信号的时候就可以调节舵机的角度 我们可以从原理图可以看到舵机的脚在PA6 从芯片手册我们又可以看到PA6对应TIM3_CH1,并且不用开启部分重映像就能使用 新建Servo.c存放PWM初始化 配置PWM void Servo_TIM3_Init(u16 arr,u16 psc) {//开启TIM3的时钟RCC_APB1…

Docker部署SpringBoot服务(Jar包映射部署)

介绍 项目在docker部署运行以后&#xff0c;每次需更新jar包时&#xff0c;都得重新制作镜像&#xff0c;再重新制作容器。流程及其繁琐&#xff0c;效率极低。 以下步骤是在不更新镜像和容器的前提下&#xff0c;直接更新jar完成项目更新的操作。 不重新制作镜像部署 1. 创…

基于单片机的智能模拟路灯控制系统

摘 要: 随着电力资源的紧缺,以及光污染和雾霾天气的影响,更智能化的路灯设计对人们的日常生活意义重大。本文的智能路灯控制系统是基于单片机的控制器,通过介绍该系统相应的硬件设计和软件设计,实现定时开关和依具体情况是否需要来开关路灯和进行亮度调节,并且具有自检功能…

CESS 受邀出席香港Web3.0标准化协会第一次理事会议,共商行业未来

2024 年 4 月 5 日&#xff0c;CESS&#xff08;Cumulus Encrypted Storage System&#xff09;作为香港 Web3.0 标准化协会的副理事会成员&#xff0c;于香港出席了 2024 年度第一次理事会会议。此次会议汇聚了来自不同领域的知名企业和专家&#xff08;参会代表名单见文末&am…

PaddleOCR训练自己模型(1)----数据准备

一、下载地址&#xff1a; PaddleOCR开源代码&#xff08;下载的是2.6RC版本的&#xff0c;可以根据自己需求下载&#xff09; 具体环境安装就不详细介绍了&#xff0c; 挺简单的&#xff0c;也挺多教程的。 二、数据集准备及制作 &#xff08;1&#xff09;下载完代码及配置…

实时气象水文监测站

TH-SW4随着科技的飞速发展和人类对环境保护意识的日益增强&#xff0c;实时气象水文监测站在水库环境管理中的作用日益凸显。这种在线监测技术不仅为水库的安全运行提供了坚实的技术支撑&#xff0c;也为环境保护和灾害预防提供了及时、准确的数据支持。 一、实时气象水文监测…

酷开科技以用户为中心,搭建强大空间赋能的酷开系统

从市场前景和竞争格局来看&#xff0c;现在人口红利正在消逝&#xff0c;中国刚需类家电消费正在进入饱和期。在目前激烈的市场竞争环境下&#xff0c;智能家电正在成为家居市场新宠儿。酷开科技以用户为中心&#xff0c;为用户搭建智能的酷开系统&#xff0c;具有强大的空间赋…

[C++][算法基础]求最小生成树(Prim)

给定一个 n 个点 m 条边的无向图&#xff0c;图中可能存在重边和自环&#xff0c;边权可能为负数。 求最小生成树的树边权重之和&#xff0c;如果最小生成树不存在则输出 impossible。 给定一张边带权的无向图 G(V,E)&#xff0c;其中 V 表示图中点的集合&#xff0c;E 表示图…

【C++】explicit关键字详解(explicit关键字是什么? 为什么需要explicit关键字? 如何使用explicit 关键字)

目录 一、前言 二、explicit关键字是什么&#xff1f; 三、构造函数还具有类型转换的作用 &#x1f34e;单参构造函数 ✨引出 explicit 关键字 &#x1f34d;多参构造函数 ✨为什么需要explicit关键字&#xff1f; ✨怎么使用explicit关键字&#xff1f; 四、总结 五…

硕博电子经济型高性能LED面板

在科技进步的洪流中&#xff0c;硕博电子始终保持敏锐的洞察力与创新能力。SPM-LEDP-C12是硕博电子开发的兼具性价比与创新性能的LED面板。该产品具备1路CAN总线&#xff0c;12个LED指示灯&#xff08;丝印字符带背光&#xff09;。 不同于以往独立控制的单个指示灯&#xff…

StableDiffusion-02 LoRA上手使用实测 尝试生成图片 使用多个LoRA 调整LoRA效果 10分钟上手 多图

准备工作 请你确保&#xff0c;你已经完成了 StableDiffusion-01 这一节的内容&#xff0c;可以顺利的运行SD&#xff0c;并且可以正常的生成图片。 本节我们就尝试使用LoRA并生成图片。 介绍 LoRA Stable Diffusion中的LoRA&#xff08;Low-Rank Adaptation&#xff0c;低秩…

ubuntu下的串口调试工具cutecom

系统&#xff1a;ubuntu20.04 &#xff08;1&#xff09;接线 使用 rs485&#xff1c;-----> rs232 转接口&#xff08; 设备直接出来的是rs485&#xff09;&#xff0c;电脑主机接入一根 rs232&#xff1c;-----> USB口 连接线&#xff0c;ubuntu系统下打开 termin…

【Vue】setup语法糖的使用

文章目录 setup简介使用vite-plugin-vue-setup-extend插件 指定组件名字 setup简介 <script setup> 是在单文件组件 (SFC) 中使用组合式 API 的编译时语法糖 相比较普通的<script> ,它有以下优势&#xff1a; 更少的样板内容&#xff0c;更简洁的代码。能够使用纯…

RocketMQ为什么这么快?

如果你对 RocketMQ 还不了解&#xff0c;可以查看我之前写的关于 RocketMQ 专栏 的几篇文章 如果你对 RocketMQ 源码也感兴趣&#xff0c;可以从下面这个仓库 fork 一下源码&#xff0c;我在源码中加了中文注释&#xff0c;并且后面我还会持续更新注释 https://github.com/san…

自然语言处理——情绪检测数据集

一、重要性及意义 情绪检测的重要性和意义体现在多个方面&#xff0c;不仅对于个人日常生活有深远影响&#xff0c;也在多个行业和领域中扮演着关键角色。以下是情绪检测的重要性和意义的具体体现&#xff1a; 提高人机交互体验&#xff1a; 在人工智能和机器学习驱动的系统中…

MySQL慢SQL优化方案汇总

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《mysql经验总结》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途 目录 写在前面 优化思路 避免查询不必要的列 分页优化 索引优化 JOIN优化 排序优化 UNION 优化 写在最后 写在前面 本…