活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题：字符个数统计

用STL的set维护不同字符的个数即可。

#include <iostream>
#include <set>
using namespace std;

int main() {
    string s;
    cin >> s;
    set<char> st;
    for(char x: s) {
        if(x >= 0 && x <= 127)
            st.insert(x);
    }
    cout << st.size() << endl;
    return 0;
}

中等题：删除字符串中出现次数最少的字符

用一个map来记录每个字符出现的次数（当然用数组也完全ok，字符的范围是有限的）。

然后打擂台求一个最小值。

输出的时候当且仅当该字符出现次数大于这个最小值的时候才输出它。

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<char ,int> cnt;
    string s;
    cin >> s;
    for(auto x: s) {
        cnt[x] ++;
    }
    int minv = 20;
    for(auto x: s) {
        minv = min(minv, cnt[x]);
    }
    for(auto x: s) {
        if(cnt[x] > minv) cout << x;
    }
}

困难题：四则运算

这道应该是这周的困难题里最难写的一道，涉及的细节比较多，导致wa了两次才过。

其实就是一个栈的究极运用，不过这道题有括号和“负数”使得它比普通的四则运算模板要难一些。

基本思想就是用一个栈nums存数字，一个栈ops存符号。

那么进行一次计算相当于把nums的栈顶两个元素弹出来，把ops的栈顶元素弹出来，做运算即可。

而只考虑+-*/的话，只要新来的符号优先级不大于上一个符号，我们就可以把上一个符号运算掉。

而如果有括号的话，就要提前把()内部的全部处理完。

而三种括号属实比较麻烦，其实把它们全部统一成()，完全不影响功能，反而会方便处理一些。

然后不难发现，如果遇到有负数的话（例如题给测试数据），只可能是在+-*/(之后有一个-；前面是数字或者右括号的话，-一定都是减号。对于这个细节，用一个bool变量处理一下就好（详见代码里的p）。

最后栈剩下的一定是一些加或减的表达式，按倒着顺序算就行。

#include <iostream>
#include <map>
#include <stack>
using namespace std;
// 计算一次
void compute(stack<int>& nums, stack<char>& ops) {
    int b = nums.top(); nums.pop();
    int a = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();
    if(op == '+') nums.push(a + b);
    if(op == '*') nums.push(a * b);
    if(op == '-') nums.push(a - b);
    if(op == '/') nums.push(a / b);
}
int main() {
    string s;
    cin >> s;
    // 预处理括号
    for(char& c: s) {
        if (c == '{' || c == '[') c = '(';
        else if (c == '}' || c == ']') c = ')';
    }
    map<char, int> val; // 定义优先级
    val['+'] = val['-'] = 1;
    val['*'] = val['/'] = 2;
    stack<int> nums;
    stack<char> ops;
    int n = s.size();
    bool p = false;
    for(int i=0; i<n; i++) {
        char c = s[i];
        if(c >= '0' && c <= '9') {
            int t = c - '0';
            while(i+1 < n && s[i+1] >= '0' && s[i+1] <= '9') {
                t = t*10 + s[i+1]-'0';
                i ++;
            }
            if(p) {
                t = -t;
                p = false;
            }
            nums.push(t);
        } else if(c == '(') {
            ops.push(c);
        } else if(c == ')') {
            while(ops.top() != '(')
                compute(nums, ops);
            ops.pop();
        } else { // 只剩+-*/了
            if((i == 0 || !(s[i-1] >= '0' && s[i-1] <= '9' || s[i-1] == ')')) && c == '-') {
                p = true;
                continue;
            }
            while(!ops.empty() && ops.top() != '(') {
                if(val[ops.top()] >= val[c]) {
                    compute(nums, ops);
                } else break;
            }
            ops.push(c);
        }
    }
    while(!ops.empty()) {
        compute(nums, ops);
    }
    cout << nums.top() << endl;
    return 0;
}

fun fact：这个题对于py选手来说就可以秒了，所以我个人觉得校招如果出这种题是挺不合适的，不如出一些其他的【栈的运用】妙妙题。

s = input()
s = s.replace("{", "(")
s = s.replace("}", ")")
s = s.replace("[", "(")
s = s.replace("]", ")")
print(int(eval(s)))