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

《LeetCode热题100》---<5.①普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的五道题

第一道:最大子数组和(中等)

第二道:合并区间(中等)

第一道:最大子数组和(中等)

法一:贪心算法

class Solution {public int maxSubArray(int[] nums) {int len = nums.length;int cur_sum  = nums[0];int max_sum = cur_sum;for(int i = 1; i <len; i++){cur_sum = Math.max(nums[i],cur_sum+nums[i]);max_sum = Math.max(cur_sum,max_sum);}return max_sum;}
}

1.将当前和与最大和设置为数组第一个元素 

2.从第二个元素开始遍历数组元素。

  • 令当前和等于 当前元素当前和+当前元素 的最大值
  • 令最大和等于 当前和 与 最大和 的最大值

3.返回最大和,即为答案。

法二:动态规划

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}

 这个动态规划的答案实际上和上面讲的贪心算法的答案是一样的。

第二道:合并区间(中等)

方法一:排序 

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}
  • 检查空数组:如果输入的区间数组 intervals 为空,则返回一个空的二维数组。
  • 排序区间:将所有区间按起始位置进行排序,确保按从左到右的顺序处理区间。
  • 合并区间
    • 初始化一个列表 merged,用于存储合并后的区间。
    • 遍历每个区间,获取当前区间的起始位置 L 和结束位置 R
    • 如果 merged 为空,或者当前区间的起始位置 L 大于 merged 中最后一个区间的结束位置,则直接将当前区间加入 merged
    • 否则,将当前区间与 merged 中最后一个区间合并,更新最后一个区间的结束位置为二者的最大值。
  • 返回结果:将 merged 列表转换为二维数组并返回。

 通过先对区间进行排序,然后逐一合并重叠区间,最终返回合并后的区间数组。

相关文章:

《LeetCode热题100》---<5.①普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 第二道&#xff1a;合并区间&#xff08;中等&#xff09; 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 法一&#xff1a;贪心算法 class So…...

根据id查找树形结构中匹配数据与上级所有数据

背后 在用户管理业务开发过程中&#xff0c;通常需要查询出用户管理的菜单数据和当前菜单的所有上级数据。为了方便后续的cv工作&#xff0c;我打算把这种方法记录下来&#xff0c;以备不时之需. 代码实现细节 Data public class MenuDTO {Schema(description "菜单id&qu…...

探索亚马逊Amazon S3:无缝存储管理与极速数据传输的奥秘

亚马逊云科技中Amazon S3&#xff0c;因其设计简单与高度可靠&#xff0c;允许用户通过互联网存储和检索任意数量的数据&#xff0c;并能够自动扩展以满足各种规模的需求&#xff0c;使得Amazon S3成为了许多云计算应用和网站的核心存储基础设施之一&#xff0c;Amazon S3提供的…...

Linux_监测CPU和内存

通过TOP持续获取进程的CPU和内存消耗&#xff0c;并写入到表格 # 配置进程名 processvm-agent # 配置次数 number100 # 配置间隔时间 time5 # csv结果文件 filecm_$(date %s).csv echo "%CPU,%MEM">${file} pid$(ps -aux | grep ${process} | awk -F {OFS"…...

OpenCV经典案例:01 答题卡识别

目录 透视变换矫正 选项识别匹配 QT 界面设计 引言&#xff1a;随着信息化的发展&#xff0c;计算机阅卷已经成为一种常规操作。在大型考试中&#xff0c;客观题基本不再 需要人工阅卷。本项目旨在开发一个基于OpenCV的高效答题卡识别系统&#xff0c;通过先进的图像处理和模…...

进程的管理与控制详解:创建、终止、阻塞等待与非阻塞等待

目录 一、进程创建 1、实例 2、fork函数详解 (1)fork函数模板 (2). fork() 函数的工作原理 (3). fork() 返回值和错误处理 3、如何理解进程创建过程 二、进程终止 1、终止是在做什么&#xff1f; 2、进程终止&#xff0c;有三种情况 3、进程如何终止&#xff1f; 三…...

【从零开始一步步学习VSOA开发】开发环境搭建

开发环境搭建 开发 VSOA 首先需要搭建开发环境&#xff0c;这里讲解 Windows 下 C/C 开发环境搭建方法。 下载 IDE 并申请授权码 SylixOS 的开发和部署需要 RealEvo-IDE 的支持&#xff0c;因此您需要先获取 RealEvo-IDE 的安装包和注册码。 RealEvo-IDE 分为体验版和商业版…...

一篇文章让你用我的世界中的红石搞懂什么是ALU!

目录 1.一些在开始的约定 2.七大逻辑门电路 1、 与门 2、 或门 3、 非门 5、 或非门 6、 异或门 7、 同或门 3.半加器 4.全加器 5.ALU 1.一些在开始的约定 相同的概念&#xff1a;相同的概念&#xff1a;高电平低电平逻辑真逻辑假 开关的开 开关的关 灯的亮 灯…...

硬盘数据恢复:所需时长、全面指南及注意事项

在数字化时代&#xff0c;硬盘作为我们存储重要数据的核心设备&#xff0c;其重要性不言而喻。然而&#xff0c;由于各种原因&#xff0c;如误删除、格式化、硬盘故障等&#xff0c;我们时常面临数据丢失的困境。数据恢复不仅关乎个人隐私和信息安全&#xff0c;更可能影响到我…...

基于SpringBoot+Vue的科研管理系统(带1w+文档)

基于SpringBootVue的科研管理系统(带1w文档) 基于SpringBootVue的科研管理系统(带1w文档) 科研的管理系统设计过程中采用Java开发语言,B/S结构&#xff0c;采取springboot框架&#xff0c;并以MySql为数据库进行开发。结合以上技术&#xff0c;对本系统的整体、数据库、功能模块…...

计算机组成原理 —— 五段式指令流水线

计算机组成原理 —— 五段式指令流水线 五段式指令流水线运算类指令LOAD指令的执行过程STORE指令的执行过程条件转移指令执行过程无条件转移指令的执行过程 我们今天来看看五段式指令流水线&#xff1a; 五段式指令流水线 五段式指令流水线是一种常见的处理器架构设计中采用的…...

【Bigdata】什么是关系联机分析处理

这是我父亲 日记里的文字 这是他的生命 留下留下来的散文诗 几十年后 我看着泪流不止 可我的父亲已经 老得像一个影子 &#x1f3b5; 许飞《父亲写的散文诗》 关系联机分析处理&#xff08;Relational Online Analytical Processing&#xff0c;简称 ROLA…...

svd在求解最小二乘中的应用

文章目录 线性最小二乘的直接解法&#xff08;正规方程解法&#xff09;什么是伪逆&#xff1f;伪逆矩阵的一般形式伪逆矩阵与SVD的关系 线性最小二乘的直接解法&#xff08;正规方程解法&#xff09; 对于 A x b \boldsymbol{A}xb Axb的线性最小二乘问题&#xff0c;有直解析…...

JVM—垃圾收集算法和HotSpot算法实现细节

参考资料&#xff1a;深入理解Java虚拟机&#xff1a;JVM高级特性与最佳实践&#xff08;第3版&#xff09;周志明 1、分代回收策略 分代的垃圾回收策略&#xff0c;是基于这样一个事实&#xff1a;不同的对象的生命周期是不一样的。因此&#xff0c;不同生命周期的对象可以采取…...

nvidia系列教程-AGX-Orin基础环境搭建

目录 前言 一、Agx-Orin&#xff08;32GB&#xff09;介绍 1.1 GPU 1.2 CPU 1.3 NVDLA 1.4 内存 1.5 存储 二、安装JetPack SDK 三、基础环境配置 四、jetpack软件版本 总结 前言 NVIDIA Jetson AGX Orin 是一款功能强大的嵌入式AI平台&#xff0c;专为需要高性能和低…...

使用SpringAOP实现公共字段填充

文章目录 概要整体架构流程技术细节小结 概要 在新增员工或者新增菜品分类时需要设置创建时间、创建人、修改时间、修改人等字段&#xff0c;在编辑员工或者编辑菜品分类时需要设置修改时间、修改人等字段。这些字段属于公共字段&#xff0c;也就是也就是在我们的系统中很多表…...

c++初阶-----适配器---priority_queue

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…...

VSCode上安装C#环境教程

本章教程,教你如何在vscode上,可以快速运行一些基础的c#代码。 1、下载 .NET Code SDK 下载地址:https://dotnet.microsoft.com/zh-cn/download/dotnet/sdk-for-vs-code?utm_source=vs-code&utm_medium=referral&utm_campaign=sdk-install 根据自己的操作系统,选择…...

VS Code 和 Visual Studio 哪个更好

文章目录 VS Code 和 Visual Studio 哪个更好Visual Studio Code简介Visual Studio简介相同点差异点总结 VS Code 和 Visual Studio 哪个更好 Visual Studio Code简介 Visual Studio Code&#xff08;简称 VS Code&#xff09;是一款开源的、免费的、跨平台的、轻量级的代码编…...

FCA-数据分析理论试卷

其他参考&#xff1a; https://segmentfault.com/a/1190000043363073 https://blog.csdn.net/CSDN_WYY/article/details/137082340 Part.1&#xff1a;判断题&#xff08;总分&#xff1a;8分 得分&#xff1a;8&#xff09; 第1题 判断题 对任意事件A和B&#xff0c;必有 …...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...