算法:字符串相关

目录

题目一:最长公共前缀

题目二:最长回文子串

题目三:二进制求和

题目四:字符串相乘


题目一:最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀

如果不存在公共前缀,返回空字符串 ""

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

解法一:两两比较

解法一就是两两比较的策略,先进行前两个字符串的比较,比较完后,将前两个字符串的公共前缀再与第三个字符串比较,从而得到前三个字符串的公共前缀,以此类推

代码如下:

class Solution 
{
public:string findCommon(string& s1, string& s2){int i = 0;//i有可能会出现越界的情况,所以i小于s1s2长度时再循环判断while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])i++;return s1.substr(0, i);}string longestCommonPrefix(vector<string>& strs) {int n = strs.size();//same字符串就是存储最长公共前缀的字符串string same = strs[0];for(int i = 1; i < n; i++)same = findCommon(same, strs[i]);return same;}
};

解法二:统一比较

统一比较也就是一次性将所有字符串的同一位置作比较,判断是否该位置相同,直到出现不同的字符时为止

这里会出现越界的情况,出现越界说明某一个字符串已经结束了,那么也就可以终止比较了

代码如下:

class Solution 
{
public:string longestCommonPrefix(vector<string>& strs) {int i = 0;//以第一个字符串为基准,与其他所有字符串做比较for(i = 0; i < strs[0].size(); i++){//ch表示第一个字符串当前循环到的字符char ch = strs[0][i];//循环strs中其余的字符串,其余字符串的i位置字符与ch做比较for(int j = 1; j < strs.size(); j++){  //如果i大于当前字符串的长度,说明当前字符串已经没有元素了if(i > strs[j].size() || strs[j][i] != ch)return strs[0].substr(0, i);}}return strs[0];}
};

题目二:最长回文子串

给你一个字符串 s,找到 s 中最长的 回文子串

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

普通的暴力枚举算法,设置两个指针,一个 i 一个 j ,固定 i ,向后移动 j ,每次移动 j 都需要判断 i 和 j 之间的字符串是否是回文子串,此时移动 j 和判断 i、j 之间是否是回文子串,这里的时间复杂度是O(N^2),又因为外面嵌套着一层 i ,用于遍历整个字符串,所以整个暴力枚举的时间复杂度是非常高的,达到了O(N^3),下面看优化后的中心扩展算法:

解法:中心扩展算法

中心扩展算法就是:

①固定一个中心点
②从中心点开始,向两边扩展(奇数和偶数长度都需要考虑到)

也就是每次固定一个中心点 i,每次向 i 的左边和右边扩展,判断是否是回文串,这种算法遍历 i 时间复杂度是O(N),嵌套的向 i 的左边和右边扩展,时间复杂度也是O(N),所以最终是O(N^2),会比上面所说的暴力解法,优化非常多

需要注意的就是中心扩展算法的第二点,需要考虑奇数和偶数,因为奇数是将left和right指针,从 i 位置开始一左一右移动,而偶数需要left在 i 位置,right在 i + 1位置,然后再一左一右移动

需要注意代码中的长度是 right - left - 1,因为当前 left 和 right 指向元素如果相同,需要将left--,right++,此时如果不相同就退出循环,所以 left 和 right 都比回文串多移动了一个位置,所以长度才是 right - left - 1 计算的,具体见下图:

如上图所示,left和right指向当前时退出循环,所以回文子串aa的长度就是:
right - left - 1 = 3 - 0 - 1 = 2


代码如下:

class Solution 
{
public:string longestPalindrome(string s) {if(s.size() == 1) return s;int n = s.size(), begin = 0, size = 0;for(int i = 0; i < n; i++){//先做奇数长度的扩展int left = i, right = i;//left和right符合条件,且指向元素相等再进入循环while(left >= 0 && right < n && s[left] == s[right]){--left;++right;}//如果长度更大,更新begin与sizeif((right - left - 1) > size){size = right - left - 1;begin = left + 1;}//再做偶数长度的扩展left = i, right = i + 1;//left和right符合条件,且指向元素相等再进入循环while(left >= 0 && right < n && s[left] == s[right]){--left;++right;}//如果长度更大,更新begin与sizeif((right - left - 1) > size){size = right - left - 1;begin = left + 1;}            }return s.substr(begin, size);}
};

题目三:二进制求和

给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。

示例 1:

输入:a = "11", b = "1"
输出:"100"

示例 2:

输入:a = "1010", b = "1011"
输出:"10101"

这道题就是计算高精度的加法,进行一个模拟运算,模拟列竖式计算的过程

需要设定两个指针cur1和cur2,分别指向两个字符串,再设定一个变量t ,表示进位

代码如下:

class Solution 
{
public:string addBinary(string a, string b) {//t表示相加后的进位int t = 0;string ret;int cur1 = a.size()-1, cur2 = b.size()-1;//cur1或cur2 >= 0表示字符串没遍历完,t>0表示还剩一个进位while(cur1 >= 0 || cur2 >= 0 || t){if(cur1 >= 0) t += a[cur1--] - '0';  if(cur2 >= 0) t += b[cur2--] - '0';ret += to_string(t % 2);t /= 2;}//从后向前加的,刚好反过来了,需要逆置reverse(ret.begin(), ret.end());return ret;}
};

题目四:字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

解法一:模拟竖式运算

就是数学上,乘法列的竖式,这是最容易想到的方法

如下所示:

我们可以理解为,下面的456的每一位分别乘上面的123,再相加,有三点细节:

①高位相乘需要补0,因为738和615相加时错了一位,可以理解为 738 + 6150
②处理前导0,可能出现123 × 0 的情况,这时答案是000,需要处理一下
③注意计算结果的顺序,因为计算时是逆序计算的,乘法都是从最后一位开始计算的

但是这种方法并不好写代码,我们需要借助这种方法来优化一下

解法二:对解法一优化

无进位相乘再相加,最后一步再处理进位:

即相乘时不管是多少,都不进位,最后加完后再进位

同样,在开始计算时,先逆序,这里由于相乘后可能是两位数,所以就不能使用string表示了,可以采用一个数组存储

由于逆序了,所以123对应的的下标是2,1,0,456对应的下标也是2,1,0

有一个非常好用的规律:i 和 j 下标的数相乘,结果恰好放在数组第 i + j 位上

①定义一个长度是 m + n - 1 数组tmp(m和n对应两个相乘数字的长度)
正在相乘的两个数字的下标分别是 i,j,将计算的结果放在数组的第 i + j 位上
②最后加完以后,需要处理进位
③处理前置0

代码如下:

class Solution 
{
public:string multiply(string num1, string num2) {//先逆序两个字符串reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//定义一个数组tmpint m = num1.size(), n = num2.size();vector<int> tmp(m + n - 1);//无进位相乘然后相加for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');//处理进位string ret;int t = 0, cur = 0;while(cur < m + n - 1 || t != 0){if(cur < m + n - 1) t += tmp[cur++];ret += to_string(t % 10);t /= 10;}if(t) ret += to_string(t);//处理前置0while(ret.back() == '0' && ret.size() > 1) ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

字符串相关的题目到此结束

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

阶乘尾数00

题目链接 阶乘尾数 题目描述 注意点 算出 n 阶乘有多少个尾随零 解答思路 n阶乘有多少个尾随零取决于阶乘中有多少个2 * 5的组合&#xff0c;其中阶乘中2的数量一定多于5的数量&#xff0c;所以关键是要找到由多少个质因子5n的阶乘中质因子5的数量等于不断将n除以5&#x…

STM32快速搭建项目框架

注&#xff1a;编写本博客的原因&#xff0c;学习期间基于复习之前知识点的需要&#xff0c;故撰写本教程&#xff0c;即是复习前面的知识点也是作为博客的补充 1.0 文件夹的创建 创建一个STM32项目为模版工程&#xff0c;问价夹下分别包含4个子文件夹&#xff0c;一个是Librar…

【C++项目】从零实现一个在线编译器

前言 身为一名程序员&#xff0c;想必大家都有接触过像leetcode这样的刷题网站&#xff0c;不知你们在刷题的过程中是否思考过一个问题&#xff1a;它们是如何实现在线编译运行的功能。如果你对此感到好奇&#xff0c;那么本文将一步步带你来实现一个简易在线编译器。 项目概…

深入了解线程锁的使用及锁的本质

文章目录 线程锁的本质局部锁的使用 锁的封装及演示线程饥饿问题 线程加锁本质可重入和线程安全死锁问题 根据前面内容的概述, 上述我们已经知道了在linux下关于线程封装和线程互斥,锁的相关的概念, 下面就来介绍一下关于线程锁的一些其他概念. 线程锁的本质 当这个锁是全局的…

Vue使用Echarts(入门级)

最终效果&#xff1a; npm install echarts --save // 先安装echarts<template><!-- 创建一个dom区域用于挂载echarts图表 --><div id"chart" style"width: 600px;height:500px;"/> </template> <script> import * as ech…

WPF依赖附加属性

依赖附加属性的定义 基本过程&#xff1a;声明、注册、包装 依赖附加属性必须在依赖对象&#xff0c;附加属性不一定&#xff0c;关注的是被附加的对象是否是依赖对象 快捷方式&#xff1a;propa tab 关键字&#xff1a;RegisterAttached // 方法封装 public static int …

4.MkDocs样式

学习 Admonitions(警告) - Material for MkDocs (wdk-docs.github.io) 提示 - Material for MkDocs 中文文档 (llango.com) Buttons(按钮) - Material for MkDocs (wdk-docs.github.io) 建议去看这些网站&#xff0c;更为详细。 常用功能 便利贴 ​​ 开启 markdown_ex…

FL Studio 24.1.1.4234 (Windows) / 24.1.1.3884 (Mac OS X)

FL Studio 24.1.1.4234 (Windows) / 24.1.1.3884 (Mac OS X) 主页多媒体音频编辑FL Studio 24.1.1.4234 (Windows) / 24.1.1.3884... FL Studio 图标 FL Studio&#xff08;前身为 FruityLoops&#xff09;是一款功能强大的音乐制作环境或数字音频工作站&#xff08;DAW&#x…

基于Java的科大讯飞大模型API调用实现

写在前面&#xff1a;因为现在自己实习的公司新拓展的一个业务是结合AI的低代码平台&#xff0c;我负责后端的开发&#xff0c;之前一直都是直接使用gpt或者文心一言等ui界面来直接使用大模型&#xff0c;从来没有自己调接口过&#xff0c;所以本文记录一下自己第一次使用大模型…

【密码学】分组密码概述

一、分组密码的定义 分组密码和流密码都是对称密码体制。 流密码&#xff1a;是将明文视为连续的比特流&#xff0c;对每个比特或字节进行实时加密&#xff0c;而不将其分割成固定的块。流密码适用于加密实时数据流&#xff0c;如网络通信。分组密码&#xff1a;是将明文数据…

【无聊找点事干】局域网内把window 搭建为代理服务器上网

场景描述 同一局域网内&#xff0c;server 2012可以上网&#xff0c;window 10无法上网。现在将电脑server 2012设置为代理服务器&#xff0c;使得window 10可以通过server 2012访问公网。 server 2012&#xff1a;服务端 安装代理服务器软件&#xff1a;CCProxy点击‘设置’…

『大模型笔记』GraphRAG:利用复杂信息进行发现的新方法!

GraphRAG:利用复杂信息进行发现的新方法! 文章目录 一. GraphRAG:利用复杂信息进行发现的新方法!1. 将RAG应用于私人数据集2. 整个数据集的推理3. 创建LLM生成的知识图谱4. 结果指标5. 下一步二. 参考文献微软官方推文:https://www.microsoft.com/en-us/research/blog/gra…

综合安全防护

题目 1,DMZ区内的服务器,办公区仅能在办公时间内(9:00-18:00)可以访问,生产区的设备全天可以访问. 2,生产区不允许访问互联网,办公区和游客区允许访问互联网 3,办公区设备10.0.2.10不允许访问DMz区的FTP服务器和HTTP服务器,仅能ping通10.0.3.10 4,办公区分为市场部和研发部,研…

activemq-CVE-2022-41678

Apache ActiveMQ Jolokia 后台远程代码执行漏洞 Apache ActiveMQ在5.16.5&#xff0c;5.17.3版本及以前&#xff0c;后台Jolokia存在一处任意文件写入导致的远程代码执行漏洞。 启动环境 admin/admin 方法一&#xff1a;利用poc 这个方法受到ActiveMQ版本的限制&#xff0c;因…

化妆品3D虚拟三维数字化营销展示更加生动、真实、高效!

随着人们越来越追求高速便捷的生活工作方式&#xff0c;企业在营销市场也偏国际化&#xff0c;借助VR全景制作技术&#xff0c;将企业1:1复刻到云端数字化世界&#xff0c;能带来高沉浸式的逼真、震撼效果。 通过我们独特的漫游点自然场景过渡技术&#xff0c;您将置身于一个真…

Java | Leetcode Java题解之第225题用队列实现栈

题目&#xff1a; 题解&#xff1a; class MyStack {Queue<Integer> queue;/** Initialize your data structure here. */public MyStack() {queue new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {int n queue.size();…

Qt Creator仿Visual Studio黑色主题

转自本人博客&#xff1a;Qt Creator仿Visual Studio黑色主题 1.演示 配置文件和步骤在后面&#xff0c;先看成品&#xff0c;分别是QWidget和QML的代码编写界面&#xff1a; 2. 主题配置文件 下载链接&#xff1a;QtCreator _theme_VS_dark.xml 也可以自己新建一个xml文件&…

理解局域网技术:从基础到进阶

局域网&#xff08;LAN&#xff09;是在20世纪70年代末发展起来的&#xff0c;起初主要用于连接单位内部的计算机&#xff0c;使它们能够方便地共享各种硬件、软件和数据资源。局域网的主要特点是网络为一个单位所拥有&#xff0c;地理范围和站点数目均有限。 局域网技术在计算…

后端——全局异常处理

一、老办法try-catch 当我们执行一些错误操作导致程序报错时&#xff0c;程序会捕捉到异常报错&#xff0c;这个异常会存在一个Exception对象里 那我们在spring boot工程开发时&#xff0c;当我们执行一个sql查询时报错了&#xff0c;那就会从最底层的Mapper层捕捉到Exceptio…