Leetcode 刷题
题目
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串”abcdefg”和数字2,该函数将返回左旋转两位得到的结果”cdefgab”。
示例1
输入: s = "abcdefg", k = 2 输出: "cdefgab"
|
示例2
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
|
提示
1 <= k < s.length <= 10000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
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; } };
|
思路
不申请额外空间,只在本串上操作:局部反转+整体反转
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
以为这就完了?但实际上这只是一个最简单的引导题,翻转字符串还有很多需要考虑的事情,见题:
精彩的题解:代码随想录
题目
给你一个字符串 s ,逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明:
- 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
- 翻转后单词间应当仅用一个空格分隔。
- 翻转后的字符串中不应包含额外的空格。
示例 1:
输入:s = "the sky is blue" 输出:"blue is sky the"
|
示例 2:
输入:s = " hello world " 输出:"world hello" 解释:输入字符串可以在前面或者后面包含多余的空格,但是翻转后的字符不能包括。
|
示例 3:
输入:s = "the sky is blue" 输出:"blue is sky the"
|
示例4:
输入:s = " Bob Loves Alice " 输出:"Alice Loves Bob"
|
示例5:
输入:s = "Alice does not even like bob" 输出:"bob like even not does Alice"
|
提示
1 <= s.length <= 104
s
包含英文大小写字母、数字和空格 ' '
s
中 至少存在一个 单词
进阶:
- 请尝试使用
*O*(1)
额外空间复杂度的原地解法。
思考:用什么去除空格?
用s.erase()?
仔细琢磨一下erase的时间复杂度,一个erase本来就是O(n),如果循环遍历字符串,代码移除冗余空格的代码时间复杂度为O(n^2)。
erase实现原理题目:数组:就移除个元素很难么?,最优的算法来移除元素也要O(n)
结论
使用双指针法来去移除空格,最后resize(重新设置)一下字符串的大小,就可以做到O(n)的时间复杂度。
void removeExtraSpaces(string& s) { int slowIndex = 0, fastIndex = 0; while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') { fastIndex++; } for (; fastIndex < s.size(); fastIndex++) { if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') { continue; } else { s[slowIndex++] = s[fastIndex]; } } if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { s.resize(slowIndex - 1); } else { s.resize(slowIndex); } }
|
如果使用erase来移除空格:
- leetcode上的测试集里,字符串的长度不够长,如果足够长,性能差距会非常明显。
- leetcode的测程序耗时不是很准确的。
还可以实现反转字符串的功能,支持反转字符串子区间,实现分别在344.反转字符串和541.反转字符串II。
代码如下:
// 反转字符串s中左闭又闭的区间[start, end] void reverse(string& s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { swap(s[i], s[j]); } }
|
本题题解
class Solution { public: void reverse(string& s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { swap(s[i], s[j]); } }
void removeExtraSpaces(string& s) { int slowIndex = 0, fastIndex = 0; while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') { fastIndex++; } for (; fastIndex < s.size(); fastIndex++) { if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') { continue; } else { s[slowIndex++] = s[fastIndex]; } } if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { s.resize(slowIndex - 1); } else { s.resize(slowIndex); } }
string reverseWords(string s) { removeExtraSpaces(s); reverse(s, 0, s.size() - 1); int start = 0; int end = 0; bool entry = false; for (int i = 0; i < s.size(); i++) { if (!entry) { start = i; entry = true; } if (entry && s[i] == ' ' && s[i - 1] != ' ') { end = i - 1; entry = false; reverse(s, start, end); } if (entry && (i == (s.size() - 1)) && s[i] != ' ' ) { end = i; entry = false; reverse(s, start, end); } } return s; }
};
|