8.4 字符串中等 443 String Compression 467 Unique Substrings in Wraparound String

443 String Compression

在这里插入图片描述
在这里插入图片描述

注意:这里是按照顺序压缩,不忽略顺序就不能用字母表计数再还原了。
如果char num == 1 只需要压入char本身
num > 1 时还需要压入char的个数 按字符压入

class Solution {
public:vector<char> Push(vector<char>& prev , int num , char letter){prev.push_back(letter);if(num == 1){return prev;}else{for(char ch : to_string(num)){prev.push_back(ch);}}return prev;}int compress(vector<char>& chars) {//按顺序压缩字符串//主体:遍历charsint n = chars.size();int count = 0;vector<char> prev;int res = 0 , start = 0;for(int i = 0 ; i < n ; i++){if(i == n-1 || chars[i+1] != chars[i]){//触发压缩计数count = i - start + 1;prev = Push(prev , count , chars[i]);start = i+1;}}res = prev.size();chars.clear();//chars.size() == 0for(int i = 0 ; i < res ; i++){chars.push_back(prev[i]);}return res;}
};

优化:使用双指针,原地压缩,不用管多余出来的部分,因为会直接被cut掉:最后输出的字符组长度是按照return来的。

class Solution {
public:int compress(vector<char>& chars) {//双指针 write readint n = chars.size();int write = 0 , start = 0;for(int read = 0 ; read < n ; read++){if(read == n-1 || chars[read+1] != chars[read]){//触发压缩,使用writeint count = read - start + 1;//字符输入chars[write] = chars[read];write++;//个数字符串的输入if(count > 1){for(char ch : to_string(count)){chars[write++] = ch;}}start = read+1;}}return write;}
};

467 Unique Substrings in Wraparound String【全文背诵】

在这里插入图片描述
在这里插入图片描述
constraint : 限制,束缚,行为约束---->restrain

原思路:计算单个字符,找到len >1 的子字符 ,计算其除了长度为1以外的子字符串个数
但是如果重复出现abc这个子字符,代码会全部计算进去,但这是错的,只需要计算以a开头的最长的那个字符串的数就可以了,也就是题目中的unique的要求

class Solution {
public:int findSubstringInWraproundString(string s) {vector<int> count(26,0);//记录s中字母个数int res = 0;int len = 0;for(int i = 0 ; i < s.size() ; i++){//单个字符if(count[s[i] - 'a'] == 0){res ++;}count[s[i] - 'a']++;//多个字符if(i >0 &&( s[i] == s[i-1] +1 || (s[i-1] == 'z'&&s[i] == 'a'))){len++;}else{if(len > 1){res = res + len*(len+1)/2 - len;//长度>1的子字符串个数}len = 1;}}if(len > 1){res = res + len*(len+1)/2 - len;//长度>1的子字符串个数}return res;}
};

这个思路中很巧妙的是整先将s整个遍历,使用dp是用来计数以’a’+i结尾的最长字符串的最大长度
介是动态规划?!是我有眼无珠了
优点1:通过加法还原了计算长度为n的字符串的子字符串个数 1 + 2 +3…+ n = n*(n+1)/2
优点2:只取最大的长度,就完成了唯一字符串的要求,不会像原思路中将重复字符串也计算进入res中

class Solution {
public:int findSubstringInWraproundString(string s) {// dp数组,用于记录以每个字符结尾的最长子字符串的长度vector<int> dp(26, 0);int maxLen = 0; // 当前连续子字符串的长度for (int i = 0; i < s.size(); i++) {// 检查当前字符和前一个字符是否连续if (i > 0 && (s[i] == s[i - 1] + 1 || (s[i - 1] == 'z' && s[i] == 'a'))) {maxLen++;} else {maxLen = 1;}int index = s[i] - 'a';dp[index] = max(dp[index], maxLen);}// 计算结果,即所有以每个字符结尾的最长子字符串长度之和int res = 0;for (int len : dp) {res += len;}return res;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Debug-019-git reflog的两种使用场景

前情&#xff1a;最近在开发项目中对版本管理有了新的理解&#xff0c;感觉在这方面有了新的收获。同时学习了一个新的git指令&#xff1a;git reflog 实际了解之后&#xff0c;发现这个指令不是很常用&#xff0c;但是对于特定的场景的话它还是非常比较方便 这里我列举两种我…

Nextjs——国际化那些事儿

背景&#xff1a; 某一天&#xff0c;产品经理跟我说&#xff0c;我们的产品需要搞国际化 国际化的需求说白了就是把项目中的文案翻译成不同的语言&#xff0c;用户想用啥语言来浏览网页就用啥语言&#xff0c;虽然说英语是通用语言&#xff0c;但国际化了嘛&#xff0c;产品才…

算法--初阶

1、tips 1.1、set求交集 {1,2,3} & {2,3} & {1,2} {2} 其实就是位运算&#xff0c; 只有set可以这样使用&#xff0c; list没有这种用法 {1,2,3} | {2,3, 4} | {1,2} {1, 2, 3, 4} 并集 1.2、*与** * 序列(列表、元组)解包&#xff0c;如果是字典&#xff0c;那…

第一个 Flask 项目

第一个 Flask 项目 安装环境创建项目启动程序访问项目参数说明Flask对象的初始化参数app.run()参数 应用程序配置参数使用 Flask 的 config.from_object() 方法使用 Flask 的 config.from_pyfile() 方法使用 Flask 的 config.from_envvar() 方法步骤 1: 设置环境变量步骤 2: 编…

【C++学习第19天】最小生成树(对应无向图)

一、最小生成树 二、代码 1、Prim算法 #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N 510, INF 0x3f3f3f3f;int n, m; int g[N][N]; int dist[N]; bool st[N];int prim() {memset(dist, 0x3f, sizeof di…

学习分享:解析电商 API 接入的技术重难点及解决方案

在当今电商业务迅速发展的时代&#xff0c;接入电商 API 已成为许多企业提升竞争力和拓展业务的重要手段。然而&#xff0c;在这个过程中&#xff0c;往往会遇到一系列的技术重难点。本文将深入解析这些问题&#xff0c;并提供相应的解决方案。 一、电商 API 接入的技术重难点 …

c++ 初始值设定项列表(initializer_list)

引例 我们在写c代码的时候&#xff0c;多多少少会遇到这样写的&#xff1a; 如果是这样写还好说&#xff1a; 第一个是因为编译器强制匹配参数。 其他都是因为在有对应构造函数的情况下支持的隐式类型转换。 而支持的构造函数是这个&#xff1a; 如果有不懂的可以开这一篇&a…

麦田物语第十八天

系列文章目录 麦田物语第十八天 文章目录 系列文章目录一、(Editor)制作 [SceneName] Attribute 特性二、场景切换淡入淡出和动态 UI 显示一、(Editor)制作 [SceneName] Attribute 特性 在本节课我们编写Unity的特性Attribute来更好的完善我们项目,具体是什么呢,就是当…

深入理解 ReLU 激活函数及其在深度学习中的应用【激活函数、Sigmoid、Tanh】

ReLU&#xff08;Rectified Linear Unit&#xff09;激活函数 ReLU&#xff08;Rectified Linear Unit&#xff09;激活函数是一种广泛应用于神经网络中的非线性激活函数。其公式如下&#xff1a; ReLU ( x ) max ⁡ ( 0 , x ) \text{ReLU}(x) \max(0, x) ReLU(x)max(0,x) 在…

docker部署elasticsearch和Kibana

部署elasticsearch 通过下面的Docker命令即可安装单机版本的elasticsearch&#xff1a; docker run -d \--name es \-e "ES_JAVA_OPTS-Xms512m -Xmx512m" \-e "discovery.typesingle-node" \-v es-data:/usr/share/elasticsearch/data \-v es-plugins:/u…

《LeetCode热题100》---<5.①普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 第二道&#xff1a;合并区间&#xff08;中等&#xff09; 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 法一&#xff1a;贪心算法 class So…

我的256天创作纪念日

机缘 ————今天一大早收到CSDN的推送消息&#xff0c;告诉我这是我的256天创作纪念日。在这个特别的日子里&#xff0c;我回望自己踏上创作之路的点点滴滴&#xff0c;心中充满了感慨与感激。从最初的懵懂尝试到如今能够自信地分享见解&#xff0c;这段旅程不仅见证了我的成…

【教学类-73-01】20240804镂空瓶子01

背景需求&#xff1a; 瓶子里的春天呀&#xff01; - 小红书 (xiaohongshu.com)https://www.xiaohongshu.com/explore/63ef87f8000000000703acae?app_platformandroid&ignoreEngagetrue&app_version8.47.0&share_from_user_hiddentrue&xsec_sourceapp_share&…

揭秘Matplotlib等高线图:让数据‘高山流水‘间,笑点与深度并存!

1. 引言 在这个数据如山的时代&#xff0c;你是不是也曾在茫茫数海中迷失方向&#xff0c;渴望找到那片隐藏的“数据绿洲”&#xff1f;别怕&#xff0c;今天咱们就来聊聊Matplotlib这位绘图界的魔术师&#xff0c;特别是它那令人叹为观止的等高线图技能。想象一下&#xff0c…

MySQL:数据库用户

数据库用户 在关系型数据库管理系统中&#xff0c;数据库用户&#xff08;USER&#xff09;是指具有特定权限和访问权限的登录账户。每个用户都有自己的用户名和密码&#xff0c;以便系统可以通过认证来识别他们的身份。数据库用户可以登录数据库&#xff0c;在其中执行各种类…

【QT】常用控件-上

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 目录 &#x1f449;&#x1f3fb;QWidgetenabledgeometryrect制作上下左右按钮 window frame 的影响window titlewindowIcon代码示例: 通过 qrc 管理图片作为图标 windowOpacitycursor使用qrc自…

【论文笔记】SEED: A Simple and Effective 3D DETR in Point Clouds

原文链接&#xff1a;https://arxiv.org/abs/2407.10749 简介&#xff1a;基于DETR的3D点云检测器难以达到较高的性能&#xff0c;这可能有两个原因&#xff1a;&#xff08;1&#xff09;由于点云的稀疏性和分布不均匀&#xff0c;获取合适的物体查询较为困难&#xff1b;&…

基于微信小程序的微课堂笔记的设计与实现(源码+论文+部署讲解等)

博主介绍&#xff1a;✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍&#xff1a;我是程序员阿龙&#xff…

给虚拟机Ubuntu扩展硬盘且不丢数据

1.Ubuntu关机状态下先扩展&#xff0c;如扩展20GB 2.进入ubuntu&#xff0c;切换root登录&#xff0c;必须是root全选&#xff0c;否则启动不了分区工具gparted 将新的20GB创建好后&#xff0c;选择ext4,primary&#xff1b; 3.永久挂载 我的主目录在/并挂载到/dev/sda1 从图…

【C++】C++11之新的类功能与可变参数模板

目录 一、新的默认成员函数 二、新的关键字 2.1 default 2.2 detele 2.3 final和override 三、可变参数模板 3.1 定义 3.2 递归展开参数包 3.3 逗号表达式展开参数包 3.4 emplace_back 一、新的默认成员函数 在C11之前&#xff0c;默认成员函数只有六个&#xff0c;…