目录
一、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
初始化为i
,right
初始化为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 分别为两个输入字符串的长度。这个方法非常适合处理大整数的乘法运算,因为它不依赖于内置的数值类型。