1、反转字符串
首先我们来看第一道，先从简单一点的开始做起✍
① 题目描述：
力扣原题
class Solution {
public:
void reverseString(vector& s) {
}
};
② 思路分析：
- 本题很简单，就是将题目中给出的字符串做一个前后逆置的操作。这边首先想到的就是双指针的一个思路，让一个指针
i在前，一个指针j在后，相对而行，不断交互二者位置上的字符，直到二者相遇为止
③ 代码展示：
- 代码很简洁，一个for循环就能搞定了
void reverseString(vector& s) {
for(int i = 0, j = s.size() - 1; i < j; ++i, --j)
{
swap(s[i], s[j]);
}
}
④ 运行结果：
- 来看看执行结果，发现效率中一般，不过能AC就行😁
2、反转字符串||
接下去再来看第二道，稍稍复杂一些
① 题目描述：
力扣原题
class Solution {
public:
string reverseStr(string s, int k) {
}
};
② 思路分析：
-
本题相对上一题来说就发生了一些变化，虽然都是在反转字符串，但本题呢不是一个一个地在遍历，而是2k个2k个地在遍历，在题目给到的参数中还有一个k，我们在遍历这个字符串时是 ==一次遍历2k个，然后反转前k个==
-
在不断执行的过程中总会碰到结束，此时题目又给出了两种结果。
- 也就是当剩余的字符少于2k个，但是大于等于k个的话，则反转前k个，这个其实我们可以和题干中的意思做一个结合，多加一个是否到达结尾即可
- 当剩余的字符连k个都不足的话，此时将剩余的全部反转即可
-
很多同学在写本题的时候都会纠结于这个2k，所以在循环遍历的时候会选择拿一个计数器去计数，然后当这个计数器到达的 2k 的时候就对前k个去做反转，其实没必要这样，我们在这里直接去修改循环遍历的次数即可，即
i += 2 * k，让i每次移动的距离就是 2k 个，那当我们在遍历的时候也无需去考虑那么多了
接下去呢我们就要在循环内部去反转对应的字符串了，这里大家可以自己实现一个（就是我们上一题所讲的代码），或者是直接使用库函数【reverse】
- 不过记住了在库函数这里我们要传递的是 ==迭代器==，注意这里【reverse】是左闭右开的，所以不包含
i + k这个位置
reverse(s.begin() + i, s.begin() + i + k);
- 不过呢也不是任何区间我们都可以去做反转的，至少不能发生越界的情况，此时我们给出判断的条件
i + k = 0 || end2 >= 0)
- 我们来看一下这个案例就可以了，【999 + 1 = 1000】，如果我们执行完【9 + 1 = 10】后就结束了，那么最后返回的就是0了，这很明显是不符合实际的。那么当一个结束了之后还不能结束我们需要使用的是 按位或
||
然后我们就返回这个
retStr去执行一下吧，但是先计算的结果刚好反了- 如果对 string类 中的
operator+=()接口了解的话就可以清楚我们这里其实是做了一个尾插的操作，所以这个顺序才会是倒着的，那我们要获取到正确的顺序的话采取reverse()做一个颠倒即可
reverse(retStr.begin(), retStr.end());- 这回再去执行的话确实是没什么问题了，但是呢提交之后可以发现，有一些测试用例的话我们是跑不过（示例能跑过不代表所有测试用例都能跑过）
- 这个测试用例其实大家可以带入到我们上面的这个循环中，就发现它跑完一遍的话就结束了，因为位数只有一位，那么此时我们在循环结束之后应该再去做一个判断才行，如果这个进制位不为0的话（正常结束进制位一定为0），我们就要再把这个进制位给追加上去
// 如果在出了循环后carry为1的话, 则表示二者只有1位的长度 if(carry == 1) { retStr += '1'; }③ 代码展示：
- 然后展示一下，读者最好自己去推导一遍然后尝试着写写看
class Solution { public: string addStrings(string num1, string num2) { int end1 = num1.size() - 1; int end2 = num2.size() - 1; string retStr; int carry = 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 + carry; // 更新进位值 carry = ret / 10; // 取出当前位上的余数 ret %= 10; // 累加到新的string对象中去(尾插) retStr += (ret + '0'); end1--; end2--; } // 如果在出了循环后carry为1的话, 则表示二者只有1位的长度 if(carry == 1) { retStr += '1'; } // 最后再对尾插后的字符串做一个翻转 reverse(retStr.begin(), retStr.end()); return retStr; } };④ 运行结果：
- 来看看执行结果，发现效率中一般，不过能AC就行😁
10、字符串相乘【⭐⭐】
看完了 字符串相加 后，我们再来看 字符串相乘，本题要在上一题的基础上难很多，做好准备，发车了:car:
① 题目描述：
力扣原题
class Solution { public: string multiply(string num1, string num2) { } };② 思路分析：
- 题目意思也是一样很简单，把两个字符串当成数值一样来进行相乘，最后返回的结果还是一个 字符串。我们知道对于乘法而言和加法不同，对于加法而言我们只需要考虑一个进位的问题，但是对于乘法而言不一样，我们要考虑的则是更多
- 通过下面来看，两个三位数相乘的话我们要考虑让上面的那个数和下面的每个数进行相乘，并要把它们加起来，不过在相加的时候也需要再考虑到的时我们要实行的是【错位相加】，什么意思呢？
例如下面的这个
738不能直接和615进行相加，而是要和6150进行相加，因为这是上面的数与十位数【5】相乘所得的结果，那么下面也是一样，我们要和49200进行相加
代码走读🏃
💬 经过上面这么一分析，相信你一定觉得这个题目要考虑的因素有很多了。不用怕，我们立马来进行分析
- 首先我们考虑一下特殊情况，若是这个
num1或者是num2存在字符0相同的话，那不需要再进行相乘了，因为任何数与0相乘一定为0，那么我们直接返回“0”
if(num1 == "0" || num2 == "0") return "0";💬 接下去我们要明确的一点是，我们要让那些数进行相乘？要乘几次？
- 很明显这里的
num1为被乘数，num2是每一位乘数，它有几位我们就需要乘几次，所以我们这里拿【sz1】和【sz2】分别去做一个记录
int sz1 = num1.size(); // 被乘数 int sz2 = num2.size(); // 次数- 上面说到这个
num2的位数即为需要相乘的次数，那我们在这里给到的外层循环就是去遍历这个sz2的大小
for(int i = sz2 - 1; i >= 0; --i) { // ... }- 下面有两个string类的对象，
ans表示最后累加总和后所需要存放的字符串；curr则表示我们每乘完一次构后所需要累加到字符串
string ans = "0";string curr = "";- 下面这段逻辑非常地重要，看着代码本身大家应该就可以知道，就是我们在上面所说到的。如果被乘数和十位或者百位上的数相乘的话，若是在后面和总数进行相加的时候就需要对应地添上
0
// 给此处其余位添加0 for(int j = sz2 - 1; j > i; --j){ curr.push_back(0 + '0'); }那接下去呢我们就可以去获取到对应的字符，然后将它们转化为数值进行运算了
- 下面这一段代表的就是被乘数与其中一位的乘数进行相乘的逻辑，这个
[y]指的就是num2中的那一位乘数，而[x]则指的是通过循环获取到的每一位被乘数，二者的乘积还要再加上进制位，因为乘法和加法一定也会产生进制位，那么接下去两句在更新 当位结果和 进制位 的时候，读者就不会那么生疏了 - 那随着循环的一步步进行，num2中当前的这一位乘数和被乘数就计算出了结果
int carry = 0; // 进制位 int ret = 0; // 开始逐位累乘 int y = num2[i] - '0'; // 获取到当前这一位的数值 for(int k = sz1 - 1;k >= 0; --k) { int x = num1[k] - '0'; // 获取到被乘数的数值位 ret = x * y + carry; curr.push_back(ret % 10 + '0'); carry = ret / 10; // 更新进制位 }- 当然，和我们上一题中所考虑到的一样，对于乘法来说也会存在两个个位数的情况，如果此时因为循环只执行了一次的话，那还有一个位数一定没有被累加进来，此时我们就需要再把它拿过来
// 考虑到个位数的问题 if(carry != 0){ curr.push_back(carry % 10 + '0'); carry /= 10; }- 我们可以到VS下来测试一下这种情况，可以看到当这个
num1和num2都为个位数的时候，它们在相乘时只会进入一次循环，此时可以看到这个carry是为3的，因此还会再进入下面的那个if判断，将其追加到【curr】中
- 最后的话别忘记了我们是使用的
push_back()即尾插，那里面的字符串都是颠倒的，还要调用一下reverse()函数去做一个反转
// 翻转字符串 reverse(curr.begin(), curr.end());当然对于上面的这段逻辑只是被乘数与一个乘数之间的计算结果，我们要的是所有的结果之和
- 可再看一下下图思考思考
- 这里我们还需要一个字符串相加的逻辑，那其实的话就是我们在上面做到的那题
// 累加每一个计算完后的字符串 ans = AddStrings(ans, curr);③ 整体代码展示：
class Solution { public: string multiply(string num1, string num2) { if(num1 == "0" || num2 == "0") return "0"; int sz1 = num1.size(); // 被乘数 int sz2 = num2.size(); // 次数 string ans = "0"; // 外层遍历次数 for(int i = sz2 - 1; i >= 0; --i) { string curr = ""; // 给此处其余位添加0 for(int j = sz2 - 1; j > i; --j){ curr.push_back(0 + '0'); } int carry = 0; // 进制位 int ret = 0; // 开始逐位累乘 int y = num2[i] - '0'; // 获取到当前这一位的数值 for(int k = sz1 - 1;k >= 0; --k) { int x = num1[k] - '0'; // 获取到被乘数的数值位 ret = x * y + carry; curr.push_back(ret % 10 + '0'); carry = ret / 10; // 更新进制位 } // 考虑到个位数的问题 if(carry != 0){ curr.push_back(carry % 10 + '0'); carry /= 10; } // 翻转字符串 reverse(curr.begin(), curr.end()); // 累加每一个计算完后的字符串 ans = AddStrings(ans, curr); } return ans; } // 两个字符串相加逻辑 string AddStrings(string& num1, string& num2) { int end1 = num1.size() - 1; int end2 = num2.size() - 1; int ret = 0; int carry = 0; string retStr; while(end1 >= 0 || end2 >= 0 || carry != 0) { int val1 = end1 >= 0 ? num1[end1] - '0' : 0; int val2 = end2 >= 0 ? num2[end2] - '0' : 0; ret = val1 + val2 + carry; carry = ret / 10; retStr += ret % 10 + '0'; end1--; end2--; } reverse(retStr.begin(), retStr.end()); return retStr; } };调试观察💻
经过上面的代码走读，相信读者已经明白了一些原理，但是呢心中一定感觉还有些含糊。接下去我将会带着你一步步地去做调试，来看看这段代码究竟是如何
- 我们就以本文所讲的这个【123】和【456】带读者来看看
- 我们通过动图来观察，此时第一次进入循环，即要拿被乘数
123和第一个乘数位4进行计算，此时呢我们是无需添加0的，所以这里的循环不进入是对的，记住这边的这个循环的结束条件是j < i，而不是j
- 我们来看一下这个案例就可以了，【999 + 1 = 1000】，如果我们执行完【9 + 1 = 10】后就结束了，那么最后返回的就是0了，这很明显是不符合实际的。那么当一个结束了之后还不能结束我们需要使用的是 按位或
