算法思想总结:字符串

一、最长公共前缀

. - 力扣(LeetCode)

思路1:两两比较  时间复杂度mn  实现findcomon返回两两比较后的公共前缀

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//两两比较 string ret=strs[0];size_t n=strs.size();for(size_t i=0;i<n;++i)ret=findcommon(ret,strs[i]);return ret;}string findcommon(string&s1,string&s2){size_t n=min(s1.size(),s2.size());size_t i=0;for(;i<n;++i)if(s1[i]!=s2[i]) break;return s1.substr(0,i);}
};

 思路2:统一比较  时间复杂度mn

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {//统一比较size_t m=strs.size(),n=strs[0].size();for(int i=0;i<n;++i){char temp=strs[0][i];for(int j=0;j<m;++j)if(i==strs[j].size()||strs[j][i]!=temp)return strs[0].substr(0,i); }return strs[0];//可能只有一个字符串}
};

二、最长回文子串

. - 力扣(LeetCode)

解法:中心扩展算法

1、固定一个中心点,从中心点开始往两边扩展

2、要考虑奇数长度,也要考虑偶数长度

class Solution {
public:string longestPalindrome(string s) {size_t begin=0; size_t len=0;//帮助我们记录符合要求的回文子串//中心扩展算法size_t n=s.size();for(size_t i=0;i<n;++i){int left=i,right=i;//考虑奇数回文串while(left>=0&&right<n&&s[left]==s[right]) {--left;++right;}if(right-left-1>len) {begin=left+1;len=right-left-1;}//考虑偶数回文串left=i;right=i+1;//考虑奇数回文串while(left>=0&&right<n&&s[left]==s[right]) {--left;++right;}if(right-left-1>len) {begin=left+1;len=right-left-1;}}return s.substr(begin,len);}
};

三、二进制求和(字符串相加)

. - 力扣(LeetCode)

解法:模拟进位相加,但是区别就是得逢2进1 ,再将最后的结果逆序。

class Solution {
public:string addBinary(string a, string b) {//模拟进位相加,但是区别就是逢2进1size_t n1=a.size(),n2=b.size();string ret;//返回   从后往前模拟进位相加ret.reserve(n1>n2?n1+1:n2+1);//提前开空间  减少时间消耗int cur1=n1-1; int cur2=n2-1;int t=0;while(cur1>=0||cur2>=0||t) //可能会有进位的遗失{if(cur1>=0) t+=a[cur1--]-'0';if(cur2>=0) t+=b[cur2--]-'0';ret+=t%2+'0';t/=2;}reverse(ret.begin(),ret.end());//结果要反转一下return ret;}
};

 四、字符串最后一个单词的长度

字符串最后一个单词的长度_牛客题霸_牛客网

该题不能用cin>>s 因为遇到空格就会停止,所以要解决这个问题就必须用getline

而string中的rfind可以帮助我们从后往前找。

#include <iostream>
using namespace std;int main() 
{string s;getline(cin,s);//接受一个带空格的字符串cout<<s.size()-1-s.rfind(" ")<<endl;//while(cin>>s);//cout<<s.size();return 0;
}

因为该题凑巧找的是最后一个,所以也可以直接用while(cin>>s) 最后会接受到最后一个字符串

五、仅仅翻转字母

. - 力扣(LeetCode)

       非英文字符保存在原地,而英文字母翻转,所以我们可以用双指针分别指向字符串的首尾位置,如果遇到非字母的就往中间靠,当两个指针指向的都是字母的时候,交换两个指针指向的字母即可 

class Solution {
public:string reverseOnlyLetters(string s){//双指针法size_t begin=0;size_t end=s.size()-1;while(begin<end){while(begin<end&&!isalpha(s[begin])) ++begin;while(begin<end&&!isalpha(s[end]))   --end;swap(s[begin],s[end]);++begin;--end;}return s;}
};

六、验证回文串

. - 力扣(LeetCode)

       验证回文串,只需要用双指针指向首尾的位置,对非字母数字的直接跳过,当两个指针停下来的时候判断对应位置的字母是不是相同的。

class Solution {
public:bool isPalindrome(string s){//双指针往中间靠,直到相遇则回文  int length=s.size();int left=0,right=length-1;while(left<right){while(left<right&&!isalnum(s[left]))  ++left;while(left<right&&!isalnum(s[right])) --right;if(left<right)if(tolower(s[left])!=tolower(s[right]))return false;++left;--right;}return true;}
};

七、反转字符串II

. - 力扣(LeetCode)

class Solution {
public:string reverseStr(string s, int k){int n=s.size();for(int i=0;i<n;i+=2*k)reverse(s.begin()+i,s.begin()+min(i+k,n));return s;}
};

需要注意的是如果i+k超过了n,就要将他修正为n。

 八、反转字符串III

双指针,始终让两个指针指向字符串中某个单词的头和尾,然后进行反转。 

class Solution {
public:string reverseWords(string s){int head=0,tail=0;//双指针法int length=s.size();while(head<length){if(s[head]!=' '){while(tail<length&&s[tail]!=' ')++tail;reverse(s.begin()+head,s.begin()+tail);}++tail;head=tail;}return s;}
};

 九、字符串相乘(重点)

. - 力扣(LeetCode)

class Solution {
public: //从后往前不需要处理前导0string multiply(string num1, string num2){ //高位相乘补0   处理前导0  最后处理进位if(num1=="0"||num2=="0") return "0";string ret="0";//处理返回值 方便进行相加int m = num1.size(), n = num2.size();for(int i=n-1;i>=0;--i){string cur;int add=0;//处理进位for(int j=n-1;j>i;--j) //为了高位的补0cur.push_back('0');int y=num2[i]-'0';//取出这一位for(int j=m-1;j>=0;--j){int x=num1[j]-'0';int product=x*y+add;cur.push_back(product%10+'0');add=product/10;//保留进位}while(add!=0){cur.push_back(add%10+'0');add/=10;}reverse(cur.begin(),cur.end());ret= addBinary(ret, cur);}return ret;}string addBinary(string a, string b) {//模拟进位相加,但是区别就是逢2进1size_t n1=a.size(),n2=b.size();string ret;//返回   从后往前模拟进位相加ret.reserve(n1>n2?n1+1:n2+1);//提前开空间  减少时间消耗int cur1=n1-1; int cur2=n2-1;int t=0;while(cur1>=0||cur2>=0||t) //可能会有进位的遗失{if(cur1>=0) t+=a[cur1--]-'0';if(cur2>=0) t+=b[cur2--]-'0';ret+=t%10+'0';t/=10;}reverse(ret.begin(),ret.end());//结果要反转一下return ret;}
};

class Solution {
public:string multiply(string num1, string num2) {//处理相乘问题->1、先无进位相乘 2、然后相加 3、然后处理进位  4、然后处理前导0size_t m=num1.size(),n=num2.size();//准备工作,模拟进位前将两个字符串先进行逆序reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());vector<size_t> temp(m+n-1);for(size_t i=0;i<m;++i) //无进位相乘for(size_t j=0;j<n;++j) temp[i+j]+=(num1[i]-'0')*(num2[j]-'0');//无进位相乘后累加//处理进位size_t cur=0,t=0;//t是进位信息string ret;ret.reserve(m+n);//优化一下,提前开空间while(cur<m+n-1||t) {if(cur<m+n-1) t+=temp[cur++];ret+=t%10+'0';t/=10;}//3 处理前导0while(ret.size()>1&&ret.back()=='0') ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};

十、字符串中常用的一些接口

C语言相关:

C语言:字符函数和字符串函数-CSDN博客

 C++相关:

C++:String类的使用-CSDN博客

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

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

相关文章

Flutter实现局部刷新的几种方式

目录 前言 1.局部刷新的重要性 1.概念 2.重要性 2.局部刷新实现的几种方式 1.使用setState方法进行局部刷新 2.使用StatefulWidget和InheritedWidget局部刷新UI 3.ValueNotifier和ValueListenableBuilder 4.StreamBuilder 5.Provider 6.GetX 7.使用GlobalKey 前言 …

实战:功能强大齐全BBS论坛项目Echo简介

项目简介 Echo 是一套前后端不分离的开源社区系统&#xff0c;基于目前主流 Java Web 技术栈&#xff08;SpringBoot MyBatis MySQL Redis Kafka Elasticsearch Spring Security ...&#xff09;&#xff0c;并提供详细的开发文档和配套教程。包含帖子、评论、私信、系…

HarmonyOS NEXT:一次开发,多端部署

寄语 这几年特别火的uni-app实现了“一次开发&#xff0c;多端使用”&#xff0c;它这个端指的是ios、安卓、各种小程序这些&#xff0c;而HarmonyOS NEXT也提出了“一次开发&#xff0c;多端部署”&#xff0c;而它这个端指的是终端设备&#xff0c;也就是我们的手机、平板、电…

记录些MySQL题集(2)

MySQL 不使用limit的分页查询 limit问题&#xff1a;limit&#xff0c;offset递增问题。随着offset的增加&#xff0c;条数不变&#xff0c;耗时却增加了。 limit 0,10 耗时1ms limit 300000,10 耗时152ms limit 600000,10 耗时312ms 毫秒级别可能没感觉。假…

gitlab 搭建使用

1. 硬件要求 ##CPU 4 核心500用户 8 核心1000用户 ##内存 4 G内存500用户 8 G内存1000用户 2. 下载 链接 3. 安装依赖 yum -y install curl openssh-server postfix wget 4. 安装gitlab组件 yum -y localinstall gitlab-ce-15.9.3-ce.0.el7.x86_64.rpm 5. 修改配置文…

使用Python的Turtle模块绘制小猪佩奇

引言 在编程学习中&#xff0c;Turtle是一个非常有趣且实用的模块&#xff0c;尤其适合初学者。它允许用户通过控制一个可以在屏幕上移动的小海龟来绘制图形&#xff0c;从而直观地理解坐标、角度和循环等概念。本篇博客将介绍如何使用Python的Turtle模块来绘制一个可爱的卡通…

PostgreSQL日志文件配置,记录所有操作记录

为了更详细的记录PostgreSQL 的运行日志&#xff0c;我们一般需要修改PostgreSQL 默认的配置文件&#xff0c;这里整理了一些常用的配置 修改配置文件 打开 PostgreSQL 配置文件 postgresql.conf。该文件通常位于 PostgreSQL 安装目录下的 data 文件夹中。 找到并修改以下配…

IDEA实现热部署

什么是热部署&#xff1f; 热部署&#xff08;Hot Deployment&#xff09;是指在应用程序运行过程中&#xff0c;无需停止整个应用程序或重新启动服务器&#xff0c;就能够部署新的代码、资源或配置文件&#xff0c;使其立即生效。这种部署方式有助于提高开发效率和系统的可用性…

【边缘计算网关教程】4.西门子PPI协议对接

前景回顾&#xff1a;【边缘计算网关教程】3.创建第二个流程-CSDN博客 目录 1. 硬件连接 2. PLC串口参数 2.1. 打开STEP7软件 2.2. 查看通信参数 3. 网关设置 3.1. PLC连接设置 3.2. 数据点位设置 3.3. 测试 西门子 PPI 协议 适配PLC&#xff1a;S7-200 西门子S7-200 PLC…

【RHCE】综合实验0710综合实验

题目&#xff1a; 主服务器192.168.244.130 防火墙允许服务的放行&#xff1a; selinux放行 [rootlocalhost ~]# ll -Z /nfs/rhce 总用量 4 -rw-r--r--. 1 root root unconfined_u:object_r:default_t:s0 8 7月 10 16:52 index.html -rw-r--r--. 1 nobody nobody system_…

推荐一款uniapp拖动验证码插件

插件地址&#xff1a;易盾验证码 - DCloud 插件市场 具体使用方式访问插件地址自行获取

企业网三层架构

企业网三层架构&#xff1a;是一种层次化模型设计&#xff0c;旨在将复杂的网络设计分成三个层次&#xff0c;每个层次都着重于某些特定的功能&#xff0c;以提高效率和稳定性。 企业网三层架构层次&#xff1a; 接入层&#xff1a;使终端设备接入到网络中来&#xff0c;提供…

什么叫图像的双边滤波,并附利用OpenCV和MATLB实现双边滤波的代码

双边滤波&#xff08;Bilateral Filtering&#xff09;是一种在图像处理中常用的非线性滤波技术&#xff0c;主要用于去噪和保边。它在空间域和像素值域上同时进行加权&#xff0c;既考虑了像素之间的空间距离&#xff0c;也考虑了像素值之间的相似度&#xff0c;从而能够有效地…

西安明德理工学院师生莅临泰迪智能科技开展参观见习活动

为进一步深化校企合作&#xff0c;落实高校应用型人才培养。7月8日&#xff0c;西安明德理工学院与广东泰迪智能科技股份有限公司联合开展学生企业见习活动。西安明德理工学院金融产业学院副院长刘敏、金融学专业负责人张莉萍、金融学专业教师曹艳飞、赵浚妤、泰迪智能科技董事…

板级调试小助手(2)ZYNQ自定义IP核构建属于自己的DDS外设

一、前言 在上期文章中讲述了小助手的系统结构和原理。在PYNQ的框架开发中&#xff0c;我们一般可以将PL端当做PS端的一个外设&#xff0c;通过读写寄存器的方式来操作外设的功能&#xff0c;就类似于在开发ARM和DSP中操作外设一样&#xff0c;不同时的是&#xff0c;我们可以通…

【实战】Nginx+Keepalived高可用部署,后端Tomcat

目录 一、下载Tomcat安装包 二、安装Tomcat 三、 运行测试Tomcat是否安装成功 四、开放8080端口 五、Tomcat服务脚本 一、环境说明&#xff1a; 三、安装Keepalived 3.1、主机安装配置 实战目的是为了Nginx和后端的Tomcat都可以实现高可用&#xff0c;防止单节点故障的…

AWS-S3实现Minio分片上传、断点续传、秒传、分片下载、暂停下载

文章目录 前言一、功能展示上传功能点下载功能点效果展示 二、思路流程上传流程下载流程 三、代码示例四、疑问 前言 Amazon Simple Storage Service&#xff08;S3&#xff09;&#xff0c;简单存储服务&#xff0c;是一个公开的云存储服务。Web应用程序开发人员可以使用它存…

方便好用的C#.Net万能工具库Masuit.Tools

文章目录 简介开发环境安装使用特色功能示例代码1. 检验字符串是否是Email、手机号、URL、IP地址、身份证号等2.硬件监测(需要管理员权限&#xff0c;仅支持Windows&#xff0c;部分函数仅支持物理机模式)3.html的防XSS处理&#xff1a;4.整理Windows系统的内存&#xff1a;5.任…

IAR全面支持芯驰科技E3系列车规MCU产品E3119/E3118

中国上海&#xff0c;2024年7月11日 — 全球领先的嵌入式系统开发软件解决方案供应商IAR与全场景智能车芯引领者芯驰科技宣布进一步扩大合作&#xff0c;最新版IAR Embedded Workbench for Arm已全面支持芯驰科技的E3119/E3118车规级MCU产品。IAR与芯驰科技有着悠久的合作历史&…

docker私有仓库harbor安装

Harbor默认安装 下载harbor https://github.com/goharbor/harbor/releases/download/v2.11.0/harbor-offline-installer-v2.11.0.tgz 目前要求docker版本&#xff0c;docker 20.10.10-ce &#xff0c;和docker-compose 1.18.0 查看 docker-compose版本 docker-compose --ver…