注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex151 Reverse Words in a String  

2015-05-20 22:59:10|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.
其实这一题用高级一点儿的算法其实应该很快的,比如c++,python之类的,至于用c是想完全把这些字符串处理的过程自己实现一遍,比如字符串重复空格的去除、内存拷贝等等。然后有点儿恶心的是vs和gcc里面memcpy函数不一样,貌似gcc里面对于地址重合的拷贝会出现bug,或者其他奇怪的原因。见c代码(这份代码完全是原址操作,但是貌似太慢了~~~~都落到js区域去了~~)

void myCopy(char*dis, char*src, int n)
{
//自己写的内存拷贝 表示为了简单,没有检查各种参数限制
int i = 0;
for (i = 0; i<n; i++)
{
dis[i] = src[i];
}
}
void removeRepeat(char*s)
{
//原址去掉空格
int i = 0, count = 0, start, end, len;
for (i = 0; s[i] != '\0'; i++)
{
if (s[i] == ' ')
{
count = 0;
start = i;
end = start + 1;
len = strlen(s);
while (s[end] == ' ')
{
count++;
end++;
}
myCopy(s + start + 1, s + end, (len - end)*sizeof(char));
s[len - count] = '\0';
}
}
}
void reverseWords(char *s) {
int len = strlen(s);

int i = 0;
char sep = ' ';
len = strlen(s);
removeRepeat(s); //原址去掉重复的字符串
len = strlen(s);

//去掉第一个空格
if (s[0] == sep)
{
myCopy(s, s + 1, (len - 1)*sizeof(char));
s[len - 1] = '\0';
}
len = strlen(s); //更新字符串的长度
//去掉最后的空格
if (len <= 0)
return;
if (s[len - 1] == sep)
{
s[len - 1] = '\0';
}
len = strlen(s);

int maxSize = 100;
char *str = (char*)malloc(maxSize * sizeof(char));

int ps = 0;
int pe = 0;
str[0] = sep;
int range = 0;//记录单词的长度
int count = 0;

for (i = 0; i < len;)
{
range = 0;
while (s[ps] != sep&&s[ps] != '\0')
{
//以免只有一个单词一下子就遍历到了字符串尾部
ps++;
range++;
}
//ps 一直是0
if (s[ps] == '\0')
{
break;
}
myCopy(str + 1, s, (range)*sizeof(char));
//第一个位置被空白占了
pe = count + range + 1;
if ((len - pe) <= 0)
{
break;
}

myCopy(s, s + ps + 1, (len - pe)*sizeof(char));//因为多了一个空格
myCopy(s + len - pe, str, (range + 1)*sizeof(char));
count += range + 1;
ps = 0;
i += range + 1;//i在这里增加了,所以在for括号里面就不增加了
}

len = strlen(s);
//去掉第一个空格
if (s[0] == sep)
{
myCopy(s, s + 1, (len - 1)*sizeof(char));
s[len - 1] = '\0';
}
len = strlen(s); //更新字符串的长度
//printf("%s===%d\n", s, len);

}


补充一个c++的代码,这个就简洁多了

class Solution {
public:
void reverseWords(string &s) {
//cout << s << "=========="<< endl;

string result;
int len = s.size();
int i, j;
i = len-1;
char sep = ' ';
while (i >= 0)
{
string temp;
while (i >= 0 && s[i] == sep)
{
i--;//跳过当前读取的空白字符
}
if (i < 0)
{
break; //到最后了,全部是空白了
}
while (i>=0&&s[i] != sep)
{
temp.push_back(s[i]); //一直压栈,直到读取到空白
i--;
}
reverse(temp.begin(),temp.end());
//逆转一下,因为这样是倒着读取的
temp.push_back(' ');
//后面加一个空格
result.append(temp);
}
len = result.size();
if (len>1&&result[len - 1] == sep)
{
result.erase(len-1,1);
}
s = result;
//cout << s <<"==============="<< endl;
}

};


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017