牛客春招刷题训练营-2025.3.14题解

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

简单题 字符个数统计

开一个大小为 的数组记录字符是否出现即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    vector<int> a(128);
    for (auto it : s)a[it] = 1;
    cout << count(a.begin(), a.end(), 1);
    return 0;
}

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

开一个数组记录字符的出现次数。
遍历小写字母，如果在字符串中出现过就把出现次数和最小值比较，如果比最小值小就把最小值设为这个字符的出现次数。
最后遍历字符串，输出出现次数不等于最小值的字符。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    vector<int> a(128);
    for (auto it : s)a[it]++;
    int mincount = 1e9;
    for (int i = 'a'; i <= 'z'; i++)
        if (a[i] != 0)
            mincount = min(mincount, a[i]);
    for (auto it : s)
        if (a[it] != mincount)
            cout << it;
    return 0;    
}

困难题 四则运算

栈的应用经典问题，我学数据结构时候手搓的，代码就直接搬过来了。
首先处理字符串，中括号和大括号一律看为小括号。
然后把中缀表达式转成后缀表达式。
初始化一个空栈。
从左到右读入中缀表达式，每次一个字符。

1. 若是运算数，直接输出。
2. 若是(，入栈。
3. 若是)，弹出并输出(前的所有操作符，(出栈并丢弃。
4. 若是操作符
   • 如果栈非空且该字符优先级小于等于栈顶运算符，则栈顶运算符出栈并输出，直到栈为空或优先级大于栈顶运算符或栈顶为(。
   • 入栈。

然后就可以计算后缀表达式了。
初始化一个空栈。

1. 如果是操作数，入栈。
2. 如果是操作符，从栈中取出最上面的两个操作数进行计算，并把计算结果压入栈中。

最后栈中应该只剩下一个元素，直接输出即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll qpow(ll a,ll b) //快速幂，本题数据量小，可以不写
{
    ll res=1;
    while(b)
    {
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
void solve(string in)
{
    stack<char> st;
    vector<string> ans;
    map<char,int> opval={{'^',3},{'*',2},{'/',2},{'+',1},{'-',1}};
    string t;
    bool bnum=0;//遇到数字=1 否则0
    for(auto it:in)
    {
        if(it=='(')
        {
            st.push(it);
            bnum=0;
        }
        else if(it==')')
        {
            if(bnum)
            {
                if(t!="")ans.push_back(t);
                t="";
            }
            while(true)
            {
                if(st.empty())break;
                char c=st.top();
                st.pop();
                if(c=='(')break;
                ans.push_back(""s+c);
            }
        }
        else if(bnum==0)
        {
            t+=it;
            if(isdigit(it))
                bnum=1;
        }
        else if(bnum==1&&(isdigit(it)||it=='.'))
        {
            t+=it;
            if(isdigit(it)||it=='.')
                bnum=1;
        }
        else if(it!=' ')
        {
            if(t!="")ans.push_back(t);
            t="";
            bnum=0;
            while(1)
            {
                if(st.empty()||opval[it]>opval[st.top()])break;
                if(st.top()!='(')ans.push_back(""s+st.top());st.pop();
            }
            st.push(it);
        }
    }
    if(bnum)
    {
        ans.push_back(t);
        bnum=0;
        t="";
    }
    while(!st.empty())
    {
        if(st.top()!='(')ans.push_back(""s+st.top());st.pop();
    }
    auto del=[](string s)->string
    {
        int sign=1;
        bool isnum=0;
        string ans;
        for(auto it:s)
        {
            if(isnum==0&&it=='-')sign=-sign;
            if(isdigit(it)||it=='.')
            {
                ans+=it;
                isnum=1;
            }
        }
        if(isnum)
        {
            if(sign==-1)ans='-'+ans;
            return ans;
        }
        else return s;
    };
    for(int i=0;i<ans.size();i++)ans[i]=del(ans[i]);
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i]=="")
        {
            ans.erase(ans.begin()+i);
            i--;
        }    
    }
    stack<ll> sts;
    for(int i=0;i<ans.size();i++)
    {
        if(isdigit(ans[i].back()))
            sts.push(atoi(ans[i].c_str()));
        else
        {
            ll b=sts.top();sts.pop();
            ll a=sts.top();sts.pop();
            ll c;
            string op=ans[i];
            if(op=="+")c=a+b;
            if(op=="-")c=a-b;
            if(op=="*")c=a*b;
            if(op=="/")
            {
                if(b==0)
                {
                    cout<<"INVALID\n";
                    return;
                }
                else c=a/b;
            }
            if(op=="^")c=qpow(a,b);
            sts.push(c);
        }
    }
    cout<<sts.top()<<"\n";
}
int main()
{
    string in;cin>>in;
    for(auto &it:in)
    {
        if(it=='['||it=='{')it='(';
        if(it==']'||it=='}')it=')';
    }
    solve(in);
    return 0;
}

Python解法，直接把中括号和大括号替换成小括号，使用eval求值。

s=input()
t=""
for i in s:
    if i=='[' or i=="{":
        t+='('
    elif i==']' or i=='}':
        t+=')'
    else:
        t+=i
print(int(eval(t)))