随想录二刷Day09——字符串

字符串

1. 反转字符串

344. 反转字符串

思路：
设置两个指针，分别指向字符串首尾，两指针向中间移动，内容交换。

class Solution {
public:void reverseString(vector<char>& s) {int s_len = s.size();int left = 0, right = s_len - 1;char temp;while (left < right) {temp = s[left];s[left++] = s[right];s[right--] = temp;}}
};

2. 反转字符串 II

541. 反转字符串 II

思路：
将每 2k 的前 k 个进行反转。
每 k 个一判断，如果最后不足 k 个，判断是前一个 k （奇数个），还是后一个 k （偶数个）：

• 奇数个 k，则将其剩余部分反转
• 偶数个 k，其前 k 个已经反转过了，不用再次反转

class Solution {
private:void myReverse(string &s, int left, int right) {right--;while (left < right) {swap(s[left++], s[right--]);}}public:string reverseStr(string s, int k) {int s_len = s.length();int i = 0;for (i = 0; i < s_len; i += k) {if ((i / k) & 1) {myReverse(s, i - k, i);}}if ((i / k) & 1) { // 剩余部分处理myReverse(s, i - k, s_len);}return s;}
};

3. 替换空格

剑指 Offer 05. 替换空格

思路：

1. 统计字符串中空格的数目
2. 将字符串的长度扩展为 原来长度 + 2 * 空格数
3. 定义两个指针分别从新旧字符串的结尾位置向字符串开头遍历，如果遇到空格，则新数组从后往前填入 02% ，否则直接将旧字符串指针处的值填到新字符串指针所在位置即可
4. 指针前移至下标为 0。

class Solution {
public:string replaceSpace(string s) {int s_len = s.length();int space_num = 0;for (int i = 0; i < s_len; i++) {if (s[i] == ' ') space_num++;}int new_s_len = s_len + space_num * 2;s.resize(new_s_len);int i = s_len, j = new_s_len;while (i >= 0) {if (s[i] != ' ') {s[j--] = s[i--];} else {s[j--] = '0';s[j--] = '2';s[j--] = '%';i--;}}return s;}
};

4. 反转字符串中的单词

151. 反转字符串中的单词

思路：
0. 把字符串间多余的空格去掉

1. 将字符串中的每个单词反转
2. 将整个字符串反转

class Solution {
private:void myReverse(string &s, int left, int right) {while (left < right) {swap(s[left], s[right]);left++;right--;}}public:string reverseWords(string s) {int s_len = s.length();int new_s_len = 0;// 处理多余的空格for (int i = 0; i < s_len; i++) {if (i == 0 && s[i] == ' ') continue;if ((s[i] == ' ' && s[i - 1] == ' ') || (s[i] == ' ' && i == s_len - 1)) continue;else {s[new_s_len++] = s[i];}}while (s[new_s_len - 1] == ' ') new_s_len--; // 把末尾空格去掉s.resize(new_s_len);// 反转每个单词int start_pos = 0;for (int i = 0; i < new_s_len; i++) {if (i == 0 || s[i - 1] == ' ') start_pos = i;if (s[i] == ' ') myReverse(s, start_pos, i - 1);}myReverse(s, start_pos, new_s_len - 1); // 反转最后一个单词// 反转整个字符串myReverse(s, 0, new_s_len - 1);return s;}
};

5. 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

思路：
本来还想模拟一下，需要整个字符串调整 k 次，看完卡哥的解法，直呼妙不可言！！！

1. 反转前 n 个字符
2. 反转后 n 个字符
3. 反转整个字符

class Solution {
public:string reverseLeftWords(string s, int n) {reverse(s.begin(), s.begin() + n);reverse(s.begin() + n, s.end());reverse(s.begin(), s.end());return s;}
};