题解 | #24点运算#

24点运算

http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d

题目有点问题

对于一个用例 K Q 6 K 明明有解为K-Q/6+K 但是给出的答案是输出 NONE图片说明

代码如下,应该是没问题的,没有什么更好的精妙解法了,差不多是直接暴力的,但是因为总共的选择有限,所以程序运行起来还是很快

#include<bits/stdc++.h>
using namespace std;
map<int,string> revmap;
void coutX(int a,int b,int c,int d,char op1,char op2,char op3){
    string s;
    vector<int> tt{a,b,c,d};
    vector<char> opp{op1,op2,op3};
    for(int i=0;i<4;i++){
        int x=tt[i];
        if(x>=2&&x<=9){
            s=s+to_string(x);
        }else{
            s=s+revmap[x];
        }
        if(i<3){
            s=s+opp[i];
        }
    }
    cout<<s<<endl;
}
int count(int left,int right,char op){
    if(op=='*'){
        return left*right;
    }else if(op=='/'){
        return left/right;
    }else if(op=='+'){
        return left+right;
    }else if(op=='-')return left-right;
    cout<<"出错!"<<endl;
    return 0;
}
bool twentyFour(int a,int b,int c,int d){
    //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl;
    int aa=a,bb=b,cc=c,dd=d;
    vector<char> operatorT={'+','-','*','/'};
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++){
                a=aa,b=bb,c=cc,d=dd;//需要每次都初始化。。。。
                char op1=operatorT[i];
                char op2=operatorT[j];
                char op3=operatorT[k];
                if(i>=2){//第一个运算符为* / 优先级比较高
                    a=count(a,b,op1);
                    if(j>=2||k<2){
                        a=count(a,c,op2);
                        a=count(a,d,op3);
                        if(a==24){
                            coutX(aa,bb,cc,dd,op1,op2,op3);
                            return true;
                        }
                    }else{
                        if(k>=2){
                            c=count(c,d,op3);
                            a=count(a,c,op2);
                            if(a==24){
                                coutX(aa,bb,cc,dd,op1,op2,op3);
                                return true;
                            }
                        }
                    }
                }else{//第一个不为* /
                    if(j>=2){
                        b=count(b,c,op2);
                        if(k>=2){
                            b=count(b,d,op3);
                            a=count(a,b,op1);
                                if(a==24){
                                coutX(aa,bb,cc,dd,op1,op2,op3);
                                return true;
                            }
                        }else{
                            //cout<<b<<" ";
                            a=count(a,b,op1);
                            //cout<<a<<" ";
                            a=count(a,d,op3);
                            //cout<<a<<" ";
                                if(a==24){
                                    //cout<<aa<<op1<<bb<<op2<<cc<<op3<<dd<<endl;
                                coutX(aa,bb,cc,dd,op1,op2,op3);
                                return true;
                            }
                        }
                    }else{
                        if(k>=2){
                            c=count(c,d,op3);
                            a=count(a,b,op1);
                            a=count(a,c,op2);
                                if(a==24){
                                coutX(aa,bb,cc,dd,op1,op2,op3);
                                return true;
                            }
                        }else{
                            a=count(a,b,op1);
                            a=count(a,c,op2);
                            a=count(a,d,op3);
                                if(a==24){
                                coutX(aa,bb,cc,dd,op1,op2,op3);
                                return true;
                            }
                        }
                    }
                }
            }
        }
    }
    return false;
}
int main(){
    vector<string> s(4);
    map<string,int> mp;
    mp.insert(pair<string,int>("10",10));
    mp.insert(pair<string,int>("A",1));
    mp.insert(pair<string,int>("J",11));
    mp.insert(pair<string,int>("Q",12));
    mp.insert(pair<string,int>("K",13));

    revmap.insert(pair<int,string>(10,"10"));
    revmap.insert(pair<int,string>(1,"A"));
    revmap.insert(pair<int,string>(11,"J"));
    revmap.insert(pair<int,string>(12,"Q"));
    revmap.insert(pair<int,string>(13,"K"));
    while(cin>>s[0]>>s[1]>>s[2]>>s[3]){
        if(s[0].size()>2||s[1].size()>2||s[2].size()>2||s[3].size()>2){
            cout<<"ERROR"<<endl;
            continue;
        }
        vector<int> model(4);
        for(int i=0;i<4;i++)
        if(s[i][0]>='2'&&s[i][0]<='9'){
            model[i]=stoi(s[i]);
            //cout<<model[i]<<" ";
        }else{
            model[i]=mp[s[i]];
            //cout<<model[i]<<" ";
        }
        //接下来也许是一个四重循环来排列元素
        /*for(auto x:model){
            cout<<x<<" ";
        }*/
        //cout<<endl;
        bool fin=false;
        for(int i=0;i<4;i++){
            if(fin)break;
            for(int j=0;j<4;j++){
                if(fin)break;
                for(int k=0;k<4;k++){
                    if(fin)break;
                    for(int l=0;l<4;l++){
                        if(fin)break;
                        if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){//每个元素各取一次
                            //cout<<i<<j<<k<<l<<endl;
                            int a=model[i],b=model[j],c=model[k],d=model[l];
                            //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl;
                            if(twentyFour(a,b,c,d)){
                                fin=true;
                            }
                        }
                    }
                }
            }
        }
        if(!fin)//找不到时的输出
        cout<<"NONE"<<endl;
    }
    return 0;
}
全部评论
按题目意思是不考虑运算符优先级的
点赞 回复 分享
发布于 2021-12-05 16:09
老哥看看题目,我当初也犯了这个错误
点赞 回复 分享
发布于 2022-04-07 22:31

相关推荐

面试摇了我吧:啊哈哈面试提前五个小时发,点击不能参加就是放弃
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务