【LeetCode】String

[227] Basic Calculator II [Medium]

实现一个简单的计算器，可以+，-，*，/。

用一个数组存数，遇到+， - 就放进数组；遇到 *， / 就先计算好，再放进数组。

用char op存当前数之前的运算符。

 //author: Wanying Zhang

 class Solution {

 public:

     int calculate(string s) {

         int digit = ;

         int ans = ;

         vector<int> tmp;

         char op = '+'; //op marks pre operator to determine how to deal current digit.

         for (int i = ; i < s.size(); ++i) {

             //if (s[i] == ' ') continue;  // what if the last character is ' '

             if (isdigit(s[i])) {

                 digit = digit *  + (s[i] - '');

             }

             if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == s.size()-) {

                 if (op == '+') {

                     tmp.push_back(digit);

                 }

                 if (op == '-') {

                     tmp.push_back((-) * digit);

                 }

                 if (op == '*' || op == '/') {

                     tmp.back() = op == '*' ? tmp.back() * digit : (tmp.back() / digit);

                 }

                 op = s[i];

                 digit = ;

             }

         }

         for (int i = ; i < tmp.size(); ++i) {

             ans += tmp[i];

         }

         return ans;

     }

 };

[434] Number of Segments in a String [Easy]

给个字符串，返回里面有几段。（空格分割）

Example:

Input: "Hello, my name is John"

Output: 5

 class Solution {

 public:

     int countSegments(string s) {

         int ans = ;

         istringstream iss(s);

         string seg;

         while (iss >> seg) {

             ans++;

         }

         return ans;

     }

 };

字符串前面加空格。

 class Solution {

 public:

     int countSegments(string s) {

         s = " " + s;

         int ans = ;

         for (int i = ; i < s.size(); ++i) {

             if (s[i-] == ' ' && s[i] != ' ') {

                 ans++;

             }

         }

         return ans;

      }

 };

[91] Decode Ways [Medium]

给个字符串，比如12121这种，问如果用A-Z 26个字母表翻译的话，能有几种翻译方式。

思路就是参考走台阶那个题，一次走一步和一次走两步，有几种走法。注意bug-free，以及要想评价高，就用滚动数组。

 class Solution {

 public:

     int numDecodings(string s) {

         // Write your code here

         // 有很多违规的例子，要注意返回0，比如说空串，第一个字母为0，或者连续两个0，或者存在 30 ，40...这种东西

         if (s.size() ==  || s[] == '') {

             return ;

         }

         int a0 = , a1 = , a2 = , ans = ;

         for (int i = ; i < s.size(); ++i) {

             if (s[i] != '') {

                 if (s[i-] == '' || s[i-] == '' &&  s[i] >= '' && s[i] <= '') {

                     ans = a1 + a2;

                 } else {

                     ans = a2;

                 }

             } else {

                 if (s[i-] != '' && s[i-] != '') {

                     return ;

                 } else {

                     ans = a1;

                 }

             }

             a0 = a1;

             a1 = a2;

             a2 = ans;

         }

         return ans;

     }

 };

[151] Reverse Words in a String [Medium]

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

思路是先反转一遍字符串，然后再每个单词反转一遍。

这个题目对空格输出有要求，不能有连续的空格，串首和串尾都没有空格。

空格搞的非常恶心。去除空格的套路就是流式处理法。

 string s = "asssss kd ds";

 string tmp = "";

 stringstream ss(s);

 while (ss >> tmp) {

     ....

 }

流式处理空格

 class Solution {

 public:

     void reverseWords(string &s) {

         if (s.empty()) { return; }

         reverse(s, , s.size()-);

         int start = , end = -;

         for (int i = ; i < s.size(); ++i) {

             if (s[i] != ' ') {

                 if (i ==  || i- >=  && s[i-] == ' ') { start = i; }

                 if (i == s.size()- || i+ < s.size() && s[i+] == ' ') { end = i; }

                 if (start < end) {

                     reverse(s, start, end);

                     start = end + ;

                 }

             } else {

                 if (i ==  || i == s.size()- || s[i-] == ' ') {

                     s.erase(i--, );

                 }

             }

         }

         if (s.back() == ' ') s.pop_back();

     }

     void reverse(string &s, int start, int end) {

         if(s == "") return;

         while (start < end) {

             swap(s[start++], s[end--]);

         }

     }

 };

[214] Shortest Palindrome [Hard]

给个字符串，问前面最少补几字符能使整个字符串为回文串。

暴力法超时了：找出从第一个字符开始的最长回文串，然后主串之后的那一堆就是要翻转加到字符串前面的东西。

Manacher方法：利用P数组找出一个位置j，使得s[0..j]是最长的回文串。然后翻转后面的。注意下manacher的写法。这个是一个非常好实现的算法。

 class Solution {

 public:

     string shortestPalindrome(string s) {

         if (s.size() == ) return s;

         string ori_str = s;

         s = preProcess(s);

         vector<int> p(s.size(), );

         int mx =, dx = ;

         for (auto i = ; i < s.size(); ++i) {

             if (mx > i) {

                 p[i] = min(p[*dx-i], mx-i);

             } else {

                 p[i] = ;

             }

             while (s[i+p[i]] == s[i-p[i]]) {

                 p[i]++;

             }

             if (i + p[i] > mx) {

                 mx = i + p[i];

                 dx = i;

             }

         }

         int max_len = ;

         for (auto i = ; i < p.size(); ++i) {

             if (i == p[i] && i > max_len) {

                 max_len = i;

             }

         }

         max_len--;  // P[i]-1正好是原字符串中回文串的总长度

         string ss = ori_str.substr(, max_len);

         string need_reverse = ori_str.substr(max_len);

         reverse(need_reverse.begin(), need_reverse.end());

         string ans = need_reverse + ori_str;

         return ans;

     }

     //变成 $#a#b#c#d# 这种模式

     string preProcess(string &s) {

         string tmp = "$#";

         for (int i = ; i < s.size(); ++i) {

             tmp += s[i];

             tmp += "#";

         }

         return tmp;

     }

 };

巴特西

【LeetCode】String

最新文章

热门文章