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

LeetCode[中等] 763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

思路 贪心算法

数组 last 存储每个字母最后出现的下标

利用滑动窗口,每次更新end指针,如果最后出现的下标 i == end,说明找到当前最大片段,则加入结果中,更新 start指针

public class Solution {public IList<int> PartitionLabels(string s) {int[] last = new int[26];for(int i = 0; i < s.Length; i++){last[s[i] - 'a'] = i;}List<int> result = new List<int>();int start = 0, end = 0;for(int i = 0; i < s.Length; i++){end = Math.Max(end, last[s[i] - 'a']);if(i == end){result.Add(end - start + 1);start = end + 1;}}return result;}
}

复杂度分析 

  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。需要遍历字符串一次记录每个字母在字符串中最后一次出现的下标,然后需要遍历字符串一次计算划分结果。

  • 空间复杂度:O(∣Σ∣),其中 Σ 是字符集,这道题中 Σ 是全部小写英语字母,∣Σ∣=26。空间复杂度主要取决于哈希表,需要使用哈希表记录每个字母在字符串中最后一次出现的下标。注意返回值不计入空间复杂度。

http://www.lryc.cn/news/452091.html

相关文章:

  • Java LeetCode每日一题
  • 数据结构--集合框架
  • Win10鼠标总是频繁自动失去焦点-非常有效-重启之后立竿见影
  • 智能涌现|迎接智能时代,算力产业重构未来
  • 关于HTML 案例_个人简历展示01
  • 【前端开发入门】css快速入门
  • java中创建不可变集合
  • D25【 python 接口自动化学习】- python 基础之判断与循环
  • HTTP1.0和HTTP1.1有什么区别
  • 卡夫卡的理解
  • 基础算法之滑动窗口--Java实现(上)--LeetCode题解:长度最小的子数组-无重复字符的子串-最大连续1的个数III-将x减到0的最小操作数
  • Linux -- 文件系统(文件在磁盘中的存储)
  • 微服务(Microservices),服务网格(Service Mesh)以及无服务器运算Serverless简单介绍
  • 【AIGC】AI时代的数据安全:使用ChatGPT时的自查要点
  • 什么是区块链桥?
  • 机器学习框架
  • 金三银四:20道前端手写面试题
  • RAC被修改权限及相关问题
  • Golang | Leetcode Golang题解之第441题排列硬币
  • 数学建模--什么是数学建模?数学建模应该怎么准备?
  • Java项目实战II基于Java+Spring Boot+MySQL的智能物流管理系统(源码+数据库+文档)
  • 【数据分享】2000—2023年我国省市县三级逐月植被覆盖度(FVC)数值(Shp/Excel格式)
  • 《Linux从小白到高手》理论篇(十一):Linux的系统环境管理
  • Qt/C++开源控件 自定义雷达控件
  • 什么是IDE(集成开发环境)?
  • 【Linux】用虚拟机配置Ubuntu 24.04.1 LTS环境
  • MacOS升级Ruby版本详解:步骤、挑战与解决方案
  • Log4j的配置与使用详解
  • docker 的目录有那些,分别存放什么东西
  • 开源模型应用落地-模型微调-语料采集-数据格式化(四)