注重medium先不做hard吧
- to do
anagram写过了
1] Count and Say
** 1.naive的模拟，73%**
string countAndSay(int n) {
if (n<2) return "1";
string read ="1", write = "";
char last = '\0';
int ct = 0;
for (int i=1; i<n; ++i) {
for (int j=0; j<read.size(); ++j ) {
if (read[j]!=last) {
if (last!='\0') {
write.push_back(ct+'0');
write.push_back(last);
}
last = read[j];
ct = 1;
} else {
++ct;
}
}
write.push_back(ct+'0');
write.push_back(last);
read = write;
write = "";
last = '\0';
ct = 0;
}
return read;
}
2. 内置STL
auto nexti = find_if(i, curr.end(), bind1st(not_equal_to<char>(), *i));
- findif (iterator start, iterator end, unary operation) :
within [first, end),
-> return the iterator pointing to the first elem that returns T under the unary operation,
-> else return end - bind1st/bind2nd(const Operation& op, const T& x)
- not_equal_to<GIVE TYPE HERE>(_, _)
- stringstream
used in original answer, can be used to convert different types into string, eg. ss<<distance(i, nexti)<<*i;
istringstream类是从istream和stringstreambase派生而来, 以此类推见图
void getNext (string& curr) {
string ss;
for (auto i=curr.begin(); i<curr.end();) {
auto nexti = find_if(i, curr.end(), bind1st(not_equal_to<char>(), *i));
ss+= '0'+ distance(i, nexti);
ss+= *i;
i = nexti;
}
swap(curr, ss);
}
string countAndSay(int n) {
string curr = "1";
while (--n) getNext(curr);
return curr;
}
2] Valid Anagram
基本最快的
用 int record[24] = {somenum}; 来确保initialization，内构是第一个设为somenum，其余0
bool isAnagram(string s, string t) {
if (s.length()!=t.length()) return false;
int record[24] = {0};
for (int i=0; i<s.size(); ++i) {
++record[s[i]-'a'];
--record[t[i]-'a'];
}
for(int i=0; i<24; ++i) {
if (record[i]) return false;
}
return true;
}
3】 Simplify Path
自己写没考虑全，mark重写
中间loop可以精简但是考虑到会增加时间。
-
find (iterator begin, iterator end, const char)
returns iterator pointing to found one - distinct from
someStr.find (char c OR string& OR char*, size_t pos=0, size_type n)
pos (op): starting to search from here, default to be 0 if not specified
n (op): len of sequence of chars (needle) to match - also
+=seems work faster thenappend
string simplifyPath(string path) {
stack<string> record;
for (auto i=path.begin(); i<path.end();) {
++i;
auto lenCurr = find(i, path.end(), '/');
string curr = string(i, lenCurr);
if (curr !="." && curr !="") {
if (curr=="..") {
if (!record.empty()) {
record.pop();
}
} else {
record.push(curr);
}
}
i = lenCurr;
}
string ret;
while (!record.empty()) {
ret.insert( 0, record.top());
ret.insert( 0, "/");
record.pop();
}
return ret==""? "/" : ret;
}
4] Length of Last Word
注意去词尾空格就好
int lengthOfLastWord(string s) {
auto i=s.rbegin();
while (i<s.rend() && *i==' ') ++i;
int len = 0;
for (; i<s.rend(); ++i) {
if (*i==' ') break;
else ++len;
}
return len;
}
