class Solution {
public:
void reverseWords(vector<char>& s) {
}
};
186. 反转字符串中的单词 II
给你一个字符数组 s ，反转其中 单词 的顺序。
单词 的定义为：单词是一个由非空格字符组成的序列。s 中的单词将会由单个空格分隔。
必须设计并实现 原地 解法来解决此问题，即不分配额外的空间。
示例 1：
输入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"] 输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
示例 2：
输入：s = ["a"] 输出：["a"]
提示：
1 <= s.length <= 105s[i] 可以是一个英文字母（大写或小写）、数字、或是空格 ' ' 。s 中至少存在一个单词s 不含前导或尾随空格s 中的每个单词都由单个空格分隔原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-17 11:06:18
func reverseWords(s []byte) {
i, j := 0, 0
n := len(s)
for j < n {
if s[j] == ' ' {
reverse(s, i, j-1)
i = j + 1
}
if j == n-1 {
reverse(s, i, j)
}
j++
}
reverse(s, 0, n-1)
}
func reverse(s []byte, left, right int) {
for i := 0; i <= (right-left)/2; i++ {
s[left+i], s[right-i] = s[right-i], s[left+i]
}
}
cpp 解法, 执行用时: 20 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-17 11:03:35
// 两次反转，先整体翻转，再翻转每个单词
class Solution {
public:
void reverseWords(vector<char>& s) {
int left = 0;
int right = 0;
int len = s.size();
while (right < len) {
if (s[right] == ' ') {
Swap(s, left, right - 1);
right++;
left = right;
} else {
right++;
}
}
Swap(s, left, len - 1);
Swap(s, 0, len - 1);
}
void Swap(vector<char>& s, int left, int right) {
char temp;
while (left < right) {
temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 46.6 MB, 提交时间: 2023-10-17 11:02:21
class Solution {
private void reverse(char[] s, int start, int end) {
while (start < end) {
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
public void reverseWords(char[] s) {
// 两次翻转即可，第一次全局翻转，第二次翻转各个单词
int len = s.length;
reverse(s, 0, len - 1);
int start = 0;
for (int i = 0; i < len; i++) {
if (s[i] == ' ') {
// 翻转前面的单词
reverse(s, start, i-1);
start = i + 1;
}
}
// 翻转最后一个单词
reverse(s, start, len - 1);
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 46.6 MB, 提交时间: 2023-10-17 11:01:59
class Solution {
//
public void reverseWords(char[] str) {
int i = 0;
for(int j = 0; j < str.length; j++){ // aTbTc
if(str[j] != ' ') continue;
reverse(str, i, j);
i = j + 1;
}
reverse(str, i, str.length); // aTbTcT
reverse(str, 0, str.length); // cba
}
private void reverse(char[] str, int i, int j){
for(int k = i; k < (i + j) / 2; k++){
char tmp = str[k];
int g = j - 1 - k + i;
str[k] = str[g];
str[g] = tmp;
}
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 21.9 MB, 提交时间: 2023-10-17 10:59:40
class Solution:
def reverseWords1(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
res = ' '.join(''.join(s).split(' ')[::-1]) # 使用了额外空间
for i in range(len(s)):
s[i] = res[i]
# 不适用额外空间
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify str in-place instead.
"""
i = 0
for j in range(len(s)): # aT bT c
if s[j] != ' ': continue
self.reverse(s, i, j) # 倒置每个单词
i = j + 1
self.reverse(s, i, len(s)) # aT bT cT
self.reverse(s, 0, len(s)) # c b a
def reverse(self, s: List[str], i: int, j: int):
for k in range(i, (i + j) // 2):
g = j - 1 - k + i
s[k], s[g] = s[g], s[k]