【优选算法】字符串 {相关编程题解析}

2024-06-05 07:20

本文主要是介绍【优选算法】字符串 {相关编程题解析},希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、相关编程题

1.1 最长公共前缀

题目链接

14. 最长公共前缀 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

// 解法一:两两比较
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int k = strs[0].size(); //表示最长公共前缀的结束位置for(int i = 0; i < strs.size()-1; ++i){for(int j = 0; j < k; ++j){if(j==min(strs[i].size(), strs[i+1].size()) || strs[i][j] != strs[i+1][j]){k = j;break;}}}return string(strs[0], 0, k);}
};// 解法二:统一比较
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int k = 0;while(k < strs[0].size()){char ch = strs[0][k];for(int i = 1; i < strs.size(); ++i){if(k==strs[i].size() || strs[i][k]!=ch)return string(strs[0], 0, k);}   ++k;}return strs[0];}
};

1.2 最长回文子串

题目链接

5. 最长回文子串 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

//中心扩展算法
class Solution {
public:string longestPalindrome(string s) {int maxlen = 0, maxi = 0, n = s.size();for(int i = 0; i < n; ++i) //依次枚举所有的中点{//奇数长度的扩展int j = i, k = i;for(; j>=0 && k<n; --j, ++k)if(s[j] != s[k]) break;if(maxlen < k-j-1){maxlen = k-j-1;maxi = j+1;}//偶数长度的扩展j = i; k = i+1;for(; j>=0 && k<n; --j, ++k)if(s[j] != s[k]) break;if(maxlen < k-j-1){maxlen = k-j-1;maxi = j+1;}}return s.substr(maxi, maxlen);}
};

1.3 二进制求和

题目链接

67. 二进制求和 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

  • 应该从低位到高位进行加法运算,将每一位的加法结果%2(进制数)就是这一位的结果,/2就是这一位的进位。
  • 要保证将两个运算量的每一位都遍历相加,并不再有进位,此时结束循环。
  • 要将最终的计算结果逆序才能得到正确的答案。

编写代码

class Solution {
public:string addBinary(string a, string b) {int i = a.size()-1, j = b.size()-1, t = 0;string ret;while(i>=0 || j>=0 || t>0){if(i>=0) t+=a[i--]-'0';if(j>=0) t+=b[j--]-'0';ret+=t%2+'0';t/=2;}reverse(ret.begin(), ret.end());return ret;}
};

1.4 字符串相乘

题目链接

43. 字符串相乘 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

//解法一:模拟
class Solution {
public:string multiply(string num1, string num2) {//为了从低位到高位相乘,先将两字符串逆序reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());string tmp, ret; //tmp存储每位相乘的结果,ret是最终结果//用num1的每一位与num2相乘,再将tmp结果相加到retfor(int i = 0; i < num1.size(); ++i) {tmp.clear();for(int k = 0; k < i; ++k) tmp+='0'; //高位相乘补'0'int mul = 0; //保存每位相乘的结果及进位for(int j = 0; j < num2.size(); ++j){mul += (num1[i]-'0')*(num2[j]-'0');tmp+=mul%10+'0';mul/=10;}while(mul>0){tmp+=mul%10+'0';mul/=10;}ret = StrSum(ret, tmp); }//处理前导'0'int i = ret.size()-1;while(i>0) //注意个位的'0'保留{if(ret[i] != '0') break;else --i;}ret.resize(i+1);//将结果翻转reverse(ret.begin(), ret.end());return ret;}//两逆序字符串相加,返回的结果也是逆序的(从低位到高位)string StrSum(const string& str1,const string& str2){int i = 0, j = 0, t = 0;string ret;while(i<str1.size() || j<str2.size() || t>0){if(i<str1.size()) t+=str1[i++]-'0';if(j<str2.size()) t+=str2[j++]-'0';ret += t%10+'0';t/=10;}return ret;}
};//解法二:无进位相乘再相加,最后处理进位
class Solution {
public:string multiply(string num1, string num2) {//为了从低位到高位相乘,先将两字符串逆序reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//无进位相乘然后相加int m = num1.size(), n = num2.size();vector<int> tmp(m+n-1, 0);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, i = 0;while(i<tmp.size() || t>0){if(i<m+n-1) t+=tmp[i++];ret+=t%10+'0';t/=10;}//处理前导'0'while(ret.size()>1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

这篇关于【优选算法】字符串 {相关编程题解析}的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032431

相关文章

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步