👉仅反转字母👈
给你一个字符串 s ，根据下述规则反转字符串：
- 所有非英文字母保留在原有位置。
- 所有英文字母（小写或大写）位置反转。
返回反转后的 s 。
思路：这道题可以借助快排的思想，左边找出字母，右边找出字母，然后进行交换。如果不是字母，就继续找。
class Solution { public: string reverseOnlyLetters(string s) { size_t begin = 0; size_t end = s.size() - 1; while(begin < end) { // isalpha是判断是否是字母的函数接口 while(begin < end && !isalpha(s[begin])) { ++begin; } while(begin < end && !isalpha(s[end])) { --end; } swap(s[begin], s[end]); ++begin; --end; } return s; } };
👉字符串中的第一个唯一字符👈
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
思路：可以借助哈希映射的思想，用一个数组统计每个字母出现的次数，然后再遍历字符串就能够知道那个字母是第一个唯一字符。
class Solution { public: int firstUniqChar(string s) { int count[26] = {0}; // 统计字母出现的次数 for(auto ch : s) { ++count[ch - 'a']; } // 顺序遍历字符串，找出第一个唯一字母 for(int i = 0; i < s.size(); i++) { if(count[s[i] - 'a'] == 1) return i; } return -1; } };
👉字符串相加👈
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
思路：这道题主要考察的就是竖式相加，我们可以从字符串的末尾依次往前相加，并保存进位信息。那如何将这个过程转换成代码呢？先定义两个变量end1和end2，并初始化为size - 1，如何利用 while 循环从后往前遍历字符串。当end1和end2都小于0时，while 循环结束。在while 循环里，定义三个变量val1、val2和ret，ret等于val1 + val2 + carry，其中carry为进位信息，其值为ret / 10。如果end小于0，则val的值为0。现在我们已经得到了相加的结果和进位信息了，就可以将数据插入到字符串。插入有两种方式，可以头插，也可以尾插。如果采用头插，效率会比较低，因为需要挪动数据。如果采用尾插，循环结束后需要将字符串逆置一下。
class Solution { public: string addStrings(string num1, string num2) { int end1 = num1.size() - 1, end2 = num2.size() - 1; int carry = 0; string retStr; retStr.reserve(max(num1.size(), num2.size()) + 1); 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; retStr.insert(0, 1, '0' + ret); --end1; --end2; } // 处理进位信息 if(carry == 1) retStr.insert(0, 1, '1'); return retStr; } };
class Solution { public: string addStrings(string num1, string num2) { int end1 = num1.size() - 1, end2 = num2.size() - 1; int carry = 0; string retStr; retStr.reserve(max(num1.size(), num2.size()) + 1); 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; retStr += '0' + ret; --end1; --end2; } // 处理进位信息 if(carry == 1) retStr += '1'; // 逆置字符串 reverse(retStr.begin(), retStr.end()); return retStr; } };
👉字符串相乘👈
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
思路：首先将补零，将 num2 的每位数字和 num1 相乘的结果存到 ret1 里，再将 ret1 逆置就能得到 num2 的低位到高位与 num1 相乘的结果，最后将 ret1 加到结果 ret 上，ret 就是最终相乘的结果了。
class Solution { public: string addStrings(string num1, string num2) { int end1 = num1.size() - 1, end2 = num2.size() - 1; int carry = 0; string retStr; retStr.reserve(max(num1.size(), num2.size()) + 1); 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; retStr += '0' + ret; --end1; --end2; } if(carry == 1) retStr += '1'; reverse(retStr.begin(), retStr.end()); return retStr; } string multiply(string num1, string num2) { // 思路：首先将补零，将num2的每位数字和num1相乘的结果存到ret1里 // 再将ret1逆置就能得到num2的个位、十位和百位与num1相乘的结果 // 再将ret1加到结果ret上，ret就是最终相乘的结果了 string ret("0"); if(num1[0] == '0' || num2[0] == '0') { return ret; } int size1 = (int)num1.size(); int size2 = (int)num2.size(); for(int i = size2 - 1; i >= 0; i--) { string ret1; for(int j = 0; j < size2 - 1 - i; j++) { ret1.append(1, '0'); } int carry = 0; for(int j = size1 - 1; j >= 0; j--) { int val1 = num1[j] - '0'; int val2 = num2[i] - '0'; int ret2 = val1 * val2 + carry; carry = ret2 / 10; ret1.append(1, '0' + ret2 % 10); } if(carry > 0) { ret1.append(1, '0' + carry); } reverse(ret1.begin(), ret1.end()); ret = addStrings(ret, ret1); } return ret; } };
👉反转字符串中的单词 III👈
给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
思路：定义两个变量pos和prevpos，pos的初始值为第一个空格所在的位置，prevpos的初始值为0。当pos != string::npos时，进入 while 循环，将prevpos到pos之间的字符逆置，逆置之后，prevpos = pos + 1，pos等于下一个空格的位置；while 循环结束，将prevpos到s.size()-1之间的字符逆置，然后字符串的单词都逆置过来了。
class Solution { public: // 逆置算法 void reverse(string& s, size_t begin, size_t end) { while(begin < end) { swap(s[begin++], s[end--]); } } string reverseWords(string s) { size_t pos = s.find(' ', 0); size_t prevpos = 0; while(pos != string::npos) { reverse(s, prevpos, pos - 1); prevpos = pos + 1; pos = s.find(' ', pos + 1); } reverse(s, prevpos, s.size() - 1); return s; } };
👉反转字符串 II👈
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
思路：先定义一个逆置算法的函数，然后判断剩余的字符有多少，然后进行相应的操作就行了。
class Solution { public: //翻转start到end区间的字符串 void Reverse(string &s, int start, int end) { char tmp; while(start < end) { tmp = s[start]; s[start] = s[end]; s[end] = tmp; start++; end--; } } string reverseStr(string s, int k) { int len = s.size(); for(int i = 0; i < len; i += 2 * k) { // 剩余字符大于k个 if(i + k - 1 < len) Reverse(s, i, i + k - 1); else // 剩余字符小于或等于k个 Reverse(s, i, len - 1); } return s; } };
👉总结👈
好久没有写过刷题博客了，上次写的时候还是在上次。希望大家能够喜欢，那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
