``` /* Reverse Words in a string */ #include #include #include using namespace std; class Solution { public: /* * @param s: A string * @return: A string * */ string reverseWords(string &s) { vector sub = split(s, " "); reverse(sub); string result = ""; for(int i = 0; i < (int)sub.size(); ++i) { result += sub[i] + " "; } return result.substr(0, result.length()-1); } private: vector split(const string &str, const string &pattern) { //将const string转换成能够进行分割的C风格字符串 char* temp = new char[str.length()+1]; strcpy(temp, str.c_str()); vector result; char* s = strtok(temp, pattern.c_str()); while(s != NULL) { result.push_back(string(s)); s = strtok(NULL, pattern.c_str()); } delete[] temp; return result; } void reverse(vector &vec) { int length = vec.size(); int i = 0, j = length - 1; while(i < j) { string temp = vec[i]; vec[i] = vec[j]; vec[j] = temp; i++; j--; } } }; int main() { string s = " wjj nicholas hehe"; Solution* sol = new Solution(); cout << sol->reverseWords(s) << endl; } /* * 验证一个字符串是否为回文串 * */ #include #include using namespace std; class Solution { public: bool isPalindrome(string &s) { int length = s.length(); for(int i = 0; i < length; i++) { s[i] = tolower(s[i]); } int i = 0, j = length - 1; while(i < j) { if((s[i] < '0' || s[i] > '9') && (s[i] < 'a' || s[i] > 'z')) { i++; continue; } if((s[j] < '0' || s[j] > '9') && (s[j] < 'a' || s[j] > 'z')) { j--; continue; } if(s[i] != s[j]) { return false; } i++; j--; } return true; } }; int main() { Solution* sol = new Solution(); string s = "*"; cout << sol->isPalindrome(s) << endl; } /* * 最长回文子串 * */ #include #include using namespace std; class Solution { public: string longestPalindrome(string &s) { int length = s.length(); if(length == 0) return 0; int res = 1; string result = s.substr(0, 1); //辅助变量 int m, n, tempLength; string tempStr; for(int i = 0; i < length; i++) { //情况一:以当前字符为中心的回文串 m = i - 1, n = i + 1; tempLength = 1; string tempStr = s.substr(i, 1); while(m >= 0 && n <= length-1 && s[m] == s[n]) { tempStr = s.substr(m, n - m +1); tempLength += 2; m--; n++; } if(tempLength > res) { res = tempLength; result = tempStr; } //情况二:回文长度为偶数的情况 m = i, n = i + 1; tempLength = 0; tempStr = s.substr(i, 1); while(m >= 0 && n <= length - 1 && s[m] == s[n]) { tempStr = s.substr(m, n - m + 1); tempLength += 2; m--; n++; } if(tempLength > res) { res = tempLength; result = tempStr; } } return result; } }; int main() { Solution* sol = new Solution(); string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"; cout << sol->longestPalindrome(s) << endl; } /* replace blank */ #include using namespace std; class Solution { public: int replaceBlank(char string[], int length) { if(length == 0) return 0; int count = 0; for(int i = 0; i < length; i++) { if(string[i] == ' ') count++; } int i = length - 1, j = length + 2 * count - 1; while(i < j) { if(string[i] != ' ') { string[j] = string[i]; i--; j--; } else { string[j] = '0'; string[j-1] = '2'; string[j-2] = '%'; j = j - 3; i--; } } return length + 2 * count; } }; int main() { Solution* sol = new Solution(); char s[] = "hello world "; cout << sol->replaceBlank(s, 11) << endl; } /* length of last word */ #include #include #include #include using namespace std; class Solution { public: int lengthOfLastWord(string &s) { if(s.length() == 0) return 0; vector vec = split(s, " "); int length = vec.size(); return vec[length-1].length(); } private: vector split(const string &s, const string &pattern) { char *str = new char[s.length()+1]; strcpy(str, s.c_str()); vector res; char* temp = strtok(str, pattern.c_str()); while(temp != NULL) { res.push_back(string(temp)); temp = strtok(NULL, pattern.c_str()); } delete[] temp; return res; } }; int main() { string s = "Hello World"; Solution* sol = new Solution(); cout << sol->lengthOfLastWord(s) << endl; } /* count and say */ #include #include #include #include using namespace std; class Solution { public: string countAndSay(int n) { if(n == 1) return "1"; string s = "1"; for(int i = 2; i <= n; i++) { s = getNextString(s); } return s; } private: string getNextString(string str) { int length = str.length(); int i = 0; string result; while(i < length) { string temp = str.substr(i, 1); int count = 0; while(i < length && str.substr(i, 1) == temp) { count++; i++; } char t[length]; sprintf(t, "%d", count); result = result + string(t) + temp; } return result; } }; int main() { Solution* sol = new Solution(); cout << sol->countAndSay(5) << endl; } ```

“经典算法解题实战”实验报告