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

【每日挠头算法题(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&#xff1a;计数法思路2&#xff1a;模拟法 总结 一、压缩字符串 点我直达~ 思路 使用双指针法 大致过程如下&#xff1a; 使用双指针&#xff0c;分别读&#xff08;read&#xff09;&…...

V4L2框架解析

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

Trie树模板与应用

文章和代码已经归档至【Github仓库&#xff1a;https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。 文章目录 Trie树&#xff08;字典树&#xff09;基本思想例题 Trie字符串统计code关于idx的理解 模板总结应用 最大异或对分…...

【华为OD统一考试B卷 | 200分】跳格子游戏(C++ Java JavaScript Python)

文章目录 题目描述输入描述输出描述用例C++javajavaScriptpython题目描述 地上共有N个格子,你需要跳完地上所有的格子,但是格子间是有强依赖关系的,跳完前一个格子后,后续的格子才会被开启,格子间的依赖关系由多组steps数组给出,steps[0]表示前一个格子,steps[1]表示st…...

该选哪个语言进修呢?

前言&#xff1a; 如今&#xff0c;计算机编程已经成为了许多工作领域中的必备技能。但是&#xff0c;现在的计算机语言有很多&#xff0c;这可能会让我们感到困惑&#xff1a;我应该从哪个语言开始呢&#xff1f;在这篇博客中&#xff0c;我们将详细分析当前流行的一些计算机…...

数据库实验三 数据查询一

任务描述 本关任务&#xff1a;按条件查询数据表的所有字段 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 如何查询数据表的所有字段 相关知识 查询数据表 命令格式&#xff1a; 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 中&#xff0c;列表渲染是非常常见的操作。它允许我们将一个数组中的数据渲染为一个列表&#xff0c;从而实现数据的展示和交互。在本文中&#xff0c;我们将探讨 Vue 中的列表渲染的基本原理和用法&#xff0c;并给出一些实例代码来帮助读者更好地理…...

java 中的关键字

1. 面向对象编程(OOP) - 把程序中的实体看做对象&#xff0c;而不是过程或函数。OOP有3个基本特征&#xff1a;封装&#xff0c;继承和多态。 2. 类(Class) - 一个用于描述对象属性和方法的蓝图。 3. 对象(Object) - 类的实例化&#xff0c;也就是一个具体的实体。 4. 方法(Met…...

python序列化和结构化数据详解

序列化和结构化数据是计算机程序中非常重要的概念&#xff0c;它们的原理和应用在许多应用程序中都是必不可少的。Python作为一种高级编程语言&#xff0c;在序列化和结构化数据方面提供了很多优秀的解决方案。在本文中&#xff0c;我们将详细介绍Python中序列化和结构化数据的…...

PoseiSwap的趋势性如何体现?

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

西南交通大学智能监测 培训课程练习4

2023.056.07和09培训 项目实战 目录 一、infracore&#xff08;基础核心层&#xff09; 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.…...

设备树的引入及简明教程

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

MM32F3273G8P火龙果开发板MindSDK开发教程12 -获取msa311加速器的敲击事件

MM32F3273G8P火龙果开发板MindSDK开发教程12 -获取msa311加速器的敲击事件 1、功能描述 msa311可以识别单击、双击事件&#xff0c;类似手机上的点击返回&#xff0c;双击截屏功能。 单击&#xff0c;双击都能产生中断事件。 中断事件产生后&#xff0c;从对应的状态寄存器读…...

Maven聚合

在实际的开发过程中&#xff0c;我们所接触的项目一般都由多个模块组成。在构建项目时&#xff0c;如果每次都按模块一个一个地进行构建会十分得麻烦&#xff0c;Maven 的聚合功能很好的解决了这个问题。 聚合 使用 Maven 聚合功能对项目进行构建时&#xff0c;需要在该项目中…...

[架构之路-211]- 需求- 软架构前的需求理解:ADMEMS标准化、有序化、结构化、层次化需求矩阵 =》需求框架

目录 前言&#xff1a; 一、什么是ADMES: 首先&#xff0c;需求是分层次的&#xff1a; 其次&#xff0c;需求是有结构的&#xff0c;有维度的 再次&#xff0c;不同层次需求、不同维度需求之间可以相互转化&#xff08;难点、经验积累&#xff09; 最终&#xff0c;标准…...

基于前推回代法的连续潮流计算研究【IEEE33节点】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【双向链表】

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

POSTGRESQL NEON - Serverless 式的POSTGRESQL 数据库的独特技能 分支数据

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…...

数据分布——长尾分布的处理

前言 长尾分布在分类任务中会提到这个名,这是因为长尾分布这个现象问题会导致在训练过程中会出现出错率高的问题&#xff0c;影响了实验结果。 这里要说的是&#xff0c;长尾分布是一种现象&#xff0c;有的地方说是一种理论或定律&#xff0c;我感觉这样说不太确切&#xff0…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...