<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">先说说为什么开始做leetcode:最近由于同学开始找工作了,发现了很多人都很厉害。自己明年也要找工作,想了想自己的技术,还是需要进行锻炼。然后看到大师兄在看leetcode,而且他也推荐我去看看。我想反正明年我也要找工作,就看看。搜索之后看到一个博客,发现自己的经历还圆圆不够,与时就有了了他从的编码之行。</span>
leetcode_1
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue
",
return "blue is sky the
".
第一次答案是从后往前遍历,然后排除头尾空格符。开始的思路没有那么清晰,是边做边改的:
#include <iostream> #include <string> using namespace std; class Solution { public: void reverseWords(string &s) { string result=""; int last=0; for(int i = s.length()-1;i>=0;i--){ last ++; if(s[i] == ' '){ if(last==1){ result +=""; last = 0; } else{ result += s.substr(i+1,last-1); last = 0; int bools = 10; for(int k=i;k>=0;k--) { if(s[k] != ' ') bools = 1; } if(i!=0 && bools==1) result +=" "; } } else if(i==0) { result +=s.substr(0,last); } if(last<0) break; } s = result; } };
上传成功之后,查看了结果,发现时间为
不太满意,就想换一种方式。
第二种解答:
先对字符串做处理,处理完成之后再进行反转。这次就使用到STL中的Vector
#include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: //注意:当字符串为空时,也会返回一个空字符串 void trim(std::string &s) { if (s.empty()) { } s.erase(0,s.find_first_not_of(" ")); s.erase(s.find_last_not_of(" ") + 1); } void split(std::string& s, std::string& delim,std::vector< std::string >* ret) { trim(s); size_t last = 0; size_t index=s.find_first_of(delim,last); while (index!=std::string::npos) { ret->push_back(s.substr(last,index-last)); last=index+1; index=s.find_first_of(delim,last); } if (index-last>0) { ret->push_back(s.substr(last,index-last)); } } void reverseWords(string &s) { string val = string(""); vector<string> * result = new vector<string>(); string d = string(" "); split(s,d,result); for(int i=result->size()-1;i>=0;i--) { if((*result)[i] =="") continue; val += (*result)[i]; if(i!=0) val += string(" "); } s = val; } };
这次是先取出字符串的头尾空格,然后进行反转。提交之后就发现速度快了很多。
刚刚又突然想起了这个方法中分词那一步做的不够好,产生了许多“”这样的string。于是想改进一下split函数,这样可以减少在reverseWords函数中判端“”,从而提高程序的效率。
void split(std::string& s, std::string& delim,std::vector< std::string >* ret) { trim(s); size_t last = 0; size_t index=s.find_first_of(delim,last); while (index!=std::string::npos) { if((index-last)!=0) ret->push_back(s.substr(last,index-last)); last=index+1; index=s.find_first_of(delim,last); } if (index-last>0) { ret->push_back(s.substr(last,index-last)); } }
总结一下:做事情还是得闲想清楚怎么解决再动手。三思而行,但是三思而行并不意味着做事畏手畏脚,该出手时就出手。而且事后更需要总结反思