当前位置:网站首页>Leetcode——344. 反转字符串/541. 反转字符串 II/151. 颠倒字符串中的单词/剑指 Offer 58 - II. 左旋转字符串
Leetcode——344. 反转字符串/541. 反转字符串 II/151. 颠倒字符串中的单词/剑指 Offer 58 - II. 左旋转字符串
2022-07-07 12:15:00 【styfish】
概述
- 这几题都和字符串翻转有关
分析
344
题目要求原地修改,可以考虑使用双指针+swap()函数实现
实际上,内置函数reverse()就是通过这个实现;
541
- 这题,我们利用
reverse()
模拟一下操作即可
151
- 个人认为这是一个技巧题,要能想到使用多次反转的思路
- 首先翻转整个字符串
- 然后在对每个单词进行一次翻转,即可实现最终效果
这里有一个难点在于,第二次翻转如何确定一个单词进行翻转
**剑指 Offer 58 **
- 这题,个人认为也算一个技巧题,和151一样,使用多次翻转的思路
思路
151
第二次翻转如何确定一个单词?
- 我们容易想到利用空格来区分单词,但是根据题目说明:存在前导空格、尾随空格和单词间多个空格,所以这里还是需要仔细处理一下
- 首先我们第一翻转后,题目中的三种特殊空格情况仍然存在,我们可以分情况处理:
- 对于前导空格和单词间的多个空格,我们可以每次确定一个字母后,再去寻找该字母所在的单词
- 而通常也是利用空格来区分单词。但是考虑到末尾可能不存在空格,就无法区分最后一个单词,于是为了统一操作,我们可以在末尾手动添加一个空格
代码
344
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0, right = s.size() - 1; // 双指针
while (left < right) {
swap(s[left++], s[right--]); // STL swap()
}
}
};
541
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size();i += (2 * k)) {
// 模拟操作
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k );
continue;
}
reverse(s.begin() + i, s.begin() + s.size());
}
return s;
}
};
151
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end()); // 先翻转所有字符
s.push_back(' '); // 统一操作,在末尾添加空格
for(int i = 0; i < s.size(); ++i) {
if (s[i] != ' ') {
// 直到出现第一个字母,可以处理前导空格和单词间多个空格
int j = i + 1;
for (; j < s.size(); ++j) {
if (s[j] == ' ') {
// 遇到一个空格,可以确定该单词的前后位置索引了
reverse(s.begin() + i, s.begin() + j); // 再翻转单个单词
i = j; // 继续处理
break;
}
}
}
}
// 去除多余空格。利用双指针法,向前移动
int i = 0, j = 0;
for(;j < s.size(); ++j) {
if (s[j] != ' ')
s[i++] = s[j];
else if(s[j] == ' ' && i > 0 && s[i - 1] != ' ')
s[i++] = ' ';
}
s.resize(i - 1); // 缩小string,留下实际有用的部分
return s;
}
};
小技巧:
直接利用
resize()
来删除末尾的内存
剑指 Offer 58
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.end()); // 第一次翻转整个字符串
int size = s.size();
// 下面两个翻转是为了恢复正常的顺序,如果不懂可以手动模拟一下
reverse(s.begin(), s.begin() + size - n);
reverse(s.begin() + size - n, s.end());
return s;
}
};
边栏推荐
- 杭电oj2092 整数解
- MySQL "invalid use of null value" solution
- Excuse me, I have three partitions in Kafka, and the flinksql task has written the join operation. How can I give the join operation alone
- [fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
- 股票开户首选,炒股交易开户佣金最低网上开户安全吗
- 请问指南针股票软件可靠吗?交易股票安全吗?
- 请问,redis没有消费消息,都在redis里堆着是怎么回事?用的是cerely 。
- Is the spare money in your hand better to fry stocks or buy financial products?
- CSMA/CD 载波监听多点接入/碰撞检测协议
- Best practice | using Tencent cloud AI willingness to audit as the escort of telephone compliance
猜你喜欢
The longest ascending subsequence model acwing 1014 Mountaineering
Introduction to sakt method
Reverse non return to zero code, Manchester code and differential Manchester code of common digital signal coding
Introduction to database system - Chapter 1 introduction [conceptual model, hierarchical model and three-level mode (external mode, mode, internal mode)]
AutoCAD - how to input angle dimensions and CAD diameter symbols greater than 180 degrees?
UML 状态图
2022-7-6 sigurg is used to receive external data. I don't know why it can't be printed out
Social responsibility · value co creation, Zhongguancun network security and Information Industry Alliance dialogue, wechat entrepreneur Haitai Fangyuan, chairman Mr. Jiang Haizhou
Mathématiques avancées - - chapitre 8 différenciation des fonctions multivariables 1
SAKT方法部分介绍
随机推荐
参数关键字Final,Flags,Internal,映射关键字Internal
Take you to master the three-tier architecture (recommended Collection)
杭电oj2092 整数解
Horizontal of libsgm_ path_ Interpretation of aggregation program
How can the PC page call QQ for online chat?
Cargo placement problem
Lavarel之环境配置 .env
Csma/cd carrier monitoring multipoint access / collision detection protocol
Huawei image address
[fortress machine] what is the difference between cloud fortress machine and ordinary fortress machine?
Evolution of customer service hotline of dewu
gvim【三】【_vimrc配置】
课设之百万数据文档存取
. Net core about redis pipeline and transactions
Transferring files between VMware and host
MySQL "invalid use of null value" solution
requires php ~7.1 -&gt; your PHP version (7.0.18) does not satisfy that requirement
oracle 非自动提交解决
用例图
Clickhouse (03) how to install and deploy Clickhouse