当前位置: 首页 > 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…...

【Hot100】LeetCode—169. 多数元素

目录 题目1- 思路2- 实现⭐169. 多数元素——题解思路 3- ACM 实现 题目 原题连接&#xff1a;169. 多数元素 1- 思路 定义两个变量 一个是 count&#xff1a;维护当前元素的出现次数一个是 ret &#xff1a;维护当前元素 思路 遍历整个数组**①如果 count 0 **&#xff…...

专科、本科、研究生是按照什么分类的?

高等教育按照阶段主要分为以下几类 一、专业学位教育 特点&#xff1a;职业导向 专业学位教育是针对特定职业领域的专业培训&#xff0c;如医学、法律、工程等&#xff0c;旨在使学生具备从事相关职业所需的专业知识和实践技能。 实践性 专业学位教育注重实践教学和职业技…...

关于实时ODS层数仓搭建的三个问题

目录 问题一&#xff1a;数据同步的实时性无法满足 问题二&#xff1a;批量数据同步计算处理效率低 问题三&#xff1a;没有稳定的数据传输管道 FineDataLink的解决方案 实战案例-销售部门与财务部门数据同步 设置ODS层实时同步任务 设置DW层增量数据同步 设置 DM 层任务汇总 关…...

微信仿H5支付是什么

仿H5支付是指一种模拟原生H5支付流程的非官方支付方式。这种支付方式通常是由第三方支付服务提供商开发和维护的&#xff0c;目的是为了绕过官方支付渠道的限制&#xff0c;如费率、审核等问题。然而&#xff0c;由于仿H5支付并非官方授权和认可的支付方式&#xff0c;其安全性…...

网络安全知识竞赛规则及流程方案

为普及网络安全知识&#xff0c;进一步提升网络安全意识&#xff0c;树立正确的网络安全观&#xff0c;营造安全健康文明的网络环境&#xff0c;在2023年国家网络安全宣传周到来之际&#xff0c;特举办网络安全知识有奖竞赛活动&#xff0c;通过竞赛活动普及国家法律法规、政策…...

赞!蚓链用数字化打造助农扶农电商平台!

助农扶农电商平台在推动农村经济发展、促进农民增收方面发挥着重要作用。蚓链数字化平台使用“防伪溯源”为农户、商户、平台、政府与消费者打造了全方位的信任链条和纽带。给各方带来众多价值&#xff01; &#xff08;一&#xff09;农户方面 1、拓宽销售渠道&#xff0c;降…...

RocketMQ延时消息

RocketMQ消息发送基本示例(推送消费者)-CSDN博客 RocketMQ消费者主动拉取消息示例-CSDN博客 RocketMQ顺序消息-CSDN博客 RocketMQ广播消息-CSDN博客 延时消息: 延时消息实现的效果就是产者调用 producer.send 方法后&#xff0c;消息会立即发送到 Broker&#xff0c;并被存…...

【C++/STL】:哈希的应用 -- 位图布隆过滤器

目录 &#x1f680;&#x1f680;前言一&#xff0c;位图1. 位图的概念2. STL库中的位图3. 位图的设计4. 位图的模拟实现5. 位图的优缺点6. 位图相关考察题⽬ 二&#xff0c;布隆过滤器1. 布隆过滤器的概念2. 布隆过滤器的实现3. 布隆过滤器删除问题4. 布隆过滤器的优缺点 点击…...

非线性面板数据实证模型及 Stata 具体操作步骤

目录 一、引言 二、文献综述 三、理论原理 四、实证模型 五、稳健性检验 六、程序代码及解释 一、引言 在当今的经济和社会研究中&#xff0c;非线性面板数据模型的应用日益广泛。这类模型能够更好地捕捉数据中的复杂关系&#xff0c;为研究者提供更深入和准确的分析结果。…...

视角 | 麻省理工学院提出出温度计校准法,专治AI大模型过度自信

在数字化浪潮的推动下&#xff0c;人工智能&#xff08;AI&#xff09;正成为塑造未来的关键力量。硅纪元视角栏目紧跟AI科技的最新发展&#xff0c;捕捉行业动态&#xff1b;提供深入的新闻解读&#xff0c;助您洞悉技术背后的逻辑&#xff1b;汇聚行业专家的见解&#xff0c;…...

昇思25天学习打卡营第XX天|CycleGAN图像风格迁移互换

CycleGAN是一种用于图像到图像翻译的生成对抗网络&#xff0c;它突破了传统域迁移模型的限制&#xff0c;无需成对样本即可学习图像在不同域间的转换。这种无监督的方法特别适用于难以获取配对数据的场景&#xff0c;例如艺术风格迁移。与需要成对训练样本的Pix2Pix不同&#x…...

嵌入式Linux学习: interrupt实验

Linux中的Interrupt&#xff08;中断&#xff09;系统是一个至关重要的组成部分&#xff0c;它负责管理和处理系统中发生的各种硬件和软件中断&#xff0c;确保系统能够正确响应外部设备的请求&#xff0c;保持系统的稳定性和可靠性。 1.中断的作用 允许设备在没有CPU干预的情…...

GPT-4o mini 来袭:开发者如何驾驭新一代AI模型?

GPT-4o Mini 来袭&#xff1a;开发者如何驾驭新一代 AI 模型&#xff1f; 引言 随着人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;越来越多的先进模型不断涌现&#xff0c;给各行各业带来了深远的影响。OpenAI 最新推出的 GPT-4o Mini 是一种创新的 AI 模型…...

校园点餐系统

1 项目介绍 1.1 摘要 在这个被海量信息淹没的数字化时代&#xff0c;互联网技术以惊人的速度迭代&#xff0c;信息的触角无处不在&#xff0c;社会的脉动随之加速。每一天&#xff0c;我们都被汹涌而至的数据浪潮包裹&#xff0c;生活在一个全方位的数字信息矩阵中。互联网的…...

进口不锈钢309S螺栓的应用优势

进口不锈钢309S螺栓因其优异的性能和广泛的应用范围而在许多行业中备受青睐。309S不锈钢是一种含硫的易切削不锈钢&#xff0c;具有良好的耐高温和耐腐蚀性能&#xff0c;使其成为高温环境下理想的选择。下面我们就来详细探讨一下进口不锈钢309S螺栓的应用优势。 一、309S不锈钢…...

C# 设计模式之工厂方法模式

总目录 前言 本文是个人基于C#学习设计模式总结的学习笔记&#xff0c;希望对你有用&#xff01; 在简单工厂模式中说到了简单工厂模式的缺点&#xff1a;简单工厂模式系统难以扩展&#xff0c;一旦添加新产品就不得不修改简单工厂方法&#xff0c;这样就会造成简单工厂的实现…...

Webpack 从入门到精通

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 一、Webpack 简介 二、Webpack 的核心概念 三、Webpack 的安装与配置 安装 Node.js 安装 Webpack 初始…...

基于VScode和C++ 实现Protobuf数据格式的通信

目录 1. Protobuf 概述1.1 定义1.2Protobuf的优势 2. Protobuf 语法3、序列号和反序列化3.1 .pb.h 头文件3.2 序列化3.3 反序列化 4、测试用例 Protobuf详细讲解链接 1. Protobuf 概述 1.1 定义 protobuf也叫protocol buffer是google 的一种数据交换的格式&#xff0c;它独立…...

linux环境openssl升级

1、下载openssl https://openssl-library.org/source/ 或者通过wget --no-check-certificate https://www.openssl.org/source/openssl-3.0.13.tar.gz 2、解压openssl tar -zxvf openssl-3.0.13.tar.gz 3、切换到解压后的目录 cd openssl-3.0.13/ 4、配置openssl安装目录…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

接口 RESTful 中的超媒体:REST 架构的灵魂驱动

在 RESTful 架构中&#xff0c;** 超媒体&#xff08;Hypermedia&#xff09;** 是一个核心概念&#xff0c;它体现了 REST 的 “表述性状态转移&#xff08;Representational State Transfer&#xff09;” 的本质&#xff0c;也是区分 “真 RESTful API” 与 “伪 RESTful AP…...

Git 命令全流程总结

以下是从初始化到版本控制、查看记录、撤回操作的 Git 命令全流程总结&#xff0c;按操作场景分类整理&#xff1a; 一、初始化与基础操作 操作命令初始化仓库git init添加所有文件到暂存区git add .提交到本地仓库git commit -m "提交描述"首次提交需配置身份git c…...

java+webstock

maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...

vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能

vxe-table vue 表格复选框多选数据&#xff0c;实现快捷键 Shift 批量选择功能 查看官网&#xff1a;https://vxetable.cn 效果 代码 通过 checkbox-config.isShift 启用批量选中,启用后按住快捷键和鼠标批量选取 <template><div><vxe-grid v-bind"gri…...

C/Python/Go示例 | Socket Programing与RPC

Socket Programming介绍 Computer networking这个领域围绕着两台电脑或者同一台电脑内的不同进程之间的数据传输和信息交流&#xff0c;会涉及到许多有意思的话题&#xff0c;诸如怎么确保对方能收到信息&#xff0c;怎么应对数据丢失、被污染或者顺序混乱&#xff0c;怎么提高…...