当前位置: 首页 > news >正文

Leetcode - 周赛425

目录

一,3364. 最小正和子数组

二, 3365. 重排子字符串以形成目标字符串

三,3366. 最小数组和

四,3367. 移除边之后的权重最大和


一,3364. 最小正和子数组

本题可以直接暴力枚举,代码如下:

class Solution {public int minimumSumSubarray(List<Integer> nums, int l, int r) {int n = nums.size();int ans = Integer.MAX_VALUE;for(int k=l; k<=r; k++){int s = 0;for(int i=0, j=0; j<n; j++){s += nums.get(j);if(j-i+1 > k){s -= nums.get(i);i++;}if(j-i+1 == k && s > 0) ans = Math.min(ans, s);}}return ans==Integer.MAX_VALUE ? -1 : ans;}
}

如果它的数据范围更大一点,上述做法会超时,所以这里再介绍一个O(n*logn)的做法:

  • 这题求子数组和的最小正值,子数组和可以直接使用前缀和来求
  • 题目要求子数组的长度在 [L,R] 之间,可以枚举左端点 / 右端点,这里选择枚举右端点下标 i,再根据上述条件直接推出左端点的下标 j 的范围 [i-R,i-L]
  • 假设前缀和数组为 s,此时 si 是固定的,要使得 si - sj 的值更大,sj 必须是小于 si 的最大值(题目要求为正数),求 sj < si 的最大值且 j 属于 [i-R,i-L],这可以使用有序集合+二分来做

代码如下:

class Solution {public int minimumSumSubarray(List<Integer> nums, int l, int r) {int n = nums.size();int ans = Integer.MAX_VALUE;int[] pre = new int[n+1];for(int i=0; i<n; i++){pre[i+1] = pre[i] + nums.get(i);}//枚举右端点:[i-r, i-l] ~ i//s[i-r, i-l] < si, 二分枚举最接近si的值 TreeMap<Integer, Integer> map = new TreeMap<>();for(int i=l, j=0; i<=n; i++){map.merge(pre[i-l], 1, Integer::sum);// 错误写法:// 当l==r时,会出错(没有计算当前子数组的大小)// if(i-r > 0){//     map.merge(pre[i-r], -1, Integer::sum);//     if(map.get(pre[i-r])==0) map.remove(pre[i-r]);// } Integer res = map.lowerKey(pre[i]);if(res != null)ans = Math.min(ans, pre[i]-res);if(i-r >= 0){map.merge(pre[i-r], -1, Integer::sum);if(map.get(pre[i-r])==0) map.remove(pre[i-r]);} }return ans == Integer.MAX_VALUE ? -1 : ans;}
}

二, 3365. 重排子字符串以形成目标字符串

本题直接暴力哈希,使用哈希表统计字符串 s 中分割成 k 个等长的子字符串,再看 t 中分割出的 k 个等长子字符串是否与字符串 s 完全相同。

代码如下:

class Solution {public boolean isPossibleToRearrange(String s, String t, int k) {Map<String, Integer> map = new HashMap<>();int n = s.length();for(int i=n/k; i<=n; i+=n/k){map.merge(s.substring(i-n/k, i), 1, Integer::sum);}for(int i=n/k; i<=n; i+=n/k){String x = t.substring(i-n/k, i);map.merge(x, -1, Integer::sum);if(map.get(x) == 0) map.remove(x);if(map.getOrDefault(x, 0) < 0) return false; }return map.size() == 0;}
}

三,3366. 最小数组和

本题数据范围较小,直接使用dp暴力求解,先找与原问题相同的子问题,从前往后遍历,对于第 i 个数来说:

  • 不执行任何操作,剩下变成求 [i+1,n] 这些数进行 x 次操作1,y 次操作2后的最小元素和
  • 执行操作1,剩下变成求 [i+1,n] 这些数进行 x-1 次操作1,y 次操作2后的最小元素和
  • 执行操作2,剩下变成求 [i+1,n] 这些数进行 x 次操作1,y-1 次操作2后的最小元素和
  • 执行操作1和操作2,剩下变成求 [i+1,n] 这些数进行 x-1 次操作1,y-1 次操作2后的最小元素和

定义 dfs(i,x,y):对 [i,n] 进行 x 次操作1,y 次操作2后的最小元素和,对于 nums[i] 进行分类讨论:

  • 不执行任何操作,剩下变成求 [i+1,n] 这些数进行 x 次操作1,y次操作2后的最小元素和,即dfs(i+1,x,y) + nums[i]
  • 执行操作1,剩下变成求 [i+1,n] 这些数进行 x-1 次操作1,y次操作2后的最小元素和,即dfs(i+1,x-1,y) + (nums[i]+1)/2
  • 执行操作2,剩下变成求 [i+1,n] 这些数进行 x 次操作1,y-1次操作2后的最小元素和,即dfs(i+1,x,y-1) + nums[i] - k
  • 执行操作1和操作2,剩下变成求 [i+1,n] 这些数进行 x-1 次操作1,y-1次操作2后的最小元素和,即 dfs(i+1,x-1,y-1) + (nums[i] - k + 1)/2,同时操作时先2后1更优,(nums[i]+1)/2 - k >= (nums[i]-k+1)/2

代码如下:

class Solution {public int minArraySum(int[] nums, int k, int op1, int op2) {int n = nums.length;memo = new int[n][op1+1][op2+1];for (int[][] mat : memo) {for (int[] row : mat) {Arrays.fill(row, -1); // -1 表示没有计算过}}return dfs(0, op1, op2, k, nums);}int[][][] memo;int dfs(int i, int x, int y, int k, int[] nums){if(i == nums.length) return 0;if(memo[i][x][y] != -1) return memo[i][x][y];int res = dfs(i+1, x, y, k, nums) + nums[i];if(x > 0)res = Math.min(res, dfs(i+1, x-1, y, k, nums) + (nums[i]+1)/2);if(y > 0 && nums[i] >= k){res = Math.min(res, dfs(i+1, x, y-1, k, nums) + nums[i] - k);if(x > 0){int t = (nums[i]+1)/2 >= k ? (nums[i]+1)/2 - k : (nums[i]-k+1)/2;res = Math.min(res, dfs(i+1, x-1, y-1, k, nums) + t);}}return memo[i][x][y] = res;}
}

递推代码:

class Solution {public int minArraySum(int[] nums, int k, int op1, int op2) {int n = nums.length;int[][][] f = new int[n+1][op1+1][op2+1];for(int i=n-1; i>=0; i--){for(int x=0; x<=op1; x++){for(int y=0; y<=op2; y++){f[i][x][y] = f[i+1][x][y] + nums[i];if(x > 0)f[i][x][y] = Math.min(f[i][x][y], f[i+1][x-1][y] + (nums[i]+1)/2);if(y > 0 && nums[i] >= k){f[i][x][y] = Math.min(f[i][x][y], f[i+1][x][y-1] + nums[i] - k);if(x > 0){int t = (nums[i]+1)/2 >= k ? (nums[i]+1)/2 - k : (nums[i]-k+1)/2;f[i][x][y] = Math.min(f[i][x][y], f[i+1][x-1][y-1] + t);}}}}}return f[0][op1][op2];}
}

四,3367. 移除边之后的权重最大和

代码如下:

class Solution {public long maximizeSumOfWeights(int[][] edges, int k) {int n = edges.length;List<int[]>[] g = new ArrayList[n+1];Arrays.setAll(g, e -> new ArrayList<>());for(int[] e : edges){int x = e[0], y = e[1], val = e[2];g[x].add(new int[]{y, val});g[y].add(new int[]{x, val});}long[] f = dfs(0, -1, k, g);return f[1];//{s, s+first} f[1] >= f[0]}long[] dfs(int x, int fa, int k, List<int[]>[] g){PriorityQueue<Long> que = new PriorityQueue<>();//默认最小堆long s = 0;for(int[] y : g[x]){if(y[0] == fa) continue;long[] f = dfs(y[0], x, k, g);//选/不选 x-y 这条边 f[0]+y[1]/f[1]//选/不选 怎么在至多 选K个边 的情况下,使其最大?//先把不选的值全部求和,在求出如果选相较于不选提升了多少,//对其进行排序,选择k个提升最大的if(que.size() == k && que.peek() < f[0] + y[1] - f[1]){que.poll();}if(que.size() < k && f[0] + y[1] - f[1] > 0){que.offer(f[0] + y[1] - f[1]);}s += f[1];}long first = que.size() == k ? que.poll() : 0;while(!que.isEmpty()){s += que.poll();}return new long[]{s, s+first};}
}

 

相关文章:

Leetcode - 周赛425

目录 一&#xff0c;3364. 最小正和子数组 二&#xff0c; 3365. 重排子字符串以形成目标字符串 三&#xff0c;3366. 最小数组和 四&#xff0c;3367. 移除边之后的权重最大和 一&#xff0c;3364. 最小正和子数组 本题可以直接暴力枚举&#xff0c;代码如下&#xff1a; …...

c++(斗罗大陆2)

我把魂力等级更新到了31级 #include<iostream> #include<conio.h> #include<windows.h> #include<stdlib.h> #include<stdio.h> #include<time.h> #include<string.h> using namespace std; int qs10; int xthl0;//先…...

redis常见数据类型

Redis是一个开源的、内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息代理&#xff0c;支持多种数据类型。 一、数据类型介绍 String&#xff08;字符串&#xff09; Redis中最基本的数据类型。可以存储任何类型的数据&#xff0c;包括字符串、数字和二进制…...

MySQL - 性能优化

使用 Explain 进行分析 Explain 用来分析 SELECT 查询语句&#xff0c;开发人员可以通过分析 Explain 结果来优化查询语句。 比较重要的字段有: select_type : 查询类型&#xff0c;有简单查询、联合查询、子查询等 key : 使用的索引 rows : 扫描的行数 type &#xff1a;…...

Linux进程概念-详细版(一)

目录 进程概念 描述进程-PCB task_struct-PCB的一种 task_struct内容分类 查看进程 通过系统目录查看 通过ps命令查看 通过系统调用获取进程的PID和PPID 通过系统调用创建进程 fork的认识 使用if进行分流 最后的总结 Linux进程状态 运行状态-R 浅度睡眠状态-S 深度睡…...

K8S网络系列--Flannel网络下UDP、VXLAN模式的通信流程机制分析

文章目录 前言一、了解overlay、underlay容器网络二、网络通信1.分类2.网络虚拟设备对2.1、什么是网络虚拟设备对veth pair?2.2、如何查看容器的网卡与主机的哪个veth设备对是成对的关系? 3、vxlan和vtep3.1、vtep3.2、vxlan相关概念 三、Flannel网络模式剖析0、flannel的作用…...

ThreadLocal的设计思考

问题的提出 在Java多线程中&#xff0c;共享变量的读写非常容易出现不可预测的行为&#xff0c;因此对共享变量的访问控制非常重要。因此在多线程编程时&#xff0c;为了保证线程安全&#xff0c;需要进行额外的同步措施。比如典型的操作就是加锁。除了加锁外&#xff0c;另一…...

shell脚本练习(2)

1. 使用case实现成绩优良差的判断 2. for创建20用户 用户前缀由用户输入 用户初始密码由用户输入 例如&#xff1a;test01,test10 3. for ping测试指网段的主机 网段由用户输入&#xff0c;例如用户输入192.168.2 &#xff0c;则ping 192.168.2.10 --- 192.168.2.2…...

通讯专题4.1——CAN通信之计算机网络与现场总线

从通讯专题4开始&#xff0c;来学习CAN总线的内容。 为了更好的学习CAN&#xff0c;先从计算机网络与现场总线开始了解。 1 计算机网络体系的结构 在我们生活当中&#xff0c;有许多的网络&#xff0c;如交通网&#xff08;铁路、公路等&#xff09;、通信网&#xff08;电信、…...

Harmony NEXT-越过相机读写权限上传图片至项目云存储中

问题成因 在制作用户注册登录界面时想要实现用户头像上传共能&#xff0c;查询API文档&#xff0c;发现有picker和PhotoAccessHelper两个包可以选择使用&#xff0c;但是在使用PhotoAccessHelper包拉起相册并读入所选的照片后将该照片传入云存储中产生报错&#xff0c;需要相册…...

MATLAB基础应用精讲-【数模应用】Retinex图像去雾算法(附MATLAB和python代码实现)

目录 前言 算法原理 图像去雾 数学模型 算法步骤 算法拓展 多尺度Retinex (MSR) 算法 MSR算法的实现细节 McCann Retinex 算法 McCann99 Retinex算法 基于暗通道先验的图像去雾算法 暴力解法——直方图均衡化去雾 基于Retinex理论的图像去雾 基于暗通道先验的单…...

点击A组件跳转到B页面的tab的某一列

1、使用vuex存储点击的数据&#xff1b; 点击A组件里面的button按钮&#xff1a; <div><button click"banli(first)">已办理</button><button click"banli(second)">未办理</button><button click"banli(third)&quo…...

HarmonyOS xml转换JavaScript 常用的几个方法

HarmonyOS 使用 xml转换JavaScript 的好处 易用性&#xff1a; 提供了简洁的API接口&#xff0c;使得XML到JavaScript对象的转换变得简单直接。转换选项的灵活性允许开发者根据实际需求自定义转换结果。 高效性&#xff1a; HarmonyOS对底层运行时环境进行了优化&#xff0c;使…...

Linux笔记---进程:进程等待

1. 进程等待的概念 进程等待是指父进程通过系统调用wait或waitpid来对子进程进行状态检测与回收的功能。 当子进程退出时&#xff0c;如果父进程不读取子进程的退出状态&#xff0c;子进程就会成为僵尸进程&#xff0c;造成内存泄漏的问题。因此&#xff0c;父进程需要调用wa…...

【Linux】匿名管道通信场景——进程池

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;Linux系统编程 这里将会不定期更新有关Linux的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目…...

算法妙妙屋-------1.递归的深邃回响:全排列的奇妙组合

全排列的简要总结 全排列&#xff08;Permutation&#xff09;是数学中一个经典的问题&#xff0c;指的是从一组元素中&#xff0c;将所有元素按任意顺序排列形成的所有可能序列。 特点 输入条件&#xff1a; 给定一组互异的元素&#xff08;通常为数组或字符串&#xff09;。…...

【maven-6】Maven 生命周期相关命令演示

Maven 是一个广泛使用的项目管理工具&#xff0c;尤其在 Java 项目中。它通过定义一系列的生命周期阶段&#xff08;Phases&#xff09;来管理项目的构建过程。理解这些生命周期阶段及其相关命令&#xff0c;对于高效地构建和管理项目至关重要。本文将通过实际演示&#xff0c;…...

黑马程序员Java笔记整理(day06)

1.继承的特点 2.继承的权限 3. 4.小结 5.方法重写 6.子类构造器 7.兄弟构造器 8.多态 9.小结...

LeetCode【代码随想录】刷题(动态规划篇)

509. 斐波那契数 力扣题目链接 题目&#xff1a;斐波那契数&#xff08;通常用F(n)表示&#xff09;形成的序列称为斐波那契数列 。该数列由0和1开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n…...

【看海的算法日记✨优选篇✨】第三回:二分之妙,寻径中道

&#x1f3ac; 个人主页&#xff1a;谁在夜里看海. &#x1f4d6; 个人专栏&#xff1a;《C系列》《Linux系列》《算法系列》 ⛰️ 一念既出&#xff0c;万山无阻 目录 &#x1f4d6;一、算法思想 细节问题 &#x1f4da;左右临界 &#x1f4da;中点选择 &#x1f4da;…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...