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

力扣 hot100 Day72

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。例如,字符串 "ababcc" 能够被分为 ["abab", "cc"],但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

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

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

class Solution {
public:vector<int> partitionLabels(string s) {unordered_map <char,int> record;for(int i =0;i<s.length();i++){if(i>record[i]){record[s[i]]=i;}}vector<int>result;int start = 0;int maxn=0;for(int i=0;i<s.length();i++){maxn=max(maxn,record[s[i]]);if(i == maxn) {result.push_back(i - start + 1);start = i + 1;}}return result;}
};

第一次循环,先记录每个字母最后的位置,存在哈希表中。

第二次循环,维护一个区间,记录区间中所有字母最后位置的最大值,当i等于这个最大值时,就可以推入结果容器了。

核心目标就是,确保每个区间所有元素的末位置都包含在区间内

http://www.xdnf.cn/news/17857.html

相关文章:

  • Gradle(二)Gradle的优势、项目结构介绍
  • LINUX812 shell脚本:if else,for 判断素数,创建用户
  • Spring Boot项目中调用第三方接口
  • B站 韩顺平 笔记 (Day 16)
  • 终端安全与网络威胁防护笔记
  • 秋招笔记-8.12
  • Web 安全之互联网暴露面管理
  • 计算机网络2-3:传输方式
  • 赛灵思ZYNQ官方文档UG585自学翻译笔记:UART Controller,通用异步收发传输器控制器
  • C语言中关于普通变量和指针变量、结构体包含子结构体或包含结构体指针的一些思考
  • windows单机单卡+CIFAR-10数据集+Docker模拟训练
  • 一键设置 NTP 时区的脚本(亲测,适用于部署 K8S 的前置环境)
  • http网页部署
  • 【从零开始java学习|第四篇】IntelliJ IDEA 入门指南
  • C++方向知识汇总(四)
  • Ansible 自动化介绍
  • 如何在idea中导入外来文件
  • 基于大数据的在线教育评估系统 Python+Django+Vue.js
  • C++中template、 implicit 、explicit关键字详解
  • Rust 项目编译故障排查:从 ‘onnxruntime‘ 链接失败到 ‘#![feature]‘ 工具链不兼容错误
  • Rust:构造函数 new() 如何进行错误处理?
  • Xshell远程连接Ubuntu 24.04.2 LTS虚拟机
  • HCIP项目之OSPF综合实验
  • [Robotics_py] 路径规划算法 | 启发式函数 | A*算法
  • Linux系统编程Day13 -- 程序地址空间
  • git config的配置全局或局部仓库的参数: local, global, system
  • MaxKB+合合信息TextIn:通过API实现PDF扫描件的文档审核
  • 如何构建PHP表单页面及验证相关原理(PHP基础)
  • 自动驾驶决策算法 —— 有限状态机 FSM
  • Android 引导式访问(屏幕固定 Screen Pinning)完整指南