🔥个人主页:Quitecoder
🔥专栏:Leetcode刷题
目录
- 1.仅反转字母
- 2.字符串中第一个唯一字符
- 3.验证回文串
- 4.字符串相加
- 5.反转字符串I I
- 6.反转字符串中的单词III
- 7.字符串相乘
- 8.把字符串转换为整数
1.仅反转字母
题目链接:917.仅仅反转字母
题目描述:
首先,这道题仅仅需要翻转字母,我们先写一个函数来判断是否为字母
bool Isletter(char ch) { if (ch >= 'a' && ch ='A' && ch public: bool Isletter(char ch) { if (ch = 'a' && ch size_t begin1 = 0; size_t end1 = s.size() - 1; while (begin1
函数逻辑
-
定义一个空字符串 result,它最终将存储相加后的结果
-
定义两个整型变量 end1 和 end2,分别表示 num1 和 num2 字符串的末位索引
-
定义变量 next,表示在每一步相加中可能产生的进位
-
使用一个 while 循环,条件是 end1 或 end2 中有一个或两个大于或等于0。这表示至少还有一个数字字符串有未处理的数字
-
在循环内部,分别计算 val1 和 val2,它们代表当前要相加的两个字符对应的数字值。如果索引小于0,则表示该数字字符串没有更多的位数可以处理,因此对应的值为0
-
计算 ret,它是 val1、val2 和前一步的进位 next 之和
-
更新 next 为 ret 除以10,因为手写加法中,超过10的部分产生进位
-
更新 ret 为 ret 对10取余,因为余数是当前位上的数字
-
将 ret 转换为对应的字符,然后将该字符插入 result 字符串的最前面
-
重复步骤5-9,直到处理完 num1 和 num2 的所有位数
-
循环结束后,检查是否还有未添加的进位 next。如果 next 为1,将字符 ‘1’ 插入 result 字符串的最前面(这一部分可以查阅函数库来了解insert的多种实现形式)
-
返回结果字符串 result
优化:
因为不断的头插,数据会挪动,使函数的时间复杂度来到了O(N2)
优化思路:
- 尾插,再进行反转
class Solution { public: string addStrings(string num1, string num2) { string result; int end1=num1.size()-1,end2=num2.size()-1; int next=0; while(end1>=0||end2>=0) { int val1=end1>=0?num1[end1--]-'0':0; int val2=end2>=0?num2[end2--]-'0':0; int ret=val1+val2+next; next=ret/10; ret=ret%10; result+=ret+'0'; } if(next==1) { result+='1'; } reverse(result.begin(), result.end()); return result; } };
5.反转字符串I I
题目链接:541.反转字符串I I
题目描述:
这段代码意在实现根据指定的整数 k 来部分反转字符串 s 的功能。但是,代码中有几个问题需要解决才能正确实现这一功能。
首先,让我们明确正确的逻辑:
- 遍历字符串,步长为 2k 字符。
- 在每个步长内:
- 如果剩余字符少于 k 个,则反转这些字符。
- 如果剩余字符小于 2k 但至少有 k 个,则只反转前 k 个字符
- 如果有足够的字符,则反转前 k 个字符,保持其余字符不变
class Solution { public: string reverseStr(string s, int k) { int size = s.size(); for (int start = 0; start size) { reverse(s.begin() + start, s.end()); } else { // 反转从 start 开始的 k 个字符 reverse(s.begin() + start, s.begin() + start + k); // 其余字符保持原样,根据题目要求这部分不需要任何操作 } } return s; } };
使用一个 for 循环,步长为 2 * k,遍历字符串 s,每次移动2k步,检查并反转前k个字符
在循环中检查剩余字符的数目,根据这个数目适当地反转字符串的一部分
使用 reverse 方法来反转从 start 开始的字符。注意,reverse 方法的第二个参数是我们想要反转区间的结束位置的下一个迭代器。如果剩余字符少于 k 个,则 reverse 的参数是 s.end(),这样可以反转从 start 开始的所有剩余字符
如果 start + k 小于或等于 size,则只反转前 k 个字符,而其余字符保持原样
6.反转字符串中的单词III
题目链接:557.反转字符串中的单词III
题目描述:
这道题主要思路就是找到每个空格位置对单词进行分割,逐个翻转
class Solution { public: string reverseWords(string s) { int size = s.size(); size_t pos = s.find(' '); int start = 0; while (pos != string::npos) { reverse(s.begin() + start, s.begin() + pos); start = pos + 1; pos = s.find(' ', start); } reverse(s.begin() + start, s.end()); return s; } };
注意,reverse接收的参数应该是迭代器,我们应该使用 s.begin() 加上相应的索引来获取正确的迭代器位置,每次找到一个空格就更新索引往后寻找,直到找到最后一个单词结束,结束后,再对最后一个单词进行反转
7.字符串相乘
题目链接:43.字符串相乘
题目描述:
思路一:
这道题与我们的字符串相加类似,我们需要做的就是用num2的每一位与num1相乘,每得到两个结果就进行字符串相加
class Solution { public: string multiply(string num1, string num2) { if (num1 == "0" || num2 == "0") return "0"; string result(num1.size() + num2.size(), '0'); for (int i = num1.size() - 1; i >= 0; i--) { for (int j = num2.size() - 1; j >= 0; j--) { int mul = (num1[i] - '0') * (num2[j] - '0'); int sum = (result[i + j + 1] - '0') + mul; result[i + j + 1] = (sum % 10) + '0'; result[i + j] += sum / 10; } } size_t startpos = result.find_first_not_of("0"); if (startpos != string::npos) { return result.substr(startpos); } return "0"; } };
这段代码理解起来十分简单,详细讲解:
此代码模拟了我们在纸上作乘法运算时的过程:
- 处理特殊情况
如果 num1 或 num2 中任意一个是 “0”,那么乘积为 “0”
if (num1 == "0" || num2 == "0") return "0";
- 初始化结果字符串
初始化结果字符串 result,长度为 num1.size() 加上 num2.size(),所以 result 的长度足以存储乘法得到的所有可能数字,包括合并进位。所有字符先被设置为 '0'
string result(num1.size() + num2.size(), '0');
- 嵌套循环
外层循环以 num1.size() - 1 开始,即 num1 字符串的最后一个字符,向前遍历整个字符串。内层循环以 num2.size() - 1 开始,即 num2 字符串的最后一个字符,向前遍历整个字符串。循环索引 i 和 j 分别对应 num1 和 num2 的每个数位
for (int i = num1.size() - 1; i >= 0; i--) { for (int j = num2.size() - 1; j >= 0; j--) { // ... } }
- 计算乘积
对于每对数位(num1[i], num2[j]),计算它们值的乘积,另外再把结果 result 相应位置上的值加上去(需要先把result[i+j+1]字符转化为整数)。需要注意的是,计算中还会加上之前的进位
int mul = (num1[i] - '0') * (num2[j] - '0'); int sum = (result[i + j + 1] - '0') + mul;
- 处理结果和进位
当前乘积mul与结果result当前位置上的数相加后,可能会大于等于10,即产生进位。将当前位的结果模上10得到最终结果,并把商加到下一位上
result[i + j + 1] = (sum % 10) + '0'; result[i + j] += sum / 10;
- 移除前导零
由于乘积可能比 num1.size() + num2.size() 这么长要短,所以会在 result 最前面出现一些 ‘0’。我们需要找到第一个不是 ‘0’ 的字符的位置,并从那里开始返回子字符串
size_t startpos = result.find_first_not_of("0"); if (startpos != string::npos) { return result.substr(startpos); }
如果整个字符串都是 ‘0’,说明两个数的乘积是 0,直接返回 “0”。
- 返回结果
如果 result 中有非 ‘0’ 的字符,就从第一个非零字符开始返回剩余的子字符串,否则直接返回 “0”。
8.把字符串转换为整数
题目链接:LCR 192.把字符串转换为整数(atoi)
题目描述:
首先,我们写两个函数来对空字符和正负号进行处理:
int i = 0; int sign = 1; int result = 0; while (i
接着处理数字部分,如果超过32 位有符号整数范围,则进行截断:
class Solution { public: int myAtoi(string str) { int i = 0; int sign = 1; int result = 0; while (i INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) { return sign == 1 ? INT_MAX : INT_MIN; } result = 10 * result + digit; i++; } return result * sign; } };
if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) { return sign == 1 ? INT_MAX : INT_MIN; }
这部分代码的目的是检查在将下一个数字添加到已解析的结果 result 之前,是否会导致整数溢出。溢出指的是整数的值超出了它能表示的最大范围。在C++中,对于32位 int 类型,能够表示的最大整数值定义在 头文件中,称为 INT_MAX,通常为 2^31 - 1(即2147483647),最小整数值为 INT_MIN,通常为 -2^31(即-2147483648)
为了避免result在由字符串转换为整数时溢出,代码使用了下列条件检查:
result > INT_MAX / 10
这个检查确保将当前的 result 乘以 10(也就是添加新的数字之前)不会超过最大整数值 INT_MAX。如果 result 已经大于 INT_MAX 除以 10,那么在下一步乘以 10 时一定会发生溢出。
(result == INT_MAX / 10 && digit > INT_MAX % 10)
如果 result 已经达到了 INT_MAX 除以 10 的值,那么我们可以检查下一个要添加的数字(digit)是否会导致溢出。因为我们知道 result 乘以 10 刚好达到但不超过 INT_MAX,所以我们只需要保证添加的数字小于或等于 INT_MAX 最后一个数位的数字的值,即 INT_MAX % 10。如果 digit 大于这个值,那么加上 digit 之后会超出 INT_MAX,发生溢出
如果以上任何一种溢出条件满足,那么根据数字的正负符号,函数返回最大或最小的 int 值:
return sign == 1 ? INT_MAX : INT_MIN;
- 当 sign 为 1,即正数的情况下,返回 INT_MAX。
- 当 sign 为 -1,即负数的情况下,返回 INT_MIN。
本节内容到此结束,感谢大家阅读,可以多多交流!!
-
还没有评论,来说两句吧...