代码随想录day8 ● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串

344. 反转字符串

 1 class Solution {
 2 public:
 3     void reverseString(vector<char>& s) {
 4         for (int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){
 5             //交换两头的字母，经典倒油瓶
 6             //char temp = s[i];
 7             //s[i] = s[j];
 8             //s[j] = temp;
 9 
10             //函数法
11             swap(s[i], s[j]);
12         }
13     }
14 };

541. 反转字符串 II

 1 class Solution {
 2 public:
 3 
 4     void reverse(string& s, int start, int end){
 5         for (int i = start, j = end; i < j; i++, j--){
 6             swap(s[i], s[j]);
 7         }
 8     }
 9 
10     string reverseStr(string s, int k) {
11         for (int i = 0; i < s.size(); i += 2 * k){
12             //反转前K个字母
13             if (i + k <= s.size()){
14                 reverse(s, i, i + k - 1);
15             //反转剩下的字母
16             } else {
17                 reverse(s, i, s.size() -1);
18             }
19         }
20         return s;
21     }
22 };

剑指 Offer 05. 替换空格

 1 class Solution {
 2 public:
 3     string replaceSpace(string s) {
 4         //先统计空格的个数
 5         int count = 0;//空格个数
 6         int sOldSize = s.size();
 7         for (int i = 0; i < s.size(); i++){
 8             if (s[i] == ' '){
 9                 count++;
10             }
11         }
12 
13         //扩充数组的大小
14         s.resize(sOldSize + count * 2);
15         int sNewSize = s.size();
16         //从后往前将空格替换为%20
17         for (int i = sOldSize - 1, j = sNewSize - 1; i < j; i--, j--){
18             if (s[i] != ' '){
19                 s[j] = s[i];
20             } else {
21                 s[j] = '0';
22                 s[j - 1] = '2';
23                 s[j - 2] = '%';
24                 j -= 2;
25             }
26         }
27         return s;
28     }
29 };

151. 反转字符串中的单词

 1 class Solution {
 2 public:
 3     //反转字符串
 4     void reverse(string& s, int start, int end){
 5         for (int i = start, j = end; i < j; i++, j--){
 6             swap(s[i], s[j]);
 7         }
 8     }
 9     //删除多余空格
10     void  removeExtraSpaces(string& s){
11         //定义慢指针
12         int slow = 0;
13         for (int i = 0; i < s.size(); ++i){
14             //遇到非空格就处理，即删除所有的空格
15             if (s[i] != ' '){
16                 if (slow != 0){
17                     s[slow++] = ' ';
18                 }
19                 //补上该单词
20                 while (i < s.size() && s[i] != ' '){
21                     s[slow++] = s[i++];
22                 }
23             }
24         }
25         //重新设置数组大小
26         s.resize(slow);
27     }
28     //反转数组内单词
29     string reverseWords(string s) {
30         //删除数组内多余空格
31         removeExtraSpaces(s);
32         //反转整个字符串
33         reverse(s, 0, s.size() - 1);
34         //第一个单词的下标为0
35         int start = 0;
36         for (int i = 0; i <= s.size(); ++i){
37             if (i == s.size() || s[i] == ' '){
38                 reverse(s, start, i - 1);
39                 start = i + 1;
40             }
41         }
42         return s;
43     }
44 };

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

1 class Solution {
2 public:
3     string reverseLeftWords(string s, int n) {
4         reverse(s.begin(), s.begin() + n);
5         reverse(s.begin() + n, s.end());
6         reverse(s.begin(), s.end());
7         return s;
8     }
9 };

 1 class Solution {
 2 public:
 3     string reverseLeftWords(string s, int n) {
 4         //记录要移动的字母
 5         string str = {s.begin(), s.begin() + n};
 6         //将后面的字母向前移动
 7         for (int i = n; i < s.size(); i++){
 8             s[i - n] = s[i];
 9         } 
10         int j = 0;
11         int k = s.size() - n;
12         //将记录下来的字母替换原来的字母
13         for (; k < s.size(); k++){
14             s[k] = str[j];
15             cout << str[j] << endl;
16             j++;
17         }
18         return s;
19     }
20 };