刷leetcode的第一道题——Reverse Words in a String

时间:2021-09-28 06:24:14

好久没在Online Judge上做题了,今晚7点就要做阿里校招的在线笔试了,前两个多小时去leetcode做了一道字符串的题,好多潜在的trick,还好在WA了两次后终于AC了。

Leetcode第一题Reverse Words in a String,题目很简单:

Given an input string, reverse the string word by word.

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

第一次没点题目的详细说明,总结trick:

1、前导和后导空格需要去掉,中间多个空格只能保留一个(话说这还是我上次实习面有道的一道题目)

2、字符串只有空格时,返回""


下面贴上代码,基本上用到的字符串函数都是自己手动实现的(除memmove外),Leetcode的接口居然定义的是string,下面代码的实现都是char*

class Solution {
public:
void reverseWords(string &s) {
if(s.length() == 0 || s == " "){
s = "";
return;
}
int cnt = 0;
for(int i = 0 ; i < s.length(); i ++){
if(s[i] == ' ')
cnt ++;
else
break;
}
if(cnt == s.length()){
s = "";
return;
}
char str[10240];
strcpy(str ,s.c_str());
strtrim(str);
int len = strlength(str);

int begin = 0;
for (int i = 0; i < len; i ++) {
if (str[i] == ' ') {
reverse(str,begin,i - 1);
begin = i + 1;
}
}
reverse(str, begin, len - 1);
reverse(str,0,len-1);
for (int i = 0; i < len ; i ++) {
s[i] = str[i];
}
s.resize(len);
}

int strlength(const char *str){
const char *pstr = str;
while (*pstr ++ != '\0');
return pstr - str - 1;
}

void swap(char &a,char &b) {
char tmp = a;
a = b;
b = tmp;
}

void strtrim(char *str){//去除空格
char *pstr = str;
int len = strlen(str);
int from = 0, to = 0;
while(*pstr == ' ') {
pstr++;
from ++;
}
pstr = str + len - 1;
while(*pstr == ' ') {
pstr --;
to ++;
}
memmove(str,str+from,len - from - to);
*(str + len - from - to) = '\0';
pstr = str;
char *ts = str;
while(*pstr != '\0'){
if(*pstr != ' '){
*ts = *pstr;
ts++;
pstr++;
}else{
while(*pstr == ' ') pstr ++;
*ts ++ = ' ';
}
}
*(ts++) = '\0';
}

void reverse(char *str, int from, int to) {
char *pbegin = str + from;
char *pend = str + to;
while (pbegin <= pend) {
swap(*pbegin++, *pend --);
}
}
};


代码写的不好,'\0'截断问题谁能给指导一下。