647. Palindromic Substrings

647. Palindromic Substrings1

思路:

Manacher算法:

回文字符串的判断方式方式会从中心点从发向外不断扩展,Manacher算法给出了缩减了字符串判断回文的重复步骤。其核心思想在于,一段回文s上的呈对称状的左右AB两点,B点的最小回文长度可以通过A点的回文长度和Bs边右边界的长度最小值决定。另外,为了改变回文串长度为偶数和奇数的不同,在每个字符前和后都插入一个#,如此插入后的T的最长回文串半径d,与S最长回文串半径k有, k = [d / 2]

[]向下取整。

Read more

227. Basic Calculator II

227. Basic Calculator II

思路

经典的中缀转后缀练手题,但是我偏不。

在遍历字符串把数字和运算符存储到一个数字栈和运算栈中,考虑到运算顺序是乘除>加减,且左边>右边,所以在压入新运算符op前把栈中优先级大于等于op的运算法弹出,并计算。

遍历完了运算栈可能还有运算符,逆向计算即可。最后数据栈弹出结果就完事。

代码

class Solution {
public:
    using ull = unsigned long long;
    ull func(char c, ull num1, ull num2){
        if(c == '+') return num1 + num2;
        if(c == '-') return num1 - num2;
        if(c == '*') return num1 * num2;
        if(c == '/') return num1 / num2;
        return 0;
    }
    int calculate(string s) {
        s += ']';
        stack<char> op;
        stack<ull> num;
        map<char, int> pri{{'+', 1},{'-', 1},{'*', 2},{'/', 2}};
        ull cal = 0;
        for(auto c : s){
            if(isdigit(c)) cal = cal * 10 + c - '0';
            else{
                if(c == ' ') continue;
                // cout << c << ' ' << cal << endl; 
                num.push(cal); 
                cal = 0;
                if(c == ']') continue;
                
                while(op.size() &&  pri[c] <= pri[op.top()]){
                    int num2 = num.top(); num.pop();
                    int num1 = num.top(); num.pop();
                    num.push( func(op.top(), num1, num2) );
                    op.pop();
                }
                op.push(c);
            }
        }
        // cout << num.size() << ' ' << op.size() << endl;
        while(op.size()){
            int num2 = num.top(); num.pop();
            int num1 = num.top(); num.pop();
            num.push( func(op.top(), num1, num2) );
            op.pop();
        }
        return num.top();


    }
};