【每日挠头算法题(2)】压缩字符串|仅执行一次字符串交换能否使两个字符串相等
文章目录
- 一、压缩字符串
- 思路
- 二、仅执行一次字符串交换能否使两个字符串相等
- 思路1:计数法
- 思路2:模拟法
- 总结
一、压缩字符串
点我直达~
思路
使用双指针法
大致过程如下:
- 使用双指针,分别读(read),写(write)指针,读指针不断向后走,当read指针走到最后位置处时,或read和read的下一个位置与当前位置不相等时,说明该read指针走到了某一串相同子串的最后位置处。
- 此时write指针开始记录具体的字符,给定一个left指针记录当前位置,此时每一个子串的长度都是
read - left +1
- 使用短除法将子串的长度记录下来,再进行逆置即可。
具体操作如下:
- 1.给定两个指针write 和 left
(left指针记录每一个子串的开始位置)
,分别指向第一个元素的位置。 - 2.使用read指针,遍历字符串,当read遇到其后面一个字符与当前字符不等,或者read走到末尾时,此时将write指针记录当前子串的字符,以及长度,那就让write一边记录一边往后走。
- 3.当write指针开始记录子串的长度时,给一个下标
begin
,这个begin就是记录子串的长度的起始位置,比如一个串的长度为:123,需要记录到chars数组的是[“1”,“2”,“3”],begin记录着"1"下标的位置。 - 4.使用短除法将某一个串的长度的每一位记录下来,然后逆置,逆置的开始是begin,结尾是write。
- 5.因为write总是向后走,知道走到记录完所有的字符以及每一个相同的字符串的长度,则最终返回write的长度即可
具体代码如下:
class Solution {
public:int compress(vector<char>& chars) {int write = 0,left = 0;for(int read = 0;read<chars.size();++read){if(read == chars.size()-1 ||chars[read]!=chars[read+1]){ chars[write++] = chars[read];//存储字符int begin = write; // 逆置的左下标int n = read - left + 1 ; if(n>1){while(n){chars[write++] = (n%10) + '0';n/=10;}//逆置的右下标是writereverse(&chars[begin],&chars[write]);}left = read+1;}}return write;}
};
时间复杂度:O(n),空间复杂度O(1)
二、仅执行一次字符串交换能否使两个字符串相等
点我直达~
思路1:计数法
- 情况1:如果两个字符串的长度不同,那么不管怎么交换一定不等,返回false
- 情况2:如果两个字符串的长度相同:
-
- 情况1:如果不相同的字符超过两个,或者不相同的字符只有一个,那么两个字符串不管怎么交换字符一定不等,返回false
-
- 情况2:如果不相同的字符恰好为两个,此时有两种方法解决:
-
-
- 1.交换这两个不相同的字符的位置,如果交换后s1 == s2,返回true,否则false。
-
-
-
- 2.判断 s1[i] == s2[j] ,s1[j] == s2[i]是否满足即可。
-
具体请看下面代码:
class Solution {
public:bool areAlmostEqual(string s1, string s2){//1.相等,trueif(s1 == s2)return true;//2.长度不等,falseif(s1.size() != s2.size())return false;//3.遍历s1和s2,如果发现有两个以上字母不同,不管怎么交换都不等 vector<int> v1; // 两个下标int count = 0;//计算s1和s2有几个不等的字母for(int i = 0;i<s1.size();++i){if(s1[i]!=s2[i]){++count;v1.push_back(i);}}//如果不是只有两个字母不同,不管怎么交换一定不等。if(count !=2)return false;return s1[v1[0]] == s2[v1[1]] && s1[v1[1]] == s2[v1[0]] ;//下面的操作也可//swap(s2[v1[0]],s2[v1[1]]);// if(s1 == s2)// return true;// return false;}
};
思路2:模拟法
模拟法整体思路与计数法大致相同
给定两个初始值pos1 ,pos2均为 -1,记录两个字符串不同的字符的下标。
- 如果不同位置超过两个或者只有一个,返回false
- 如果不同位置为两个或者没有不同位置,返回true
具体请看下面代码:
class Solution {
public:bool areAlmostEqual(string s1, string s2){int n = s1.size(),pos1 = -1,pos2 = -1;for(int i = 0;i<n;++i){if(s1[i] == s2[i])continue;if(pos1 == -1)pos1 = i;else if(pos2 == -1)pos2 = i;//该情况是超过两个不同的字符elsereturn false;}//该情况是没有不同的字符if(pos1 == -1)return true;//该情况是只有一个不同的字符if(pos2 == -1)return false;//该情况是正常情况return s1[pos1] == s2[pos2] && s1[pos2] == s2[pos1];}
};
总结
通过写今天的两道题,重新认识了双指针法的厉害的地方,哪哪都可以考虑双指针法。
比如:排序,字符串逆置,字符串压缩等等,有关字符串的题都可以考虑一下双指针法
还有只要涉及到两个字符串中的两个字符的问题,都可以进行下标的模拟,或者计数法来实现。
相关文章:

【每日挠头算法题(2)】压缩字符串|仅执行一次字符串交换能否使两个字符串相等
文章目录 一、压缩字符串思路 二、仅执行一次字符串交换能否使两个字符串相等思路1:计数法思路2:模拟法 总结 一、压缩字符串 点我直达~ 思路 使用双指针法 大致过程如下: 使用双指针,分别读(read)&…...

V4L2框架解析
和你一起终身学习,这里是程序员Android 经典好文推荐,通过阅读本文,您将收获以下知识点: 一、概览二、流程简介三、关键结构体四、模块初始化五、处理用户空间请求 一、概览 相机驱动层位于HAL Moudle与硬件层之间,借助linux内核驱…...

Trie树模板与应用
文章和代码已经归档至【Github仓库:https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。 文章目录 Trie树(字典树)基本思想例题 Trie字符串统计code关于idx的理解 模板总结应用 最大异或对分…...
【华为OD统一考试B卷 | 200分】跳格子游戏(C++ Java JavaScript Python)
文章目录 题目描述输入描述输出描述用例C++javajavaScriptpython题目描述 地上共有N个格子,你需要跳完地上所有的格子,但是格子间是有强依赖关系的,跳完前一个格子后,后续的格子才会被开启,格子间的依赖关系由多组steps数组给出,steps[0]表示前一个格子,steps[1]表示st…...
该选哪个语言进修呢?
前言: 如今,计算机编程已经成为了许多工作领域中的必备技能。但是,现在的计算机语言有很多,这可能会让我们感到困惑:我应该从哪个语言开始呢?在这篇博客中,我们将详细分析当前流行的一些计算机…...

数据库实验三 数据查询一
任务描述 本关任务:按条件查询数据表的所有字段 为了完成本关任务,你需要掌握: 如何查询数据表的所有字段 相关知识 查询数据表 命令格式: select * from 数据表 where 查询条件 任务要求 打开province数据库 第一题 查询街…...
【Python百日进阶-Web开发-Peewee】Day244 - 数据库 Postgresql、CockroachDB
文章目录 六、数据库6.1 初始化数据库6.2 使用 Postgresql6.2.1 隔离级别 6.3 使用 CockroachDB 六、数据库 http://docs.peewee-orm.com/en/latest/peewee/database.html PeeweeDatabase对象表示与数据库的连接。该类Database使用打开数据库连接所需的所有信息进行实例化&…...

Vue 中的列表渲染
Vue 中的列表渲染 在 Vue 中,列表渲染是非常常见的操作。它允许我们将一个数组中的数据渲染为一个列表,从而实现数据的展示和交互。在本文中,我们将探讨 Vue 中的列表渲染的基本原理和用法,并给出一些实例代码来帮助读者更好地理…...
java 中的关键字
1. 面向对象编程(OOP) - 把程序中的实体看做对象,而不是过程或函数。OOP有3个基本特征:封装,继承和多态。 2. 类(Class) - 一个用于描述对象属性和方法的蓝图。 3. 对象(Object) - 类的实例化,也就是一个具体的实体。 4. 方法(Met…...
python序列化和结构化数据详解
序列化和结构化数据是计算机程序中非常重要的概念,它们的原理和应用在许多应用程序中都是必不可少的。Python作为一种高级编程语言,在序列化和结构化数据方面提供了很多优秀的解决方案。在本文中,我们将详细介绍Python中序列化和结构化数据的…...

PoseiSwap的趋势性如何体现?
DEX 代表了一种先进的意识形态,相对于 CEX 其更强调无许可、去中心化以及公开透明。然而随着 DeFi 赛道逐渐从 2021 年年底的高峰逐渐转向低谷,DEX 整体的交易量、TVL等数据指标也开始呈现下滑的趋势,DEX 正在面临发展的新瓶颈期。 在这样的背…...

西南交通大学智能监测 培训课程练习4
2023.056.07和09培训 项目实战 目录 一、infracore(基础核心层) 1.1database 1.2config 1.3util 二、业务领域模块 2.1structure模块 2.1.1domain层 2.1.2application层 2.1.3adapter层 2.2sensor模块 2.2.1domian层 2.2.2application层 2.2.…...

设备树的引入及简明教程
首先说明,设备树不可能用来写驱动。 设备树只是用来给内核里的驱动程序,指定硬件的信息。比如LED驱动,在内核的驱动程序里去操作寄存器,但是操作哪一个引脚?这由设备树指定。 需要编写设备树文件(dts: device tree s…...

MM32F3273G8P火龙果开发板MindSDK开发教程12 -获取msa311加速器的敲击事件
MM32F3273G8P火龙果开发板MindSDK开发教程12 -获取msa311加速器的敲击事件 1、功能描述 msa311可以识别单击、双击事件,类似手机上的点击返回,双击截屏功能。 单击,双击都能产生中断事件。 中断事件产生后,从对应的状态寄存器读…...
Maven聚合
在实际的开发过程中,我们所接触的项目一般都由多个模块组成。在构建项目时,如果每次都按模块一个一个地进行构建会十分得麻烦,Maven 的聚合功能很好的解决了这个问题。 聚合 使用 Maven 聚合功能对项目进行构建时,需要在该项目中…...

[架构之路-211]- 需求- 软架构前的需求理解:ADMEMS标准化、有序化、结构化、层次化需求矩阵 =》需求框架
目录 前言: 一、什么是ADMES: 首先,需求是分层次的: 其次,需求是有结构的,有维度的 再次,不同层次需求、不同维度需求之间可以相互转化(难点、经验积累) 最终,标准…...

基于前推回代法的连续潮流计算研究【IEEE33节点】(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

【双向链表】
双向链表 带头双向循环链表的实现1. 函数的声明2. 函数的实现3. 主函数测试 带头双向循环链表的实现 今天我们来实现一下带头双向循环链表,顾名思义,带头就是有哨兵位,哨兵位不是链表的头,它是连接头节点的一个节点,方…...

POSTGRESQL NEON - Serverless 式的POSTGRESQL 数据库的独特技能 分支数据
开头还是介绍一下群,如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题,有需求都可以加群群内有各大数据库行业大咖,CTO,可以解决你的问题。加群请联系 liuaustin3 ,在新加的朋友会分到2群(共…...

数据分布——长尾分布的处理
前言 长尾分布在分类任务中会提到这个名,这是因为长尾分布这个现象问题会导致在训练过程中会出现出错率高的问题,影响了实验结果。 这里要说的是,长尾分布是一种现象,有的地方说是一种理论或定律,我感觉这样说不太确切࿰…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...