今天第一次在leetcode上提交了一个题目,据说这个网站基本上都是名企面试笔试题,今天无意一进去就看到第一题居然就是昨天的腾讯实习生笔试题,赶紧注册了个账号做题。
题目描述:
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) {
string temp;
stack<string> sta;
for(int i=;i<s.length();i++)
{
if(s[i]!=' ')
{
temp+=s[i];
}
else
{
if(temp!="")
sta.push(temp);
temp="";
}
}
if(temp!="")
sta.push(temp);
s="";
while(sta.size()!=)
{
s+=sta.top();
sta.pop();
s+=' ';
}
s+=sta.top();
}
};
不得不说看起来很是正确啊自己也测试了一下各种空格的串,不管是前面后面都正确,但是交上去发现直接RE了。不过还好有提示(这个也是很向面试看齐的,感觉就是我给面试官那份代码,然后面试官问我,要是我输入的是空串你能正确输出吗?)这时候才发现我代码的不足于是乎赶紧加个判断,然后又想到全是空格的串会不会有问题?果然又发现了一个错误。。。再三检查后提交AC:
class Solution {
public:
void reverseWords(string &s) {
if(s=="")
return ;
string temp;
stack<string> sta;
for(int i=;i<s.length();i++)
{
if(s[i]!=' ')
{
temp+=s[i];
}
else
{
if(temp!="")
sta.push(temp);
temp="";
}
}
if(temp!="")
sta.push(temp);
s=""; while(sta.size()>)
{
s+=sta.top();
sta.pop();
s+=' ';
}
if(sta.empty())
{
s="";
}
else
s+=sta.top();
}
};
虽说这是一道不难的题目,但是也很好的训练了思维的严密性,还是很有帮助的。但是个人感觉leetcode的这种模式以及题目资源比较国内主要面向竞赛的oj来说还是很有优势的,也推荐各位找工作的博友可以一起刷刷题,巩固一下基础。
------------------------------------------update 20141122-----------------------------------------------------
python版,一行代码解决
class Solution:
# @param s, a string
# @return a string
def reverseWords(self, s):
return " ".join(s.split()[::-1]) def main():
s = Solution()
print s.reverseWords("the sky is blue") if __name__ == '__main__':
main()