69 划分字母区间
划分字母区间
- 题解1 贪心1(方法略笨,性能很差)
- 题解2 贪心2(参考标答)
给你一个字符串
s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = "eccbbbbdec"
输出:[10]
提示:
- 1 <=
s.length<= 500 s仅由小写英文字母组成
题解1 贪心1(方法略笨,性能很差)
每次都在找当前字符所在的最大下标k,可以保证该片段的最小长度n>k-begin
class Solution {
public:vector<int> partitionLabels(string s) {int sl = s.size();vector<int> ret;int k = s.rfind(s[0]);while(k >= 0 && k < sl){set<char> tmp;int end = sl-1;for(int i = 0; i <= k; i++){tmp.insert(s[i]);}// 方向:从后往前// 原则:尽量多划,不在上一个段的也先选择划开while(end > k && !tmp.count(s[end])){end --;// 如果发现有重复字符 重新找k和end// 参考题解2 有更好的找最远位置的方法(last数组)if(end > k && tmp.count(s[end])){for(int i = k+1; i <= end; i++)tmp.insert(s[i]);k = end;end = sl-1;}}ret.push_back(end);if(end < sl-1)k = s.rfind(s[end+1]);else break;}// ret开始存的是下标,但题目要求返回长度(审题)for(int i = ret.size()-1; i > 0; i--)ret[i] = ret[i] - ret[i-1];ret[0] ++;return ret;}
};

题解2 贪心2(参考标答)
class Solution {
public:vector<int> partitionLabels(string s) {int last[26];int length = s.size();for (int i = 0; i < length; i++) {// 下标从小到大:从左往右:每个字符对应的位置都是最远位置// 反之,最近位置last[s[i] - 'a'] = i;}vector<int> partition;int start = 0, end = 0;for (int i = 0; i < length; i++) {// 在子串中去寻找最大的end值end = max(end, last[s[i] - 'a']);// 重点!! 找到最大的end值后,i没有遍历到下一个子串前不会再有更大的end值if (i == end) {partition.push_back(end - start + 1);start = end + 1;}}return partition;}
};

相关文章:
69 划分字母区间
划分字母区间 题解1 贪心1(方法略笨,性能很差)题解2 贪心2(参考标答) 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。 注意,划分结果需要满足&am…...
文件上传漏洞(1), 文件上传绕过原理
文件上传漏洞 一, 前端校验上传文件 添加 Javascript 代码,然后在 form 表单中 添加 onsubmit"returb checkFile()" <script>function checkFile() {// var file document.getElementsByName(photo)[0].value;var file document.getElementByI…...
【ARM 嵌入式 C 入门及渐进 10 -- 冒泡排序 选择排序 插入排序 快速排序 归并排序 堆排序 比较介绍】
文章目录 排序算法小结排序算法C实现 排序算法小结 C语言中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。下面我们来一一介绍: 冒泡排序(Bubble Sort):冒泡排序是通过比较相邻元素的大小进行排…...
虹科 | 解决方案 | 汽车示波器 学校教学方案
虹科Pico汽车示波器是基于PC的设备,特别适用于大课堂的教学、备课以及与师生的互动交流。老师展现讲解波形数据,让学生直观形象地理解汽车的工作原理 高效备课 课前实测,采集波形数据,轻松截图与标注,制作优美的课件&…...
广播和组播(多播)
广播 概述 广播(broadcast)是指封包在计算机网络中传输时,目的地址为网络中所有设备的一种传输方式。实际上,这里所说的“所有设备”也是限定在一个范围之中,称为“广播域”。并非所有的计算机网络都支持广播…...
【Linux】gdb调试
目录 进入调试查看代码运行代码断点打断点查断点删断点从一个断点转跳至下一个断点保留断点但不会运行该断点 退出调试逐过程逐语句监视跳转至指定行运行结束当前函数 进入调试 指令:gdb 【可执行文件】: 查看代码 :l 【第几行】如果输入指…...
MySQL创建函数及其使用
MySQL创建函数及其使用 一、MySQL 创建函数二、示例 一、MySQL 创建函数 MySQL 函数是一种可重用的代码块,可以接受输入参数并返回值。你可以在 MySQL 中创建各种类型的函数,包括系统函数、用户定义函数和存储过程。在此处,我们将重点关注用…...
大数据-Storm流式框架(四)---storm容错机制
1、集群节点宕机 Nimbus服务器 硬件 单点故障?可以搭建HA jStorm搭建 nimbus的HA nimbus的信息存储到zookeeper中,只要下游没问题(进程退出)nimbus退出就不会有问题, 如果在nimbus宕机,也不能提交…...
SpringBoot项目把Mysql从5.7升级到8.0
首先你需要把之前的库导入到mysql库导入到8.0的新库中。(导入的时候会报错我是通过navcat备份恢复的) 1、项目中需要修改pom文件的依赖 mysql 和 jdbc <dependency><groupId>mysql</groupId><artifactId>mysql-connector-java&…...
RK3568-适配at24c04模块
将at24c04模块连接到开发板i2c2总线上 i2ctool查看i2c2总线上都有哪些设备 UU表示设备地址的从设备被驱动占用,卸载对应的驱动后,UU就会变成从设备地址。at24c04模块设备地址 0x50和0x51是at24c04模块i2c芯片的设备地址。这个从芯片手册上也可以得知。A0 A1 A2表示的是模块对…...
Banana Pi BPI-W3 ArmSoM-W3之RK3588-MIPI-DSI屏幕调试笔记
一. 简介 本文是基于RK3588平台,MIPI屏调试总结。 二. 环境介绍 硬件环境: ArmSoM-W3 RK3588开发板、MIPI-DSI显示屏( ArmSoM官方配件 )软件版本: OS:ArmSoM-W3 Debian11 三. MIPI屏幕调试 3.1 调试总览,调试步骤分…...
Git的远程仓库
Git的远程仓库 添加远程仓库从远程库克隆 添加远程仓库 你在本地创建了一个Git仓库后,又想在GitHub创建一个Git仓库,并且让这两个仓库进行远程同步,这样,GitHub上的仓库既可以作为备份,又可以让其他人通过该仓库来协作…...
Linux虚拟网络设备—Veth Pair
veth是Virtual Ethernet Device的缩写,是一种成对出现的Linux虚拟网络接口设备。它最常用的功能是用于将不同的Linux network namespaces 命名空间网络连接起来,让二个namespaces之间可以进行通信。我们可以简单的把veth pair理解为用一根网线࿰…...
Parcelable protocol requires the CREATOR object to be static on class com.test
对于 Parcelable 协议,确实要求 CREATOR 对象必须是静态的。这是因为在反序列化过程中,需要通过 CREATOR 对象来创建 Parcelable 对象的实例。 根据错误信息,涉及到了com.test类中的问题。通常情况下,如果一个内部类需要实现 Par…...
Python的Matplotlib库:数据可视化的利器
引言: Matplotlib是一款强大的Python库,专为数据可视化而设计。无论是绘制折线图、散点图、柱状图还是饼图,Matplotlib都能提供灵活且易于操作的绘图方法。 1. Matplotlib简介 Matplotlib是Python中最流行的绘图库之一,被广泛应…...
普通人做抖店,需要具备什么条件?一篇详解!
我是电商珠珠 抖音小店的热度一直很高,对于想开店的新手来说,不知道需要什么条件,今天我就来给大家详细的讲一下。 一、营业执照 在入驻抖音小店之前,需要准备一张营业执照。 营业执照一共有两种类型,一种为个体工…...
Django分页功能的使用和自定义分装
1. 在settings中进行注册 # drf配置 REST_FRAMEWORK {DEFAULT_AUTHENTICATION_CLASSES: (# rest_framework_jwt.authentication.JSONWebTokenAuthentication,rest_framework_simplejwt.authentication.JWTAuthentication,rest_framework.authentication.SessionAuthenticatio…...
React-hooks有哪些用法?
React Hooks 是 React 16.8 引入的一种新的特性,用于在函数组件中使用状态和其他 React 特性。下面列举了一些常见的 React Hooks 的用法: 1:useState:用于在函数组件中添加状态。: import React, { useState } from react;function MyComponent() {const [count, setCou…...
2024年CFA一级公示表,一级quicksheet(内附分享链接)
随着金融行业的迅速发展,CFA(特许金融分析师)认证成为了许多金融从业者追求的目标。2024年CFA一级公示表资料的自学,为那些渴望在金融领域取得突破的人们提供了宝贵的机会。 通过自学CFA一级公示表资料,我们可以深入了…...
【Kubernetes】 Kubernetes 了解云原生的原理
Kubernetes 了解云原生的原理 云原生是一种软件设计、实施和部署方法,旨在充分利用基于云的服务和交付模型。云原生[1]应用程序通常也使用分布式架构运行。这意味着应用程序功能被分解为多个服务,然后分布在托管环境中,而不是整合到单个服务…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
