字符串

344. 反转字符串

题目难度：简单用时： 4 分钟标记：完成

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0,j=s.size()-1; i < s.size() / 2 ; ++i,j--) {
            swap(s[i],s[j]);
        }
    }
};

541. 反转字符串 II

题目难度：简单用时： 9 分钟标记：完成

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i+=2*k) {
            if (s.size() - i >= k)
                reverse(s.begin()+i,s.begin()+i+k);
            else reverse(s.begin()+i, s.end());
        }
        return s;
    }

};

剑指 Offer 05. 替换空格

题目难度：简单用时： 11 分钟标记：完成

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int fast = s.size() - 1;
        //计算空格数量,resize
        for (auto x:s) {
            if (x == ' ')count++;
        }
        count = s.size() + count * 2;
        s.resize(count);
        //双指针移动
        count--;
        while (fast >= 0)
        {
            if (s[fast] == ' ')
            {
                s[count--] = '0';
                s[count--] = '2';
                s[count--] = '%';
                fast--;
            } else s[count--] = s[fast--];
        }
        return s;
    }
};

151. 反转字符串中的单词

题目难度：中等用时： 30 分钟标记：完成

class Solution {
public:
    string reverseWords(string s) {

        /*
         *
         * 1.移除字符串多余空格
         * 2.翻转单词
         * 3.翻转字符串
         */

        //1.移除字符串多余空格 双指针
                int slow =0, fast=0;
        s.push_back(' ');
        while (s[fast] == ' ')fast++;
        while (fast < s.size()-1)
        {
            if (s[fast] == ' ' && s[fast+1] == ' ') fast++;
            else s[slow++] = s[fast++];

        }
        s.resize(slow);

        //2.翻转单词
        int last = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (i == s.size() - 1) std::reverse(s.begin()+last, s.end());
            else if(s[i] == ' ')
            {
                std::reverse(s.begin()+last, s.begin()+i);
                last = i+1;
            }
        }

        //3.翻转字符串
        std::reverse(s.begin(), s.end());
        return s;
    }
};

剑指 Offer 58 - II. 左旋转字符串

题目难度：简单用时： 2 分钟标记：完成

//剑指 Offer 58 - II. 左旋转字符串
 class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.begin()+n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }
};

28. 找出字符串中第一个匹配项的下标（KMP）

见其他附件

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

459. 重复的子字符串

题目难度：简单用时： 5 分钟标记：完成

技巧：两个相同字符串拼接去掉首尾元素，若能找到原字符串s则为循环字符串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string tmp = s;
        s.append(s);
        s.erase(s.size() -1 );
        s.erase(s.begin());
        int fid = s.find(tmp);
        if (fid!=-1) return true;
        else return false;
    }
};

925.长按键入

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        if(typed.size() < name.size()) return false;
        int left = 0, right = 0;
        int cnt = 0;
        char cur = name[left];
        while (left < name.size())
        {
            if(name[left] == cur) cnt++;
            else{
                while (right < typed.size() && typed[right] == cur)
                {
                    cnt--;
                    right++;
                }
                if(cnt > 0 || (right == typed.size() && left < name.size())) return false;
                cur = name[left];
                cnt = 1;
            }
            left++;
        }
        if(cnt > 0) 
        while (right < typed.size() && typed[right] == cur)
        {
            cnt--;
            right++;
        }
        if(cnt > 0 || (right == typed.size() && left < name.size())|| right != typed.size() ) return false;

        return true;
        
    }
};

680. 验证回文串 II

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0 ,right = s.size() - 1;
        int count = 0;
        //left 匹配
        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            } else
            {
                left++;
                count++;
            }
        }
        //right 匹配
        if (count <= 1) return true;

        left = 0 ,right = s.size() - 1;
        count = 0;
        //left 匹配
        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            } else
            {
                right--;
                count++;
            }
        }
        return count <= 1;
    }
};

696. 计数二进制子串（未）

从左往右遍历数组，记录和当前位置数字相同且连续的长度，以及其之前连续的不同数字的长度。举例来说，对于 00110 的最后一位，我们记录的相同数字长度是 1，因为只有一个连续 0；我们记录的不同数字长度是 2，因为在 0 之前有两个连续的 1。若不同数字的连续长度大于等于当前数字的连续长度，则说明存在一个且只存在一个以当前数字结尾的满足条件的子字符串。

题目难度：简单用时： 10分钟标记：未完成

class Solution {
public:
    int countBinarySubstrings(string s) {
        int count = 0 , pre = 0 , cur = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) cur++;
            else
            {
                pre = cur;
                cur = 1;
            }
            if (pre >= cur)count++;
        }
        return count;
    }
};

227. 基本计算器 II

class Solution {
public:
    int calculate(string s) {
        deque <char> mul;
        deque <int> num;
        int point = 0;
        while (point < s.size())
        {
            if(s[point] == '+' ||  s[point] == '-' )
            {
                //运算符入栈
                mul.push_back(s[point++]);
            }
            else if(s[point] == '*' ||  s[point] == '/')
            {
                char ss = s[point];
                //直接计算，计算结果入栈
                int left = num.back();
                num.pop_back();
                //去除空格
                point++;
                while (point < s.size() && s[point] == ' ') point++;
                
                int start = point++;
                while (point < s.size() && s[point] >= '0' && s[point] <= '9') point++;
                int temp = left * stoi(s.substr(start,point - start ));
                if(ss == '*') num.push_back(left * stoi(s.substr(start,point - start )));
                if(ss == '/') num.push_back(left / stoi(s.substr(start,point - start )));
        
            }
            else if(s[point] >= '0' && s[point] <= '9')
            {
                //遇到数字直接入栈
                int start = point++;
                while (point < s.size() && s[point] >= '0' && s[point] <= '9') point++;
                num.push_back(stoi(s.substr(start,point - start)));
            }
            else point++;
        }

        if(num.size() == 1) return num.front();
        while(!mul.empty())
        {
            char ch = mul.front();
            mul.pop_front();
            int left = num.front();
            num.pop_front();
            int right = num.front();
            num.pop_front();
            if(ch == '+') num.push_front(left+right);
            if(ch == '-') num.push_front(left-right);
        }
        return num.front();
    }
};

224. 基本计算器

一个数字绑定一个符号

class Solution {
public:
    int calculate(string s) {
        deque <char> mul;
        deque <int> num;
        int point = 0;
        while (point < s.size())
        {
            if(s[point] == '+' ||  s[point] == '-' || s[point] == '(') mul.push_back(s[point++]);
            else if(s[point] == ')')
            {
                int res = 0;
                int count = 0;
                while (!mul.empty() &&  mul.back() != '(')
                {

                    char ch =mul.back();
                    mul.pop_back();
                    if(ch == '-')res-=num.back();
                    else res+=num.back();
                    num.pop_back();
                }
                num.push_back(res);
                mul.pop_back();
                point++;
            }

            else if(s[point] >= '0' && s[point] <= '9')
            {
                //遇到数字直接入栈
                //cout << " num "<< s[point]<<endl;;
                int start = point++;
                while (point < s.size() && s[point] >= '0' && s[point] <= '9') point++;
                num.push_back(stoi(s.substr(start,point - start)));
                //遇到 
                if(mul.empty() || mul.back() == '(') mul.push_back('+');
      
            }
            else point++;
        }
        int res = 0;
        while(!mul.empty())
        {
            char ch = mul.front();
            mul.pop_front();
            int left = num.front();
            num.pop_front();

            if(ch == '+') res+=left;
            if(ch == '-') res-=left;
        }
        

        return res;
    }
};

409. 最长回文串

题目难度：简单用时： 10分钟标记：完成

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> hash;
        for (int i = 0; i < s.size(); ++i) {
            hash[s[i]]++;
        }
        int res = 0, flag = false;
        for (auto x :hash) {
            if (x.second > 1) res+= x.second / 2 * 2;
            if(x.second % 2 == 1) flag = true;
        }
        return res+flag;
    }
};

7. 整数反转

题目难度：中等用时： 10 分钟标记：完成

class Solution {
public:
    int reverse(int x) {
        if(x == INT_MIN) return 0;
        bool fu = x < 0 ? true : false;
        string nums;
    
        if (fu)  nums = to_string(-x);
        else  nums = to_string(x);

        std::reverse(nums.begin(), nums.end());
        if (nums.size() > 10) return 0;
        if (nums.size() < 10) return fu ? -stoi(nums):stoi(nums);
        int cur = 0;
        string maxs_Z = "2147483647";


        while (cur < 9)
        {
            if (nums[cur] > maxs_Z[cur]) return 0;
            if(nums[cur] < maxs_Z[cur] ) return fu ? -stoi(nums):stoi(nums);
            cur++;
        }
        if (fu && nums[cur] - '0' > 8 ) return 0;
        if (!fu && nums[cur] - '0' > 7 ) return 0;
        return fu ? -stoi(nums):stoi(nums);
    }
};

字符串

28. 找出字符串中第一个匹配项的下标（KMP）​

696. 计数二进制子串（未）​

28. 找出字符串中第一个匹配项的下标（KMP）

696. 计数二进制子串（未）