Leetcode - 147双周赛

目录

  • 一、3407. 子字符串匹配模式
  • 二、3408. 设计任务管理器
  • 三、3409. 最长相邻绝对差递减子序列
  • 四、3410. 删除所有值为某个元素后的最大子数组和

一、3407. 子字符串匹配模式

题目链接
在这里插入图片描述
字符串匹配问题,把字符串 p 分成两段 、,i 是 ’ * ’ 的下标,判断 s 是否包含这两段,且这两段处于不相交 && 有前后关系

代码如下:

class Solution {
    public boolean hasMatch(String s, String p) {
        int idx = p.indexOf('*');
        int i = s.indexOf(p.substring(0, idx));
        return i>=0 && s.substring(i+idx).contains(p.substring(idx+1));
    }
}

二、3408. 设计任务管理器

题目链接
在这里插入图片描述
使用哈希存当前每个 taskId,对应的 userId 和 priority,再使用堆存储 taskId 和 priority,按照 priority 排序,如果优先级相同,按照 taskId 排序。

  • TaskManager(),将数据存入哈希表和堆
  • add(),将数据存入哈希表和堆
  • edit(),更新哈希表,将更新后的数据存入堆
  • rmv(),更新哈希表 execTop(),不断的将数据排出堆,使用懒删除,如果当前数据存储在哈希表中,返回当前的 userId

代码如下:

class TaskManager {
    Map<Integer, int[]> map = new HashMap<>();
    PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[1]==y[1]?y[0]-x[0]:y[1]-x[1]);
    public TaskManager(List<List<Integer>> tasks) {
        for(List<Integer> x : tasks){
            int userId = x.get(0), taskId = x.get(1), priority = x.get(2);
            map.put(taskId, new int[]{userId, priority});
            que.offer(new int[]{taskId, priority});
        }    
    }
    
    public void add(int userId, int taskId, int priority) {
        map.put(taskId, new int[]{userId, priority});
        que.offer(new int[]{taskId, priority});
    }
    
    public void edit(int taskId, int newP) {
        int[] t = map.get(taskId);
        t[1] = newP;
        map.put(taskId, t);
        que.offer(new int[]{taskId, t[1]});
    }
    
    public void rmv(int taskId) {
        map.remove(taskId);
    }
    
    public int execTop() {
        while(!que.isEmpty()){
            int[] t = que.poll();
            if(map.containsKey(t[0]) && map.get(t[0])[1] == t[1]){
                int user = map.get(t[0])[0];
                map.remove(t[0]);
                return user;
            }
        }
        return -1;
    }
}

三、3409. 最长相邻绝对差递减子序列

题目链接
在这里插入图片描述
定义 f [ i ] [ j ] f[i][j] f[i][j]: 以 x = n u m s [ i ] x = nums[i] x=nums[i] 为结尾的且与倒数第二个数的绝对值的差至少 j j j(即倒数第二个数为 x − j / x + j x-j/x+j xj/x+j)的子序列的最长长度。

对于 x = n u m s [ i ] x = nums[i] x=nums[i],题目要求两数差的绝对值是非递增的(即倒数第三个数和倒数第二个数的绝对差值 > = j >=j >=j ),分类讨论:

  • n u m s [ i ] nums[i] nums[i] 单独形成一个子序列 , f [ i ] [ j ] = 1 f[i][j] = 1 f[i][j]=1
  • 倒数第一个数和倒数第二个数的绝对差值 > j >j >j,也就是绝对差值 > = j + 1 >=j+1 >=j+1 f [ i ] [ j ] = f [ i ] [ j + 1 ] f[i][j] = f[i][j+1] f[i][j]=f[i][j+1]
  • 倒数第一个数和倒数第二个数的绝对差值 = j =j =j,也就是倒数第二个数的值为 x + j / x − j x+j/x-j x+j/xj f [ i ] [ j ] = m a x ( f [ l a s t [ x − j ] ] [ j ] , f [ l a s t [ x + j ] ] [ j ] ) f[i][j] = max(f[last[x-j]][j],f[last[x+j]][j]) f[i][j]=max(f[last[xj]][j]f[last[x+j]][j])
  • l a s t [ x ] last[x] last[x]:值为 x x x 的数在 n u m s nums nums 数组中的下标

最终 f [ i ] [ j ] = m a x ( 1 , f [ i ] [ j + 1 ] , f [ l a s t [ x + j ] ] [ j ] , f [ l a s t [ x − j ] ] [ j ] ) f[i][j] = max(1,f[i][j+1],f[last[x+j]][j],f[last[x-j]][j]) f[i][j]=max(1,f[i][j+1],f[last[x+j]][j],f[last[xj]][j])

代码如下:

class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length;
        int mx = nums[0], mn = nums[0];
        for(int x : nums){
            mx = Math.max(mx, x);
            mn = Math.min(mn, x);
        }
        int maxD = mx - mn;
        int ans = 0;
        int[][] f = new int[n][maxD+2];
        int[] last = new int[mx + 1];
        Arrays.fill(last, -1);
        for(int i=0; i<n; i++){
            int x = nums[i];
            for(int j=maxD; j>=0; j--){
                f[i][j] = Math.max(f[i][j+1], 1);
                if(x - j >= 0 && last[x - j] >= 0){
                    f[i][j] = Math.max(f[i][j], f[last[x-j]][j] + 1);
                }
                if(x + j <= mx && last[x+j] >= 0){
                    f[i][j] = Math.max(f[i][j], f[last[x+j]][j] + 1);
                }
                ans = Math.max(ans, f[i][j]);
            }
            last[x] = i;
        }
        return ans;
    }
}

//定义f[x][j]:以值 x 结尾的且与倒数第二个数的绝对差值至少为 j 的子序列的最长长度
class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length;
        int mx = nums[0], mn = nums[0];
        for(int x : nums){
            mx = Math.max(mx, x);
            mn = Math.min(mn, x);
        }
        int maxD = mx - mn;
        int ans = 0;
        int[][] f = new int[mx+1][maxD+1];
        for(int x : nums){
            int fx = 1;
            for(int j=maxD; j>=0; j--){
                if(x-j >= 0){
                    fx = Math.max(fx, f[x-j][j] + 1);
                }
                if(x+j <= mx){
                    fx = Math.max(fx, f[x+j][j] + 1);
                }
                f[x][j] = fx;
                ans = Math.max(ans, fx);
            }
        }
        return ans;
    }
}

四、3410. 删除所有值为某个元素后的最大子数组和

题目链接
在这里插入图片描述
本题直接使用线段数来维护四个值——区间和,最大前缀和,最大后缀和,区间最大子数组和,代码如下:

class SegmentTree{
    private record Info(long sum, long pre, long suf, long ans){}
    Info[] tree;
    public SegmentTree(int[] nums){
        int n = nums.length;
        tree = new Info[n<<2];
        build(1, 0, n-1, nums);
    }
    void build(int i, int l, int r, int[] nums){
        if(l == r){
            int val = nums[l];
            tree[i] = new Info(val, val, val, val);
            return;
        }
        int m = (l + r) / 2;
        build(i<<1, l, m, nums);
        build(i<<1|1,m+1,r,nums);
        tree[i] = merge(tree[i<<1],tree[i<<1|1]);
    }
    Info merge(Info a, Info b){
        return new Info(
            a.sum + b.sum,
            Math.max(a.pre, a.sum+b.pre),
            Math.max(b.suf, a.suf+b.sum),
            Math.max(Math.max(a.ans, b.ans), a.suf+b.pre)
        );
    }
    void update(int o, int l, int r, int i, int val){
        if(l == r){
            tree[o] = new Info(val, val, val, val);
            return;
        }
        int m = (l + r) / 2;
        if(i <= m){
            update(o<<1, l, m, i, val);
        }else{
            update(o<<1|1, m+1, r, i, val);
        }
        tree[o] = merge(tree[o<<1], tree[o<<1|1]);
    }
    long queryAll(){
        return tree[1].ans;
    }
}
class Solution {
    public long maxSubarraySum(int[] nums) {
        SegmentTree t = new SegmentTree(nums);
        long ans = t.queryAll();
        if(ans <= 0) return ans;
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<n; i++){
            if(nums[i] < 0)
                map.computeIfAbsent(nums[i], e->new ArrayList<>()).add(i);
        }
        for(List<Integer> x : map.values()){
            for(int i : x){
                t.update(1, 0, n-1, i, 0);
            }
            ans = Math.max(ans, t.queryAll());
            for(int i : x){
                t.update(1, 0, n-1, i, nums[i]);
            }
        }
        return ans;
    }
}

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

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

相关文章

数据预测2025年AI面试市场增幅超500%!

近年来&#xff0c;随着人工智能技术的迅猛发展&#xff0c;AI在各行各业的应用逐渐广泛&#xff0c;其中企业招聘领域也不例外。最新的数据显示&#xff0c;2025年AI面试市场将迎来前所未有的增长&#xff0c;预计增幅将超过500%。这一预测不仅揭示了AI技术在招聘领域的应用潜…

浅谈云计算08 | 基本云架构

浅谈基本云架构 一、负载分布架构二、资源池架构三、动态可扩展架构四、弹性资源容量架构五、服务负载均衡架构六、云爆发架构七、弹性磁盘供给架构八、冗余存储架构 在当今数字化时代&#xff0c;云计算已成为企业发展的核心驱动力&#xff0c;而其背后的一系列关键架构则是支…

【专题】2025年节日营销趋势洞察报告汇总PDF洞察(附原数据表)

原文链接&#xff1a; https://tecdat.cn/?p38813 在当今复杂多变且竞争激烈的消费市场环境下&#xff0c;节日营销已成为企业获取市场份额、提升品牌影响力的关键战略时机。我们深知深入洞察节日营销趋势对于企业决策的重要性。 本报告汇总基于对 2024 年多个关键消费节点及…

【Linux系统】权限位(mode bits)

这张图是使用结构体 struct stat 中的 st_mode 字段时画的&#xff0c;获取表示文件的类型和权限&#xff0c;它是典型的 POSIX 系统调用&#xff08;如 stat() 和 fstat()&#xff09;返回的 struct stat 结构的一部分&#xff0c;用于描述文件的元数据。 在 Linux 和 Unix 系…

无源器件-电容

电容器件的参数 基本概念由中学大学物理或电路分析内容获得&#xff0c;此处不做过多分析。 电容的产量占全球电子元器件产品的40%以上。 单位&#xff1a;法拉 F&#xff1b;1F10^6uF&#xff1b;电路中常见的104电容就是10*10^4pF100nF0.1uF C为电容&#xff0c;Rp为绝缘电…

Go语言之路————go环境的初始化

Go语言之路————go环境的初始化 前言一、Go的安装二、环境配置三、初始化一个新项目四、常用的一些指令 前言 我是一名多年Java开发人员&#xff0c;因为工作需要现在要学习go语言&#xff0c;Go语言之路是一个系列&#xff0c;记录着我从0开始接触Go&#xff0c;到后面能正…

数据结构与算法之链表: LeetCode 234. 回文链表 (Ts版)

回文链表 https://leetcode.cn/problems/palindrome-linked-list/description/ 描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 示例 1 输入&#xff1a;head [1,2,2,1]…

Hive4.0.1集群安装部署(Hadoop版本为3.3.6)(详细教程)

前置环境 ​​​Linux环境Zookeeper集群安装&#xff08;详细教程&#xff09;-CSDN博客 Hadoop HA高可用集群3.3.6搭建&#xff08;详细教程&#xff09;-CSDN博客 MySQL8.0.40离线安装&#xff08;详细教程&#xff09;_mysql 8.0.40 ftp-CSDN博客 Hadoop3.3.6官网下载链接地…

Windows安装ES单机版设置密码

下载ES ES下载链接 我用的是7.17.26 启动前配置 解压之后打开D:\software\elasticsearch-7.17.26\bin\elasticsearch-env.bat 在elasticsearch-env.bat文件中修改jdk的路径 修改前 修改内容 if defined ES_JAVA_HOME (set JAVA"D:\software\elasticsearch-7.17.26\…

Wireshark抓包教程(2024最新版个人笔记)

改内容是个人的学习笔记 Wireshark抓包教程&#xff08;2024最新版&#xff09;_哔哩哔哩_bilibili 该课程笔记1-16 wireshark基础 什么是抓包工具&#xff1a;用来抓取数据包的一个软件 wireshark的功能&#xff1a;用来网络故障排查&#xff1b;用来学习网络技术 wireshark下…

云平台一键部署【Video-Background-Removal】视频换背景,无任何限制,随意换

Video-Background-Removal 是一款革命性的视频背景替换工具&#xff0c;旨在让用户轻松实现视频背景的快速更换。无论你是专业创作者还是普通用户&#xff0c;这款软件都能让你在几秒钟内改变背景&#xff0c;完全消除限制&#xff0c;随心所欲&#xff0c;随时随地想换就换&am…

2025年,华为认证HCIA、HCIP、HCIE 该如何选择?

眼看都到 2025 年啦&#xff0c;华为认证还吃香不&#xff1f; 把这问题摆在每个网络工程师跟前&#xff0c;答案可没那么容易说清楚。 到底考不考它值当不值当&#xff0c;重点在于您自己的职业规划&#xff0c;还有对行业走向的领会。 2025 年华为认证仍然值得一考&#…

使用 Docker 部署 Java 项目(通俗易懂)

目录 1、下载与配置 Docker 1.1 docker下载&#xff08;这里使用的是Ubuntu&#xff0c;Centos命令可能有不同&#xff09; 1.2 配置 Docker 代理对象 2、打包当前 Java 项目 3、进行编写 DockerFile&#xff0c;并将对应文件传输到 Linux 中 3.1 编写 dockerfile 文件 …

学习threejs,使用TrackballControls相机控制器

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.TrackballControls 相…

C# OpenCV机器视觉:转速测量

在一个看似平常却又暗藏神秘能量的日子里&#xff0c;阿杰正在他那充满科技感的实验室里&#xff0c;对着一堆奇奇怪怪的仪器发呆。突然&#xff0c;手机铃声如一道凌厉的剑气划破寂静&#xff0c;原来是工厂的赵厂长打来的紧急电话&#xff1a;“阿杰啊&#xff0c;咱们工厂新…

机器视觉4-损失函数与梯度计算

机器视觉4-损失函数与梯度计算 损失函数定义公式及变量含义整体理解 多类支撑向量机损失正则项与超参数什么是超参数一、与模型参数的区别二、常见的超参数三、调参方法 什么是优化一、参数优化的重要性二、利用损失函数进行反馈三、调整分类器参数的方法 优化的目标一、最小化…

网络安全-RSA非对称加密算法、数字签名

数字签名非常普遍&#xff1a; 了解数字签名前先了解一下SHA-1摘要&#xff0c;RSA非对称加密算法。然后再了解数字签名。 SHA-1 SHA-1&#xff08;secure hash Algorithm &#xff09;是一种 数据加密算法。该算法的思想是接收一段明文&#xff0c;然后以一种不可逆的方式将…

Lianwei 安全周报|2025.1.13

新的一周又开始了&#xff0c;以下是本周「Lianwei周报」&#xff0c;我们总结推荐了本周的政策/标准/指南最新动态、热点资讯和安全事件&#xff0c;保证大家不错过本周的每一个重点&#xff01; 政策/标准/指南最新动态 01 美国国土安全部发布《公共部门生成式人工智能部署手…

LabVIEW部署Web服务

目录 LabVIEW部署Web服务1、创建项目2、创建Web服务3、新建WebVI3.1、使用GET方法3.2、使用POST方法 4、 部署和对应URL4.1、应用程序&#xff1a;80804.2、本地调试&#xff1a;80094.3、NI Web服务器&#xff1a;9090(禁用) 5、测试5.1、测试GET方法5.2、测试POST方法 6、实际…

初阶数据结构【栈及其接口的实现】

目录 前言一、栈的概念及结构二、栈的实现方式三、栈的实现3.1 基本结构3.2 栈的基本功能接口栈的初始化栈的销毁 3.3 入栈接口3.4 出栈接口3.5 栈的其它接口获取数据的个数接口栈判断是否为空接口获取栈顶数据接口 注&#xff1a;为什么要实现这些简单的接口&#xff0c;直接调…