LeetCode 228 Summary Ranges 解题思路和python代码

news/2024/12/22 20:41:32/

题目
You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

“a->b” if a != b
“a” if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: [“0->2”,“4->5”,“7”]
Explanation: The ranges are:
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”
Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: [“0”,“2->4”,“6”,“8->9”]
Explanation: The ranges are:
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”

Constraints:

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
All the values of nums are unique.
nums is sorted in ascending order.

解题思路
我们从数组第一个数字开始,初始化一个变量start表示当前范围的起始值。
遍历数组中的每一个元素,如果当前元素 nums[i] 与前一个元素 nums[i-1] 不连续,那么我们将范围 [start, nums[i-1]] 添加到结果中,并更新 start 为当前元素 nums[i]。
遍历结束后,将最后一个范围添加到结果中。

python">class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:result = []if not nums:return resultstart = nums[0]for i in range(1, len(nums)):if nums[i] != nums[i-1] + 1:if start == nums[i-1]:result.append(f"{start}")else:result.append(f"{start}->{nums[i-1]}")start = nums[i]if start == nums[-1]:result.append(f"{nums[-1]}")else:result.append(f"{start}->{nums[-1]}")return result

time complexity为O(n)。
注意,使用python3。


http://www.ppmy.cn/news/1535710.html

相关文章

多模态大语言模型(MLLM)-Blip2深度解读

前言 Blip2是一个多模态大语言模型&#xff0c;因其提出时间较早&#xff08;2023年&#xff09;&#xff0c;且效果较好&#xff0c;很快成为一个标杆性工作。Blip2中提出的Q-former也成为衔接多模态和文本的重要桥梁。 Blip2发表时间是2023年&#xff0c;现在引用已经3288了…

20.1 分析pull模型在k8s中的应用,对比push模型

本节重点介绍 : push模型和pull模型监控系统对比为什么在k8s中只能用pull模型的k8s中主要组件的暴露地址说明 push模型和pull模型监控系统 对比下两种系统采用的不同采集模型&#xff0c;即push型采集和pull型采集。不同的模型在性能的考虑上是截然不同的。下面表格简单的说…

2.点位管理|前后端如何交互——帝可得后台管理系统

目录 前言点位管理菜单模块1.需求说明2.库表设计3.生成基础代码0 .使用若依代码生成器最终目标1.创建点位管理2.添加数据字典3.配置代码生成信息4.下载代码并导入项目 4.优化菜单——点位管理1.优化区域管理2.增加点位数3. 合作商4.区域管理中添加查看详情功能5.合作商添加点位…

孙子兵法-孙武

孙武与伍子胥之间的关系确实非常深厚&#xff0c;他们被称为“刎颈之交”。孙武在青年时期隐居吴国山林时&#xff0c;救助了受伤的伍子胥&#xff0c;这成为了他们友谊的起点。孙武的才华和抱负得到了伍子胥的认可&#xff0c;伍子胥将孙武推荐给吴王阖闾&#xff0c;最终孙武…

SQL Server中关于个性化需求批量删除表的做法

在实际开发中&#xff0c;我们常常会遇到需要批量删除表&#xff0c;且具有共同特征的情况&#xff0c;例如&#xff1a;找出表名中数字结尾的表之类的&#xff0c;本文我将以3中类似情况为例&#xff0c;来示范并解说此类需求如何完成&#xff1a; 第一种&#xff0c;批量删除…

设计模式、系统设计 record part03

创建者模式 1.创建、使用&#xff0c;二者分离 2.降低&#xff0c;耦合度 3.使用者&#xff0c;不用关注&#xff0c;对象的创建细节 工厂模式&#xff1a; 1.对象由工厂生产&#xff0c; 2.使用者与工厂交流&#xff0c;不与对象直接打交道&#xff0c; 3.在工厂里直接更换对象…

【ubuntu】Ubuntu20.04安装中文百度输入法

1.download 百度Linux输入法-支持全拼、双拼、五笔 2.unzip unzip Ubuntu_Deepin-fcitx-baidupinyin-64.zip 3.setting 3.1 setting fcitx sudo apt install aptitude sudo aptitude install fcitx-bin fcitx-table fcitx-config-gtk fcitx-frontend-all sudo aptitude in…

电子信息类专业技术学习及比赛路线总结(大一到大三)

本文主要是总结到目前为止电子信息类的专业技能、比赛路线&#xff0c;以后会持续更新&#xff0c;希望能为那些热爱电子技术或渴望学习课本之外知识的小伙伴们提供帮助&#xff0c;参加学科竞赛和找工作必备。&#xff08;毕竟很多课本上的内容都没什么用 &#xff09; 1.单片…