【算法系列】字符串

目录

leetcode题目

一、最长公共前缀

二、最长回文子串

三、二进制求和

四、字符串相加

五、字符串相乘

六、仅仅反转字母

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

八、验证回文串

九、反转字符串

十、反转字符串 II

十一、反转字符串中的单词 III


leetcode题目

一、最长公共前缀

14. 最长公共前缀 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/longest-common-prefix/1.题目解析

求所有字符串的最长公共前缀

2.算法分析

解法一: 将所有字符串两两比较,求最长公共前缀

解法二: 统一比较所有字符串,当某个字符串的i位置字符不相等,或者i位置在某个字符串中越界,就停止比较, 返回结果即可

3.算法代码

解法一:

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ret = strs[0];for(int i = 1; i < strs.size(); i++)ret = find_common(ret, strs[i]);return ret;}string find_common(string s1, string s2){int i = 0;while(i < s1.size() && i < s2.size() && s1[i] == s2[i])i++;return s1.substr(0, i);}
};

解法二:

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {for(int i = 0; i < strs[0].size(); i++){char tmp = strs[0][i]; //以第一个字符串的字符为基准for(int j = 1; j < strs.size(); j++)if(i == strs[j].size() || tmp != strs[j][i])return strs[0].substr(0, i);}return strs[0];}
};

二、最长回文子串

5. 最长回文子串 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/longest-palindromic-substring/description/1.题目解析

求一个字符串的最长回文子串

2.算法分析

中心扩展算法:

1.固定一个中心点

2.从中心点开始,向两边扩展
注意: 奇数长度以及偶数长度都需要考虑

时间复杂度 O(N^2)

3.算法代码

class Solution {
public:string longestPalindrome(string s) {int begin = 0, len = 0, n = s.size();for(int i = 0; i < n; i++) //1.固定一个中心点{//2.从中心点开始,向两边扩展//2.1 奇数长度的扩展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;}//2.2 偶数长度的扩展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);}
};

三、二进制求和

1.题目解析

给两个二进制字符串,以二进制字符串形式返回他们的和

2.算法分析

定义两个下标,从字符串结尾开始向前遍历相加,t 存储相加后的结果,注意进位即可~

3.算法代码

class Solution {
public:string addBinary(string a, string b) {string ret;int cur1 = a.size()-1, cur2 = b.size()-1;int t = 0;while(cur1 >= 0 || cur2 >= 0 || t) //有可能cur1和cur2都走到了空,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;}
};

四、字符串相加

415. 字符串相加 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/add-strings/1.题目解析

以字符串形式给出两个整数,返回两整数相加之后的字符串形式

2.算法分析

本题与题目三 "二进制求和" 解法是完全一样的,大家参照题目三即可~

3.算法代码

class Solution 
{
public:string addStrings(string num1, string num2) {int cur1 = num1.size()-1, cur2 = num2.size()-1;int t = 0;string ret;while(cur1 >= 0|| cur2 >= 0 || t){if(cur1 >= 0) t += num1[cur1--] - '0';if(cur2 >= 0) t += num2[cur2--] - '0';ret += t % 10 + '0';t /= 10;}reverse(ret.begin(), ret.end());return ret;}
};

五、字符串相乘

43. 字符串相乘 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/multiply-strings/1.题目解析

给定以字符串形式给出的两个非负整数,以字符串形式返回两数的乘积

2.算法分析

解法一:模拟列竖式运算 (也就是我们在演草纸上如何算乘法,就如何写代码即可

解法二:对解法一优化 -> 无进位相乘再相加,最后处理进位

下标的规律:  当计算下标为 i 和下标为 j 的两个数相乘时,最终结果放在下标为 i+j 的位置即可

细节问题:处理前导0, 当相乘的两个数字有1个为0时,结果应该是0,但是我们的做法算出来是0000等,因此需要特殊处理

3.算法代码

class Solution {
public:string multiply(string n1, string n2) {//1.准备工作int m = n1.size(), n = n2.size();reverse(n1.begin(), n1.end()); //123->321reverse(n2.begin(), n2.end()); //456->654vector<int> tmp(m+n-1);//2.无进位相乘然后相加for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)tmp[i+j] += (n1[i] - '0') * (n2[j] - '0');//3.处理进位int cur = 0, t = 0;string ret;while(cur < m + n -1 || t != 0){if(cur < m+n-1) t += tmp[cur++];ret += t % 10 + '0';t /= 10;}//4.处理前导零while(ret.size() > 1 && ret.back() == '0') ret.pop_back(); reverse(ret.begin(), ret.end());return ret;}
};

六、仅仅反转字母

917. 仅仅反转字母 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-only-letters/1.题目解析

给定一个字符串,只将字母翻转,其他字符不变

2.算法分析

双指针策略: left从头遍历,right从尾遍历,遍历过程中,遇到非字母,left++, right--, 遇到了字母,就交换即可~

ps: 判断字符是否是字母借助库函数: isalpha

3.算法代码

class Solution {
public:string reverseOnlyLetters(string s) {size_t left = 0, right = s.size() -1;while(left < right){while(left < right && !isalpha(s[left]))left++;while(left < right && !isalpha(s[right]))right--;swap(s[left], s[right]);left++;right--;}return s;}
};

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

字符串最后一个单词的长度_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&&tqId=21224&rp=5&ru=/activity/oj&qru=/ta/huawei/question-ranking1.题目解析

字符串中的单词以空格分割,求出字符串最后一个单词的长度

2.算法分析

直接调用string类的接口rfind, 从右向左找到第一个空格位置pos即可,用字符串总长度-pos-1

3.算法代码

#include <iostream>
using namespace std;
int main() 
{string s;while(getline(cin, s)){int pos = s.rfind(' ');cout << s.size() - pos - 1;}return 0;
}

八、验证回文串

125. 验证回文串 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/valid-palindrome/1.题目解析

移除所有的非字母数字字符并且大写转小写之后,正着读和反着读是一样的,则是回文串

2.算法分析

先将所有的大写字母转为小写字母或是将所有的小写字母转为大写字母,然后双指针遍历即可!遍历过程中注意 left < right ,防止越界访问,并且不能加等号, 因为当 s= ",." 时,会出现误判~

3.算法代码

class Solution {
public:bool isPalindrome(string s) {//大写转小写for(auto& e: s)e = tolower(e);//验证回文串int left = 0, right = s.size()-1;while(left < right){while(left < right && !isalpha(s[left]) && !isdigit(s[left])) left++;while(left < right && !isalpha(s[right]) && !isdigit(s[right])) right--;if(s[left] != s[right]) return false;left++, right--;}return true;}
};

九、反转字符串

344. 反转字符串 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-string/description/1.题目解析

反转字符串

2.算法分析

双指针策略

3.算法代码

class Solution {
public:void reverseString(vector<char>& s) {int left = 0;int right = s.size()-1;while(left < right){swap(s[left], s[right]);left++;right--;}}
};

十、反转字符串 II

541. 反转字符串 II - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-string-ii/

1.题目解析

每2k个字符翻转前k个字符,如果剩余字符少于k个,则全部反转,如果剩余字符在k到2k之间,则翻转前k个字符,剩余字符保持不变~

2.算法分析

3.算法代码

class Solution {
public:string reverseStr(string s, int k) {int i= 0;while(s.begin()+2*k*i+k < s.end()){reverse(s.begin()+2*k*i, s.begin()+2*k*i+k);i++;}if(s.begin()+2*k*i < s.end())reverse(s.begin()+2*k*i, s.end()); //剩余字符<k个,全部翻转return s;}
};

十一、反转字符串中的单词 III

557. 反转字符串中的单词 III - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-words-in-a-string-iii/

1.题目解析

反转字符串中的所有单词

2.算法分析

使用string提供的find接口,start下标记录一个单词的开始位置,finish下标记录单词结束后的空格位置,用reverse函数对单词进行翻转,start置成下一个单词的开始位置(finish+1), 然后重复上述过程~

3.算法代码

class Solution {
public:string reverseWords(string s) {size_t start = 0, finish = 0;while(finish != s.size()){finish = s.find(' ', start); //从start位置开始找空格if(finish == string::npos) finish = s.size(); //最后一个单词后面没有空格,将finish置成最后一个位置reverse(s.begin() + start, s.begin() + finish);start = finish + 1; //把start置成下一个单词的第一个位置}return s;}
};

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

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

相关文章

【漏洞复现】某小日子太阳能系统DataCube3审计

漏洞描述 某小日子太阳能系统DataCube3终端测量系统 多个漏洞利用方式 免责声明 技术文章仅供参考,任何个人和组织使用网络应当遵守宪法法律,遵守公共秩序,尊重社会公德,不得利用网络从事危害国家安全、荣誉和利益,未经授权请勿利用文章中的技术资料对任何计算机系统进…

【Shell脚本】Shell编程之循环语句

目录 一.循环语句 1.for语句的结构 1.1.格式 1.2.实操案例 案例1. 案例2. 案例3. 案例4. 2.while语句的结构 2.1.格式 2.2.实操案例 案例1. 案例2. 案例3. 案例4. 3.until循环命令 3.1.格式 3.2.实操案例 案例1. 二.补充 1.常用转义符 一.循环语句 1.for…

从零入门激光SLAM(十三)——LeGo-LOAM源码超详细解析4

大家好呀&#xff0c;我是一个SLAM方向的在读博士&#xff0c;深知SLAM学习过程一路走来的坎坷&#xff0c;也十分感谢各位大佬的优质文章和源码。随着知识的越来越多&#xff0c;越来越细&#xff0c;我准备整理一个自己的激光SLAM学习笔记专栏&#xff0c;从0带大家快速上手激…

RAG 场景对Milvus Cloud向量数据库的需求

虽然向量数据库成为了检索的重要方式,但随着 RAG 应用的深入以及人们对高质量回答的需求,检索引擎依旧面临着诸多挑战。这里以一个最基础的 RAG 构建流程为例:检索器的组成包括了语料的预处理如切分、数据清洗、embedding 入库等,然后是索引的构建和管理,最后是通过 vecto…

网络编程--tcp三次握手四次挥手

1、三次握手 &#xff08;1&#xff09;三次握手的详述 首先Client端发送连接请求报文&#xff0c;Server段接受连接后回复ACK报文&#xff0c;并为这次连接分配资源。Client端接收到ACK报文后也向Server段发生ACK报文&#xff0c;并分配资源&#xff0c;这样TCP连接就建立了。…

【计算机毕业设计】springboot海洋馆预约系统的设计与实现

海洋馆预约系统采用B/S架构&#xff0c;数据库是MySQL。网站的搭建与开发采用了先进的java进行编写&#xff0c;使用了 springboot框架。该系统从两个对象&#xff1a;由管理员和用户来对系统进行设计构建。主要功能包括&#xff1a;个人信息修改&#xff0c;对用户、门票信息、…

好景盒式磁带随声听

少年时代柜子里翻出来的磁带录音机电路板 两颗芯片&#xff0c;FM芯片&#xff0c;电机驱动 CD9088CBD6650

仿“今日头条”新闻系统源码

伴随着移动互联网的热潮和自媒体时代的到来&#xff0c;因此我们看到了以“今日头条、抖音、快手、小红书”等为代表的自媒体平台的崛起。这种新的信息传播方式给广大用户带来获取资讯的便利&#xff0c;也给每个人的思想和生活带来了潜移默化的影响。随着时代发展和进步&#…

【记录】常见的前端设计系统(Design System)

解释一下设计系统的定义&#xff0c;以及在国内&#xff0c;都有那些优秀的设计系统可以学习&#xff0c;希望可以帮到大家。 什么是设计系统&#xff08;Design System)&#xff1f; 设计系统&#xff08;Design System&#xff09;是一套综合性的指导原则、组件和规则&…

C补充1—1章1.0—C程序语言设计(许宝文,李志)

二手书到了&#xff0c;好消息&#xff0c;前主人看的很认真&#xff0c;坏消息&#xff0c;只看到这页了 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊最后几题好难啊啊啊啊啊&#xff0c;再议 目录 1.1 入门 1.2 变量与算数表达式 练习1-3 //打印温度对照表 练习1-4 //摄氏-华氏温…

Linux(CentOS7)离线使用安装盘部署Telnet

[在线工具网 - 各类免费AI工具合集&#xff0c;免费pdf转word等](https://www.orcc.online) https://orcc.online 挂载镜像CentOS-7-x86_64-DVD-1810.iso到/mnt下&#xff08;其他位置也行&#xff09;&#xff0c;命令如下&#xff1a; mount /dev/sr0 /mnt 安装包默认在Pa…

设置LCD为第二终端

我一直使用xshell端&#xff0c;开发板通过串口和 xshell进行通信。 调试好LCD 驱动之后&#xff0c;可以设置 LCD 作为终端&#xff0c;也就是开发板使用自己的显示 设备作为自己的终端&#xff0c;然后接上键盘就可以直接在开发板上敲命令了&#xff0c;将 LCD 设置为终端控制…

商场活动策划有哪些套路?

商场活动策划的套路很简单就是在各种各样的特定的时间节点上&#xff0c;针对商场的目标市场进行有针对性的营销活动。 这些活动套路一共也就不超过以下20个&#xff0c;掌握了就不会再怕没活动做了&#xff0c;下面何策网给你详细讲讲&#xff1a; 1.节假日促销&#xff1a;…

如何使用Whisper音频合成模型

Whisper 是一个通用语音识别模型&#xff0c;由 OpenAI 开发。它可以识别多种语言的语音&#xff0c;并将其转换为文本。Whisper 模型采用了深度学习技术&#xff0c;具有高准确性和鲁棒性。 1、技术原理及架构 Whisper 的工作原理&#xff1a;音频被分割成 30 秒的片段&#…

R语言数据探索与分析-运用时间序列预测模型对成都市API进行预测分析

一、研究背景 “绿水青山就是金山银山&#xff0c;要让绿水青山变成金山银山”让人们深刻的意识到环境的重要性。与此同时&#xff0c;由于现代生活水平的不断提高&#xff0c;所带来的环境污染也不断增多&#xff0c;空气以及环境的污染带来了越来越多的疾病&#xff0c;深刻…

分享四种免费获取SSL的方式

SSL证书目前需要部署安装的网站很多&#xff0c;主要还是基于国内目前对证书的需求度在不断的升高&#xff0c;网站多了、服务器多了之后。网络安全问题就成为了大家不得不面对的一个重要的问题了。SSL证书的作用有很多&#xff0c;这里就不一一详述了&#xff0c;本期作品主要…

华为 Huawei 交换机 配置 Dot1q 终结子接口实现同设备 VLAN 间通信示例

组网需求 企业的不同部门拥有相同的业务&#xff0c;如上网、 VoIP 等业务&#xff0c;且各个部门中的用户位于不同的网段。目前存在不同的部门中相同的业务所属的VLAN 不相同&#xff0c;现需要实现不同VLAN中的用户相互通信。 如 图 7-7 所示&#xff0c;部门 1 和部门 2 中…

SQL——高级教程【菜鸟教程】

SQL连接 左连接&#xff1a;SQL LEFT JOIN 关键字 左表相当于主表&#xff0c;不管与右表匹不匹配都会显示所有数据 右表就只会显示和左表匹配的内容。 //例显示&#xff1a;左表的name&#xff0c;有表的总数&#xff0c;时间 SELECT Websites.name, access_log.count, acc…

yum方式删除openjdk17和openjdk18

在用虚拟机安装jdk之前其他的教程中经常会有让你java -version查看是否有安装过的jdk 我相信很多新手小白和我一样经常会遇到查出来有openjdk17和openjdk18的情况 所以这个应该怎么卸载呢,看我来操作 我用的是基于centos7的linux虚拟机 我选择用yum卸载openjdk 查看已安装…

ComfyUI中图像亮度/对比度/饱和度处理

用上面这个节点可以同时设置图片的亮度、对比度和饱和度。 【保姆级教程】一口气分享在ComfyUI中常用的30多种基本图像处理方式 更多好玩且实用AIGC工作流和节点 星球号&#xff1a;32767063 本期资料链接 往期学习资料 整理AI学习资料库