字符串(典型算法思想)—— OJ例题算法解析思路

目录

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

解法一:算法代码(两两比较)

1. 初始化公共前缀

2. 遍历字符串数组

3. 辅助函数 findCommon

4. 返回最终结果

总结

解法二:算法代码(统一比较)

1. 初始化

2. 外层循环

3. 内层比较

4. 返回结果

总结

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

算法代码:(中心扩散) 

1. 初始化变量

2. 遍历每个字符

3. 奇数长度的回文扩展

4. 偶数长度的回文扩展

5. 返回结果

总结

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

算法代码:(模拟十进制的大数相加的过程) 

1. 初始化变量

2. 逐位相加

3. 反转结果字符串

4. 返回结果

总结

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

算法代码: (无进位相乘然后相加,最后处理进位)

1. 初始化和反转字符串

2. 无进位相乘

3. 处理进位

4. 处理前导零

5. 反转结果字符串

6. 返回结果

总结


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

解法一:算法代码(两两比较)

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 解法⼀:两两⽐较string ret = strs[0];for (int i = 1; i < strs.size(); i++)ret = findCommon(ret, strs[i]);return ret;}string findCommon(string& s1, string& s2) {int i = 0;while (i < min(s1.size(), s2.size()) && s1[i] == s2[i])i++;return s1.substr(0, i);}
};

1. 初始化公共前缀

  • 选择第一个字符串:将数组中的第一个字符串 strs[0] 作为初始的公共前缀 ret。这是因为在比较多个字符串时,至少第一个字符串本身是一个候选的公共前缀。

2. 遍历字符串数组

  • 逐个比较:使用一个循环,从第二个字符串(索引为 1)开始,逐个与当前的公共前缀 ret 进行比较,直到遍历完整个字符串数组。对于每个字符串,调用辅助函数 findCommon 来更新公共前缀。

3. 辅助函数 findCommon

  • 比较两个字符串:在 findCommon 函数中,传入两个字符串 s1 和 s2。初始化一个索引 i 为 0。

  • 逐字符比较:使用 while 循环逐字符比较 s1 和 s2

    • 循环条件是 i 小于 s1 和 s2 的最小长度,并且当前字符相同(s1[i] == s2[i])。

    • 当条件满足时,增加 i,表示当前公共前缀的长度。

  • 返回公共前缀:使用 s1.substr(0, i) 返回 s1 的子串,即从头到当前公共前缀的长度 i 的部分。

4. 返回最终结果

  • 返回公共前缀:当所有字符串都被比较过后,最终的公共前缀存储在 ret 中,函数返回这个结果。

总结

        该算法通过逐对字符串的比较,逐步更新公共前缀,最终得到所有字符串的最长公共前缀。时间复杂度为 O(S),其中 S 是所有字符串中字符的总数。这种方法简单直观,适合处理较小规模的字符串数组。

解法二:算法代码(统一比较)

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];}
};

1. 初始化

  • 选择第一个字符串:代码通过遍历第一个字符串 strs[0] 的每个字符来作为公共前缀的基础。

2. 外层循环

  • 逐字符遍历:使用一个外层循环遍历第一个字符串的每个字符,索引 i 表示当前字符的位置。

3. 内层比较

  • 逐个比较其他字符串:在外层循环中,使用一个内层循环,从第二个字符串开始(索引 j),依次比较当前字符 tmp(即 strs[0][i])与每个其他字符串的对应字符(strs[j][i])。

  • 条件检查

    • 如果 i 超出了当前字符串 strs[j] 的长度(即 i == strs[j].size()),或者当前字符 tmp 与 strs[j][i] 不相等,说明公共前缀到此为止,返回 strs[0] 从开始到 i 的子串(strs[0].substr(0, i))。

4. 返回结果

  • 无不匹配情况:如果外层循环完成而没有返回,意味着第一个字符串 strs[0] 本身就是所有字符串的公共前缀,直接返回 strs[0]

总结

        该算法通过统一比较的方式,逐字符检查所有字符串,能够高效地找到最长的公共前缀。时间复杂度为 O(S),其中 S 是所有字符串中字符的总数。如果没有公共前缀,该方法也能在最坏情况下高效停止并返回结果。这个方法简洁且易于理解,适合处理较小规模的字符串数组。

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

算法代码:(中心扩散) 

class Solution {
public:string longestPalindrome(string s) {// 中⼼扩展算法int begin = 0, len = 0, n = s.size();for (int 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);}
};

1. 初始化变量

  • 变量定义

    • begin:用于记录最长回文子串的起始索引。

    • len:用于记录当前找到的最长回文子串的长度。

    • n:存储字符串 s 的长度。

2. 遍历每个字符

  • 中心点枚举:使用一个循环遍历字符串 s 中的每个字符。每个字符可以视为回文的中心点,回文可以是奇数长度或偶数长度,因此需要处理这两种情况。

3. 奇数长度的回文扩展

  • 设置左右指针:将 left 和 right 都初始化为当前字符的索引 i,表示以 s[i] 为中心的奇数长度回文。

  • 扩展检查:使用一个 while 循环进行扩展,条件是 left 和 right 在字符串范围内,并且两个指针指向的字符相同。循环中向左右扩展 left-- 和 right++

  • 更新最长回文子串:在每次扩展后,如果找到的回文长度(right - left - 1)比当前记录的最长长度 len 更长,则更新 begin 和 len

4. 偶数长度的回文扩展

  • 设置左右指针:将 left 初始化为 iright 初始化为 i + 1,表示以 s[i] 和 s[i + 1] 为中心的偶数长度回文。

  • 扩展检查:同样使用 while 循环进行扩展,检查条件与之前相同。

  • 更新最长回文子串:如果找到的回文长度更长,则更新 begin 和 len

5. 返回结果

  • 提取并返回最长回文子串:循环结束后,利用 s.substr(begin, len) 返回最长的回文子串。

总结

        该算法通过中心扩展的方法,逐个检查每个字符作为回文中心的可能性,有效地检测出所有可能的回文子串。时间复杂度为 O(n²),其中 n 是字符串的长度。此方法简单且直观,适合处理较短的字符串,能够很好地找到最长回文子串。

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

算法代码:(模拟十进制的大数相加的过程) 

class Solution {
public:string addBinary(string a, string b) {string ret;int cur1 = a.size() - 1, cur2 = b.size() - 1, 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;}
};

1. 初始化变量

  • 结果字符串 ret:用于存储最终的二进制加法结果。

  • 指针 cur1 和 cur2:初始化为字符串 a 和 b 的最后一位(即末尾字符),用于从后往前逐位相加。

  • 进位变量 t:用于存储当前位的进位值,初始化为 0。

2. 逐位相加

  • 循环条件:使用 while 循环,条件是 cur1 或 cur2 大于等于 0(表示还有位数未处理)或者进位 t 非零(表示最后一位的进位需要处理)。

  • 处理每一位

    • 如果 cur1 大于等于 0,说明字符串 a 还有剩余位数,将 a[cur1](当前位)转换为数字并加到进位 t 中,然后将 cur1 向左移动一位(--cur1)。

    • 如果 cur2 大于等于 0,执行类似的操作,将 b[cur2] 加入进位,并将 cur2 向左移动一位。

    • 计算当前位的结果:使用 t % 2 获取当前位的值(即和的最后一位),并将其转换为字符形式 '0' 或 '1',然后将结果添加到字符串 ret 中。

    • 更新进位:将 t 除以 2,计算下一位的进位。

3. 反转结果字符串

  • 反转 ret:因为在计算过程中是从最低位开始添加结果到字符串 ret,最终需要将字符串反转,以获得正确的二进制表示。

4. 返回结果

  • 返回最终结果:返回反转后的字符串 ret,即两个二进制字符串相加的结果。

总结

        该算法通过模拟二进制加法的过程,逐位相加并处理进位,能够有效地计算出两个二进制字符串的和。时间复杂度为 O(max(m, n)),其中 m 和 n 分别是两个字符串的长度。这种方法简单直观,适合处理二进制字符串的加法运算。

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

算法代码: (无进位相乘然后相加,最后处理进位

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

1. 初始化和反转字符串

  • 获取字符串长度:首先,获取输入字符串 n1 和 n2 的长度,分别用 m 和 n 表示。

  • 反转字符串:将两个字符串反转,以便从低位到高位逐位相乘。这样可以简化乘法运算的过程。

2. 无进位相乘

  • 创建临时数组:使用一个向量 tmp 来存储每一位相乘的结果。该数组的大小为 m + n - 1,足以存储所有可能的乘积。

  • 逐位相乘:使用两个嵌套循环,外层循环遍历 n1 的每一位,内层循环遍历 n2 的每一位。对于每一对数字 n1[i]和 n2[j],计算它们的乘积,并将结果累加到 tmp[i + j] 中。

3. 处理进位

  • 初始化变量:使用变量 cur 来追踪 tmp 的当前索引,t 用于存储进位。

  • 计算最终结果:使用 while 循环,条件为 cur 小于 m + n - 1 或者进位 t 非零。在每次循环中:

    • 如果 cur 小于 m + n - 1,将 tmp[cur] 加入到 t 中,并自增 cur

    • 计算当前位的值 t % 10,并将其添加到结果字符串 ret 中(同样需要加上 '0' 转换为字符)。

    • 更新进位 t,通过 t /= 10 获得新的进位值。

4. 处理前导零

  • 去除前导零:在构造完成后,检查结果字符串 ret 是否有前导零(即,长度大于 1 且最后一个字符是 '0’)。如果有,逐个去除最后的零,直到没有前导零为止。

5. 反转结果字符串

  • 重新反转:由于结果字符串在构造时是从低位到高位的,因此在返回之前需要将其反转回正常顺序。

6. 返回结果

  • 最终返回:返回处理后的字符串 ret

总结

        该算法通过模拟手动乘法的过程,先进行无进位相乘,再处理进位,最终得到两个大整数的乘积。时间复杂度为 O(m * n),其中 m 和 n 分别为两个输入字符串的长度。这个方法非常适合处理大整数的乘法运算,因为它不依赖于内置的数值类型。

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

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

相关文章

宝塔面板开始ssl后,使用域名访问不了后台管理

宝塔面板后台开启ssl访问后&#xff0c;用的证书是其他第三方颁发的证书 再使用 域名/xxx 的形式&#xff1a;https://域名:xxx/xxx 访问后台&#xff0c;结果出现如下&#xff0c;不管使用 http 还是 https 的路径访问都进不后台管理 这个时候可以使用 https://ip/xxx 的方式来…

java继承

1.继承的内存图 2.成员方法不能被继承 虚方法表满足&#xff1a;1.非static、2.非private、3.非final

通用知识库问答流程

总体流程&#xff0c;定义回调&#xff08;函数执行完把回答的内容填充到数据库&#xff09;&#xff0c;使用封装的fastchat获取调用的模型&#xff0c; 根据向量数据库名&#xff0c;获取向量数据库实例 这是ssl 长连接的一种标准写法&#xff0c;首先写一个 生成器函数&…

WPS/Office使用其他LLM大语言模型作为AI助手

前言 WPS也有内置的AI&#xff0c;叫灵犀&#xff0c;但只能说是属于“能用&#xff0c;有好过无”&#xff0c;所以我一直在找能否在WPS上用上其他的LLM大语言模型&#xff0c;比如目前最火的DeepSeek&#xff0c;结论是&#xff1a;安装OfficeAI助手&#xff0c;就能在WPS上用…

亲测有效!使用Ollama本地部署DeepSeekR1模型,指定目录安装并实现可视化聊天与接口调用

文章目录 一、引言二、准备工作&#xff08;Ollama 工具介绍与下载&#xff09;2.1 Ollama介绍2.2 Ollama安装 三、指定目录安装 DeepSeek R1四、Chatbox 可视化聊天搭建4.1 Chatbox下载安装4.2 关联 DeepSeek R1 与 Chatbox 的步骤 五、使用 Ollama 调用 DeepSeek 接口5.1 请求…

4.SpringSecurity在分布式环境下的使用

参考 来源于黑马程序员&#xff1a; 手把手教你精通新版SpringSecurity 分布式认证概念说明 分布式认证&#xff0c;即我们常说的单点登录&#xff0c;简称SSO&#xff0c;指的是在多应用系统的项目中&#xff0c;用户只需要登录一次&#xff0c;就可以访 问所有互相信任的应…

傅里叶公式推导(五)

文章目录 从离散到连续回顾第四章F(w) 从离散到连续 回顾第四章 在周期 T&#xff0c; 傅里叶变换公式 f ( t ) ( t T ) f ( t ) ∑ n − ∞ ∞ C n e i n Δ w t C n 1 T ∫ 0 T f ( t ) e − i n Δ w t d t 式1 f(t)(tT) \\ f(t) \sum_{n-\infty}^{\infty }C_ne^{i…

VS Code User和System版区别【推荐使用System版本】and VSCode+Keil协同开发之Keil Assistant

VS Code User和System版区别 Chapter1 VS Code User和System版区别1. 对于安装而言2. 结束语 Chapter2 VS Code 安装、配置教程及插件推荐插件&#xff1a; Chapter3 VSCodeKeil协同开发之Keil Assistant1. 效果展示2. Keil Assistant简介3. Keil Assistant功能特性4. 部署步骤…

Python----Python高级(网络编程:网络高级:多播和广播,C/S架构,TCP,UDP,网络编程)

一、多播和广播 1.1、多播 1.1.1、定义 多播&#xff08;Multicast&#xff09;也称为组播&#xff0c;是一种一对多的通信方式&#xff0c;将信息从单个源发送到 多个特定的接收者。这些接收者组成一个特定的多播组&#xff0c;只有加入该组的设备才会接 收和处理多播数据。…

网络工程师 (41)IP协议、IP地址表示方法

一、IP协议 IP协议&#xff0c;全称网际互连协议&#xff08;Internet Protocol&#xff09;&#xff0c;是TCP/IP体系中的网络层协议。 寻址&#xff1a;IP协议通过IP地址来唯一标识网络上的每一台设备&#xff0c;确保数据能够准确地发送到目标主机。路由选择&#xff1a;IP协…

Kubernetes控制平面组件:etcd高可用集群搭建

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…

Banana Pi OpenWRT One 官方路由器的第一印象

OpenWRT One是OpenWRT开源社区推出的首款官方开发板&#xff0c;与Banana Pi社区共同设计&#xff0c;由Banana Pi制造和发行。路由器采用蓝色铝合金外壳&#xff0c;质感极佳&#xff0c;视觉效果远超宣传图。整体设计简洁&#xff0c;呈长方形&#xff0c;虽然不是特别时尚&a…

【每日一题 | 2025】2.10 ~ 2.16

个人主页&#xff1a;Guiat 归属专栏&#xff1a;每日一题 文章目录 1. 【2.10】P8707 [蓝桥杯 2020 省 AB1] 走方格2. 【2.11】P8742 [蓝桥杯 2021 省 AB] 砝码称重3. 【2.12】P8786 [蓝桥杯 2022 省 B] 李白打酒加强版4. 【2.13】P8725 [蓝桥杯 2020 省 AB3] 画中漂流5. 【2.…

微信小程序配置3 配置sass

1. 在config。json文件里面的setting配置“sass” 2. 改你需要的页面后缀名为scss。 3.查看页面即可看到样式。

撕碎QT面具(1):Tab Widget转到某个Tab页

笔者未系统学过C语法&#xff0c;仅有Java基础&#xff0c;具体写法仿照于大模型以及其它博客。自我感觉&#xff0c;如果会一门对象语言&#xff0c;没必要先刻意学C&#xff0c;因为自己具有对象语言的基础&#xff0c;等需要用什么再学也不迟。毕竟不是专门学C去搞算法。 1…

恩智浦:将开发文档迁移到DITA/XML

摘要&#xff1a;本文是德国同行Parson公司写的一篇文章&#xff0c;描述芯片巨头恩智浦编写文档方法如何从MS Word和Adobe Frame Maker转向基于DITA的结构化写作和发布。英文原文地址&#xff1a;https://www.parson-europe.com/en/references/nxp - 1 - 项目目标 在开发产…

基于SpringBoot的医院药房管理系统【源码+答辩PPT++项目部署】高质量论文1-1.5W字

作者简介&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流。✌ 主要内容&#xff1a;&#x1f31f;Java项目、Python项目、前端项目、PHP、ASP.NET、人工智能…

计算机性能与网络体系结构探讨 —— 基于《计算机网络》谢希仁第八版

(꒪ꇴ꒪ )&#xff0c;Hello我是祐言QAQ我的博客主页&#xff1a;C/C语言&#xff0c;数据结构&#xff0c;Linux基础&#xff0c;ARM开发板&#xff0c;网络编程等领域UP&#x1f30d;快上&#x1f698;&#xff0c;一起学习&#xff0c;让我们成为一个强大的攻城狮&#xff0…

【第11章:生成式AI与创意应用—11.4 生成式AI在其他领域的创新应用与未来展望】

凌晨三点,生物实验室的AI突然"灵光一闪"——它把抗病毒蛋白的结构图与蜂巢的六边形结构进行跨界组合,生成的新分子让老教授的手开始颤抖。这种打破学科壁垒的创造力,正是生成式AI带给人类最震撼的礼物。让我们走进这个"数字炼金术"的新时代。 一、科学…

网络安全:从攻击到防御的全景解析

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 1. 引言 在互联网高度发达的今天&#xff0c;网络安全已成为影响社会稳定、国家安全和企业发展的关键因素。无论是个人用户的数据…