力扣热门算法题 56. 合并区间,57. 插入区间,58. 最后一个单词的长度v

56. 合并区间,57. 插入区间,58. 最后一个单词的长度,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.20 可通过leetcode所有测试用例。

目录

56. 合并区间

解题思路

完整代码

Python

Java

​编辑

57. 插入区间

解题思路

完整代码

Python

Java

58. 最后一个单词的长度

解题思路

完整代码

Python

Java


56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

  1. 排序:首先按照每个区间的起始位置对所有区间进行排序,这样可以保证我们在处理区间时是按照顺序来的,便于合并。
  2. 合并区间:初始化一个空的结果数组,然后遍历排序后的区间。对于每个区间,如果结果数组为空或者当前区间的起始位置大于结果数组中最后一个区间的结束位置,就直接将当前区间添加到结果数组中。否则,如果当前区间与结果数组中最后一个区间有重叠(即当前区间的起始位置小于等于结果数组中最后一个区间的结束位置),就将结果数组中最后一个区间的结束位置更新为当前区间的结束位置和结果数组中最后一个区间的结束位置中的较大者。

完整代码

Python
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])  # Step 1: Sort the intervals by their start values
        merged = []
        for interval in intervals:
            # Step 2: If the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # Otherwise, there is overlap, so we merge the current and previous intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged
Java
public class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // Step 1: Sort the intervals by their start values
        LinkedList<int[]> merged = new LinkedList<>();
        for (int[] interval : intervals) {
            // Step 2: If the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, simply add it.
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Otherwise, there is overlap, so we merge the current and previous intervals.
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

57. 插入区间

给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。

返回插入之后的 intervals

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8][3,5],[6,7],[8,10] 重叠。

解题思路

要在已经排序且无重叠的区间列表中插入一个新的区间,并且仍然保持列表的有序性与不重叠性,可以采取以下步骤:

  1. 初始化:创建一个空的列表 result 来存储最终的区间列表。
  2. 添加新区间前的区间:遍历原始区间列表,将所有结束位置小于新区间起始位置的区间添加到 result 中,因为这些区间与新区间不重叠,并且在新区间的左侧。
  3. 合并重叠区间:继续遍历,对于每个与新区间重叠的区间(即区间的起始位置小于等于新区间的结束位置),更新新区间的起始和结束位置,使其扩展到包括当前区间。这一步可能会通过多次迭代来合并多个重叠的区间。
  4. 添加合并后的新区间:将更新后的新区间添加到 result 中。
  5. 添加新区间后的区间:最后,将所有起始位置大于新区间结束位置的区间添加到 result 中,因为这些区间与新区间不重叠,并且在新区间的右侧。

完整代码

Python
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result, i = [], 0
        # Step 2: Add all intervals before the newInterval
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        
        # Step 3: Merge all overlapping intervals to one considering newInterval
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)  # Step 4: Add the merged interval
        
        # Step 5: Add the rest of the intervals
        while i < len(intervals):
            result.append(intervals[i])
            i += 1
        
        return result
Java
public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        // Step 2: Add all intervals before the newInterval
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        // Step 3: Merge all overlapping intervals to one considering newInterval
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);  // Step 4: Add the merged interval
        
        // Step 5: Add the rest of the intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

58. 最后一个单词的长度

给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大

子字符串

示例 1:

输入:s = "Hello World"
输出:5
解释:最后一个单词是“World”,长度为5。

示例 2:

输入:s = "   fly me   to   the moon  "
输出:4
解释:最后一个单词是“moon”,长度为4。

示例 3:

输入:s = "luffy is still joyboy"
输出:6
解释:最后一个单词是长度为6的“joyboy”。

解题思路

  1. 去除尾部空格:首先,我们需要从字符串的尾部开始去除所有的空格,以确保当我们从字符串末尾开始查找单词时,不会被尾部的空格干扰。
  2. 查找最后一个单词:在去除尾部空格后,我们从字符串的最后一个字符开始向前遍历,直到遇到空格或到达字符串的开头。这个过程中遍历的字符数量就是最后一个单词的长度。

完整代码

Python
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        length = 0
        # Step 1: Trim the trailing spaces
        index = len(s) - 1
        while index >= 0 and s[index] == ' ':
            index -= 1
        
        # Step 2: Count the length of the last word
        while index >= 0 and s[index] != ' ':
            length += 1
            index -= 1
        
        return length
Java
public class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        int index = s.length() - 1;
        
        // Step 1: Trim the trailing spaces
        while (index >= 0 && s.charAt(index) == ' ') {
            index--;
        }
        
        // Step 2: Count the length of the last word
        while (index >= 0 && s.charAt(index) != ' ') {
            length++;
            index--;
        }
        
        return length;
    }
}

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

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

相关文章

【自然语言处理】NLP入门(八):1、正则表达式与Python中的实现(8):正则表达式元字符:.、[]、^、$、*、+、?、{m,n}

文章目录 一、前言二、正则表达式与Python中的实现1、字符串构造2、字符串截取3、字符串格式化输出4、字符转义符5、字符串常用函数6、字符串常用方法7、正则表达式1. .&#xff1a;表示除换行符以外的任意字符2. []&#xff1a;指定字符集3. ^ &#xff1a;匹配行首&#xff0…

Linux中,运行程序,顺便将打印信息存储在Log文件中查看

前言 如题&#xff0c;原本打算在代码中自己写一个类去管理将打印信息收集到log日志中&#xff0c;忽然想到&#xff0c;其实也可以写sh脚本 简单demo1 #!/bin/bash# 启动应用程序 test&#xff0c;并将标准输出和标准错误输出都追加到 log 文件中 ./test >> output.log…

基于Java中的SSM框架实现高校毕业设计管理系统项目【项目源码+论文说明】计算机毕业设计

基于Java中的SSM框架实现高校毕业设计管理系统演示 摘要 现代学校的教学规模逐渐增加&#xff0c;需要处理的信息量也在增加。每年毕业&#xff0c;将会有大量的毕业设计要处理。传统的毕业设计管理方法已不能满足师生的需求。教师和学生需要一个简单方便的系统来取代传统的机…

FPGA学习_Xilinx7系列FPGA基本结构

文章目录 前言一、7系列FPGA介绍1.1、芯片编号 二、基本组成单元2.1、可编程逻辑块CLB&#xff08;Configable Logic Block&#xff09;2.2、可编程输入输出单元&#xff08;IOB&#xff09;2.3、嵌入式块RAM&#xff08;Block RAM&#xff09;2.4、底层内嵌功能单元2.5、内嵌专…

【2】华为交换机如何修改Web登录密码?

0x01 问题描述 如果忘记了Web登录密码或者希望修改Web登录密码&#xff0c;用户可以通过Console口、STelnet或Tenet等方式登录交换机后设置新的Web登录密码。 使用Telnet协议存在安全风险&#xff0c;建议使用Console囗或STelnet V2登录设备 0x02 问题解决 <HUAWEI> s…

Linux信号补充——信号发送和保存

三、信号的发送与保存 3.1信号的发送 ​ 必须有操作系统来保存信号&#xff0c;因为他是管理者&#xff1b; ​ 信号给进程的task_struct发送信号&#xff0c;在task_struct中维护了一个整数signal有0-31位&#xff0c;共32个bit位&#xff1b;对于信号的管理使用的是位图结…

线段树优化dp

abc339 E - Smooth Subsequence 思路&#xff1a;我们很容想到一个 n n n方的的状态转移方程&#xff0c;即对于每个i&#xff0c;我们去枚举 1 1 1到 i − 1 i-1 i−1的状态&#xff0c;即 d p [ i ] m a x ( d p [ i ] , d p [ j ] 1 ) ; dp[i]max(dp[i],dp[j]1); dp[i]ma…

Vue字符串里的中文数字转换为阿拉伯数字

js字符串里的中文数字转换为数字 <template><view><view><view class"inpbox" ><textarea v-model"voiceMane" input"convert" ></textarea></view></view></view> </template> &…

3.7 RK3399项目开发实录-板载OpenWRT系统的使用(wulianjishu666)

STM32F103单片机从零到项目开发程序实例 下载链接&#xff1a;https://pan.baidu.com/s/1dWNskNinrMk4bxaE-jgHhQ?pwdymn3 1. OpenWRT 手册 1.1. 支持设备列表 主控板卡型号RK3568ROC-RK3568-PC/Station-P2 1.2. 登录 IP 、登录密码和 WIFI 名称 固件默认登录 IP 为 192.1…

Linux Ncurses库部分函数使用说明

目录 1. initscr&#xff08;&#xff09;函数 2. endwin&#xff08;&#xff09;函数 3. curs_set()函数 4.noecho()函数 5. keypad()函数 6. start_color()函数 7.init_pair()函数 8.getch()函数 9.move()函数 10.addch()函数 11. refresh()函数 12.inch()函数…

【Linux 进程概念】

【Linux 进程概念】 冯诺依曼体系结构冯诺依曼结构简要解释&#xff1a;你用QQ和朋友聊天时数据的流动过程 操作系统(OperatorSystem)概念设计OS的目的定位操作系统的上下层都分别是什么如何理解“管理"总结 进程基本概念描述进程-PCBtask_ struct内容 组织进程查看进程通…

序列化与反序列化介绍

文章目录 一、序列化与反序列化二、PHP反序列化漏洞成因三、JAVA反序列化 一、序列化与反序列化 在PHP语言开发层面上基本都是围绕着serialize()&#xff0c;unserialize()这两个函数。serialize()函数序列化对象后&#xff0c;可以很方便的将它传递给其他需要它的地方&#x…

由浅到深认识Java语言(9):Eclipse IDE简介

该文章Github地址&#xff1a;https://github.com/AntonyCheng/java-notes 在此介绍一下作者开源的SpringBoot项目初始化模板&#xff08;Github仓库地址&#xff1a;https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址&#xff1a;https://blog.c…

【蓝桥杯入门记录】继电器、蜂鸣器及原理图分析

一、继电器、继电器概述 &#xff08;1&#xff09;蜂鸣器原理 蜂鸣器的发声原理由振动装置和谐振装置组成&#xff0c;而蜂鸣器又分为无源他激型与有源自激型&#xff0c;蜂鸣器的发声原理为: 1、无源他激型蜂鸣器的工作发声原理是&#xff1a;方波信号输入谐振装置转换为声…

稀碎从零算法笔记Day23-LeetCode:二叉树的最大深度

题型&#xff1a;链表、二叉树的遍历 链接&#xff1a;104. 二叉树的最大深度 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上…

ES集群不识别节点SSL证书的问题处理

问题描述 在启动ES服务并试图加入其他节点上已启动的集群时&#xff0c;出现报错(原文是一大段话&#xff0c;我按语义拆成了几段)&#xff1a; [2024-03-19T16:32:02,844][WARN ][o.e.c.s.DiagnosticTrustManager] [node-2-master] failed to establish trust with server a…

高压线下垂钓很危险!高压线下防垂钓智能语音警示杆:科技守护生命

初春时节&#xff0c;气温逐渐回升&#xff0c;在这阳光明媚的日子里&#xff0c;大批“捕鱼达人”纷纷开始行动&#xff0c;河边、池塘、水库……不放过任何一个垂钓点&#xff0c;甚至在高压线下&#xff0c;依旧自信甩杆&#xff0c;殊不知高压线下垂钓&#xff0c;轻则伤、…

聚类算法之层次聚类(Hierarchical Clustering)

注意&#xff1a;本文引用自专业人工智能社区Venus AI 更多AI知识请参考原站 &#xff08;[www.aideeplearning.cn]&#xff09; 层次聚类是一种非常独特和强大的聚类方法&#xff0c;与众多其他的聚类技术相比&#xff0c;它不仅为数据集提供了一个划分&#xff0c;还给出了…

鸿蒙APP应用开发教程—超详细的项目结构说明

1. 新建项目 打开DevEco Studio, 选择 Create Project: 1.1 选择模版 Create Project - Choose Template 1.2 配置项目 Create Project - Configure Project 如果使用的是 DevEco 3.X 版本, 可以根据 Compile SDK版本选择不同的模式, 比如: 3.0.0(API 8)及更早 - 仅支持 …

【数据结构】堆和树详解堆和二叉树的实现堆的top-k问题

主页&#xff1a;醋溜马桶圈-CSDN博客 专栏&#xff1a;数据结构_醋溜马桶圈的博客-CSDN博客 gitee&#xff1a;mnxcc (mnxcc) - Gitee.com 目录 1.树概念及结构 1.1 树的概念 2.2 树的相关概念 1.3 树的表示 1.4 树在实际中的运用 2.二叉树的概念及结构 2.1 二叉树的概念…