
反转字符串
leetcode.344
- 链接https://leetcode.cn/problems/...
- 解题方法:双指针
l,r指针分别放在字符串的首尾两端,每次交换两个字符
每交换一次指针向中间移动一位 leetcode解题代码
class Solution { public: void reverseString(vector<char>& s) { int l = 0, r = s.size() - 1; while (l < r){ swap(s[l], s[r]); l ++, r --; } } };
leetcode.541
- 链接https://leetcode.cn/problems/...
- 解题方法:双指针
定义维护的区间[l, r],每次维护2k个数 leetcode解题代码
class Solution { public: string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n - 1; i += k * 2){ int l = i, r = min(i + k, n); reverse(s.begin() + l, s.begin() + r); } return s; } };
反转字符串中的单词
- 题目类型:给一个字符串组成的句子(带空格或标点),然后对句中单个字符串进行一系列处理
- 这类题目可以分为两类,一类是有前置或者后置空格的,另一类是没有前置和后置空格的
leetcode.58
- 链接https://leetcode.cn/problems/...
- 解题方法:创建一个临时字符串(用来存每一个单词),和一个答案数组
遍历原字符串,如果遍历到空格,判断临时字符串是否为空
如果临时字符串非空则说明已经遍历完一个单词,将其加入答案数组中并清空临时字符串
如果遍历到的不是空格,将其加入临时字符串中 leetcode解题代码
class Solution { public: int lengthOfLastWord(string s) { s += " ";// 在字符串末尾加上一个空格防止遗漏最后一个单词 string temp = ""; vector<string> res; for (auto c: s){ if (c == ' '){ if (!temp.empty()){ res.push_back(temp); temp.clear(); } } else temp += c; } if (res.empty()) return 0; return res.back().size(); } };
leetcode.557
- 链接https://leetcode.cn/problems/...
- 解题方法:与上一题类似
leetcode解题代码
class Solution { public: string reverseWords(string s) { s += " "; string temp = ""; vector<string> res; for (auto c: s){ if (c == ' '){ if (!temp.empty()){ res.push_back(temp); temp.clear(); } } else temp += c; } s.clear(); for (auto c: res){ reverse(c.begin(), c.end()); s += c + ' '; } s.pop_back();// 一开始加了一个空格记得删掉 return s; } };
剑指offer.58(leetcode.151)
- 链接https://leetcode.cn/problems/...
https://leetcode.cn/problems/... - 解题方法:与上一题类似
leetcode解题代码
class Solution { public: string reverseWords(string s) { s += " "; string temp; vector<string> res; for (auto c: s){ if (c == ' '){ if (!temp.empty()){ res.push_back(temp); temp.clear(); } } else temp += c; } s.clear(); reverse(res.begin(), res.end()); for (auto c: res){ s += c + ' '; } s.pop_back(); return s; } };
- ACM模式调试
输入字符串s
the sky is blue
输出
blue is sky the
调试代码
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
string s;
getline(cin, s);
s += ' ';
string temp;
vector<string> res;
for (auto c: s){
if (c == ' '){
if (!temp.empty()){
res.push_back(temp);
temp.clear();
}
}
else temp += c;
}
s.clear();
reverse(res.begin(), res.end());
for (auto c: res){
s += c + ' ';
}
s.pop_back();
cout << s << endl;
return 0;
}
字符串中的其他操作(替换空格,旋转字符串等)
剑指offer.05
- 链接https://leetcode.cn/problems/...
- 解题方法:创新新字符串,遍历原字符串找到空格替换即可
leetcode解题代码
class Solution { public: string replaceSpace(string s) { string res; for (auto c: s){ if (c == ' '){ res += "%20"; } else res += c; } return res; } };
leetcode.796
- 链接https://leetcode.cn/problems/...
- 解题方法:如果字符串goal能通过字符串s旋转得到
那么字符串goal一定是字符串s+s的字串,时间复杂度为O(n^2)
(本题可以用KMP和字符串哈希求解,时间复杂度可以降到O(n)) leetcode解题代码
class Solution { public: bool rotateString(string s, string goal) { if (s.size() != goal.size()) return false; s += s; return s.find(goal) != std::string::npos; } };
剑指offer.58
- 链接https://leetcode.cn/problems/...
- 解题方法:整体旋转
分别旋转前半部分和后半部分 leetcode解题代码
class Solution { public: string reverseLeftWords(string s, int n) { reverse(s.begin(), s.end()); reverse(s.begin(), s.end() - n); reverse(s.end() - n, s.end()); return s; } };
解题参考:https://www.acwing.com/
刷题顺序参考:https://www.programmercarl.com/