翻转单词顺序 Reverse Words in a String

时间:2022-02-02 18:00:06

问题:Given an input string, reverse the string word by word. For example,

Given s = "the sky is blue",
return "blue is sky the".

思路:两轮翻转。第一次整个串彻底反转,第二次逐个单词自身翻转。

输入用例:

输入数据的细节特别重要。开头有空格、结尾有空格、多个空格并列。

class Solution {
public:
void reverseWords(string &s) {
int n = s.size();
if(n == 0)
return;

string A = "";
int idx, left, right;
right = n-1;
while(right >= 0 && s[right] == ' ') //去除右侧空格
right--;
if(right < 0)
{
s = "";
return;
}
idx = 0;
while(idx <= right && s[idx] == ' ') //去除左侧空格
idx++;

while(idx <= right)
{
if(s[idx] != ' ' || s[idx-1] != ' ') //拷贝字符和单空格
A += s[idx];
idx++;
}

n = A.size();
reverse(A, 0, n-1);

idx = 0;
while(idx < n)
{
left = idx;
while(idx < n && A[idx] != ' ')
idx++;
right = idx-1;
reverse(A, left, right);
idx++; //跳过空格
}

s = A;
}

void reverse(string &s, int left, int right)
{
while(left < right)
swap(s[left++], s[right--]);
}
};

下面是jobduOJ的程序,注意:如果要键盘录入一个字符串,其中含有空格,那么最好用gets(str)。

# include<stdio.h>
# include<string.h>
# include<malloc.h>

int reverse(char *str, int left, int right) //添加两个参数来控制翻转位置
{
if(left<0 || left>right || right>strlen(str)-1) //合法性检查
return 0;
char tmp;
while(left<right) //左右游标控制
{
tmp = str[left];
str[left] = str[right];
str[right] = tmp;
left++;
right--;
}
return 1; //学会返回函数执行状态
}

void re_order(char *str)
{
int len = strlen(str);
int i=0,j=0;
while(j<len)
{
while(str[j] != ' ' && str[j] !='\0') //操作检查和合法性检查
{
j++;
}
reverse(str, i, j-1);
j++;
i = j;

}
}

int main()
{
char a[50000];
while(gets(a))
{
reverse(a, 0, strlen(a)-1);
re_order(a);
printf("%s\n",a);
}
return 1;
}