描述

给出一个数组,数组中的数字皆为正整数,除了某一个数字,其他的数字都会出现三次。 找出那个只出现一次的数。

输入

3n+1的正整数数组,使用逗号(,)分隔(n>0)

输出

单独出现的数字

输入样例

2,3,2,2
5,1,4,5,4,5,4

输出样例

3
1

AC代码:

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;
int main()
{

    map<int,int>a;
    int b;
    while(cin>>b)
    {
        a[b]++;
        if (cin.get() == '\n')
            break;
    }
    for(map<int,int>::iterator iter=a.begin();iter!=a.end();iter++){
          if(iter->second == 1){
            cout<<iter->first<<endl;
          }
	}
}

 

描述

我们知道,在逻辑表达式中广泛使用了括号,而括号都是层次化成对出现的。也就是任意左括号都应该存在一个在同一逻辑层级的右括号作为对应。 现在我们有一些仅由括号组成的字符串序列,保证每个字符为大括号”{”,”}”、中括号”[”,”]”和小括号”(”,”)”中的一种。 需要判断给定的的序列是否合法。

输入

一行仅由括号组成的字符串

输出

如果序列合法输出 1,否则输出 0

输入样例

[()]
({[])}
[()]{}

输出样例

1
0
1

小提示

栈的典型应用

AC代码:

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

int main()
{
    string s;
    while(cin>>s)
    {
        stack<char>a;
        bool flag = false;
        for(int i = 0; i<s.length(); i++)
        {
            if(s[i]=='[' || s[i]=='(' || s[i]=='{')
            {
                a.push(s[i]);
            }
            else if(s[i]==']' )
            {
                if(!a.empty() &&a.top()=='[')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
            else if(s[i]==')' )
            {
                if(!a.empty() &&a.top()=='(')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
            else if(s[i]=='}' )
            {
                if(!a.empty() &&a.top()=='{')
                {
                    a.pop();
                }
                else
                {
                    a.push(s[i]);
                }
            }
        }
        if(a.empty())
        {
            cout<<"1"<<endl;
        }
        else cout<<"0"<<endl;
    }
}

 

描述

将 M 个同样的糖果放在 N 个同样的篮子里,允许有的篮子空着不放,共有多少种不同的分法? 比如,把 7 个糖果放在 3 个篮子里,共有 8 种分法(每个数表示篮子中放的糖果数,数的个数为篮子数): 1 1 5 1 2 4 1 3 3 2 2 3 2 5 0 3 4 0 6 1 0 7 0 0

注意:相同的分布,顺序不同也只算作一种分法,如 7 0 0、0 7 0 和 0 0 7 只算作一种。

输入

输入包含二个正整数 M 和 N,以(,)分开,M 表示有几个同样的糖果,N 表示有几个同样的篮子 M与N范围:1 <= M,N <= 100。

输出

输出一个正整数 K,表示有多少种分法。

输入样例

7,3

输出样例

8

AC代码:

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

int calc(int m,int n)
{
    if(m== 0 || n==1)
    {
        return 1;
    }
    //当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
    //当没有苹果可放时,定义为1种放法;
    //递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
    //第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
    if(m < n)
    {
        return calc(m,m);
    }
    else
    {
        return calc(m-n,n)+calc(m,n-1);
        //所有篮子放满和有一个篮子空的情况
        //放满的时候分法和每个篮子拿去一个糖果相同
        //有一个篮子空的时候相当于和这个篮子不存在的时候的分法相同
    }
}


int main()
{
    int m = 0;
    int n = 0;
    while(cin>>m)
    {
        cin.get();
        cin>>n;
        cout<<calc(m,n)<<endl;
    }
}

 

描述

输入32位无符号整数,输出它的反向位。 例,输入4626149(以二进制表示为00000000010001101001011011100101),返回2808701440(以二进制表示为10100111011010010110001000000000)。

输入

一个无符号32位整数字符串

输出

一个无符号32位整数,为输入整数的反向位

输入样例

4626149

输出样例

2808701440

AC代码:

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

int pow2(int a){
     int sum = 1;
     while(a--){
        sum = sum*2;
     }
     return sum;
}



int main()
{
    int number;
    while(cin>>number)
    {
        unsigned int result = 0;
        int cnt = 0;
        unsigned int mask = 1;
    mask = mask << 31;
    while(mask)
    {
        if(number & mask)
        {
            result = result + pow2(cnt) * 1;
        }
        else
        {
            result = result + pow2(cnt) * 0;
        }
        mask = mask>>1;
        cnt++;
    }
    cout<<result<<endl;
    }
}

 

描述

等差数列是常见数列的一种,如果一个数列从第二项起,每一项与它的前一项的差等于同一个常数,这个数列就叫做等差数列,而这个常数叫做等差数列的公差,公差常用字母d表示。即对于数列S,它满足了(S[i]-S[i-1]) = d (i \gt 1)(S[i]S[i1])=d(i>1)。 显然,一个数字无法构成等差数列,而任意两个数字可以形成一个等差数列。 这里给出了一个长度为N(0<N<200)的数字序列,每个位置有一个整数(100整数100),需要找到这个数字序列里包含多少个等差数列,序列顺序固定,无需排序。 输入数据格式:{S[0] S[1] S[2] … S[N]}S[0] S[1] S[2] … S[N](以半角空格符分隔,N>1) 输出数据格式:等差数列数量 MM; 其中数列 SS 的项为整数

请注意时间复杂度的限制。

输入

输入一个数列[ 2 7 4 5 6 ],该数列包含等差数列: [ 2 7 ] [ 2 4 ] [ 2 5 ] [ 2 6 ] [ 7 4 ] [ 7 5 ] [ 7 6 ] [ 4 5 ] [ 4 6 ] [ 5 6 ] [ 2 4 6 ] [ 4 5 6 ]

输出

上例共包含12组等差数列,故应输出12

输入样例

2 7 4 5 6
3 3 3 3

输出样例

12
11

AC代码:

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

int dp[400+1][400+1];

int main()
{
        memset(dp,0,sizeof(dp));
        int b;
        int result = 0;
        vector<int>a;
        bool flag = false;
        while(cin>>b)
        {
            a.push_back(b);
            if (cin.get() == '\n')
                break;
        }
        for(int k = -200; k<=200; k++)
        {
            for(int j = 0; j<a.size(); j++)
            {
                for(int i = j+1; i<a.size(); i++)
                {
                    if(a[j]+k == a[i])
                    {
                        dp[i][k+200] = dp[i][k+200] + dp[j][k+200]+1;
                    }//k+200 因为数组下标必须大于等于0
                }
            }
        }
        for(int i = 0; i<a.size(); i++)
        {
            for(int k = -200; k<=200; k++)
            {
                result = result + dp[i][k+200];
            }
        }
        cout<<result<<endl;
}

 

描述

对于给定的算术表达式,按规则输出计算结果,仅包含加法和大小判断。

输入

一行字符串,为加号、大于、小于( + < > ) 连接的两个不限大小的非负整数。

输出

当符号为 + 时, 计算两个数相加的和, 并以字符串格式返回; 当符号为 < 时, 如果左数小于右数, 返回大写字母字符 Y, 否则返回大写字母字符 N; 当符号为 > 时, 如果左数大于右数, 返回大写字母字符 Y, 否则返回大写字母字符 N。

!!!请同学们尽量使用算法来解决这个问题

输入样例

972919822976663297>74058
875098336507333719633571722631534917759993913379786689>53558270653237768027942884431075534537929401567824882097903948774409200
7625022925148127196027859399571498914361+790786706794530

输出样例

Y
N
7625022925148127196027860190358205708891

AC代码:

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

string func1(string s1,string s2) //大于号
{
    if(s1.length()>s2.length())
    {
        return "Y";
    }
    else if(s1.length()<s2.length())
    {
        return "N";
    }
    else if(s1 == s2)
    {
        return "N";
    }
    else
    {
        int i = 0;
        while(i!=s1.length())
        {
            if((s1[i]-'0') > (s2[i]-'0'))
            {
                return "Y";
            }
            else if((s1[i]-'0') < (s2[i]-'0'))
            {
                return "N";
            }
            i++;
        }
    }
}

string func2(string s1,string s2) //小于号
{
    if(s1.length()>s2.length())
    {
        return "N";
    }
    else if(s1.length()<s2.length())
    {
        return "Y";
    }
    else if(s1 == s2)
    {
        return "N";
    }
    else
    {
        int i = 0;
        while(i!=s1.length())
        {
            if((s1[i]-'0') > (s2[i]-'0'))
            {
                return "N";
            }
            else if((s1[i]-'0') < (s2[i]-'0'))
            {
                return "Y";
            }
            i++;
        }
    }
}

string func3(string s1,string s2) //加号
{
    char temp;
    string result ="";
    bool flag = false;//判断是否有进位
    //已经默认s1>=s2
    while(s1.length()!=s2.length()){
        s2 = "0" + s2;
    }
    int i = s1.length()-1;
    while(i>=0)
    {
        stringstream ss;
        ss.clear();
        string temp = "";
        if(flag == false)
        {
            if((s1[i]-'0') + (s2[i]-'0') > 9)
            {
                flag = true;
                ss.clear();
                ss<<(((s1[i]-'0') + (s2[i]-'0'))-10);
                ss>>temp;
                result =temp + result;
            }
            else
            {
                flag = false;
                ss.clear();
                ss<<((s1[i]-'0') + (s2[i]-'0'));
                ss>>temp;
                result = temp + result;
            }
        }
        else
        {
            if((s1[i]-'0') + (s2[i]-'0')+1 > 9)
            {
                flag = true;
                ss.clear();
                ss<<(((s1[i]-'0') + (s2[i]-'0')+1)-10);
                ss>>temp;
                result =  temp+ result;
            }
            else
            {
                flag = false;
                ss.clear();
                ss<<((s1[i]-'0') + (s2[i]-'0')+1);
                ss>>temp;
                result = temp + result;
            }
        }
        i--;
    }
    if(flag == true)
        {
            result = "1" + result;
        }
    return result;
}

int main()
{
    string s="";
    while(cin>>s)
    {
        int mode = 0;
        string s1 = "";
        string s2 = "";
        for(int i = 0; i<s.length(); i++)
        {
            if(s[i] == '>' || s[i] =='<' ||s[i] =='+')
            {
                s1 = s.substr(0,i);
                s2 = s.substr(i+1,s.length()-i-1);
                if(s[i] == '>')
                {
                    mode = 1;
                }
                else if(s[i] == '<')
                {
                    mode = 2;
                }
                else if(s[i] == '+')
                {
                    mode = 3;
                }
                break;
            }

        }
        if(mode == 1)
        {
            cout<<func1(s1,s2)<<endl;
        }
        else if(mode == 2)
        {
            cout<<func2(s1,s2)<<endl;
        }
        else if(mode == 3)
        {
            if(func1(s1,s2) == "Y")
            {
                cout<<func3(s1,s2)<<endl;
            }
            else
            {
                cout<<func3(s2,s1)<<endl;
            }
        }
    }
}

 

描述

用一个数组表示一群正在排队的小学生,每个小学生用一对整数 H, K 来表示:H 表示这个小学生的身高,K 表示这个小学生前面应该有 K 个人的身高 >= 他。

写一个算法,对给出的一组小学生计算出符合描述的正确排序。

输入

输入为一组整数,以空格分隔:

  • 第 1 个数字表示小学生的数量 n;
  • 从第 2 个数字起,后续的数字两两一组,分别代表每个小学生的 H 和 K 的值

输出

根据输入,按照题目要求对小学生进行排序,每个小学生对应的 H 和 K 值为一组,按组输出,数字间使用空格分隔。

输入样例

6 7 0 4 4 7 1 5 0 6 1 5 2

输出样例

5 0 7 0 5 2 6 1 4 4 7 1

AC代码:

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

typedef struct student{
     int h;
     int k;
};

int comp(const student &a,const student &b){
    if(a.h == b.h){
        return a.k < b.k;
    }
    return a.h>b.h;
}

int main(){
   int n;
   while(cin>>n){
    student stu[n+1];
    for(int i = 0; i<n ;i++){
        cin>>stu[i].h>>stu[i].k;
    }
      sort(stu,stu+n,comp);
     vector<student>a;
     for(int i = 0;i<n;i++){
        a.insert(a.begin()+stu[i].k,stu[i]);
     }
     cout<<a[0].h<<" "<<a[0].k;
     for(int i = 1;i<n;i++){
        cout<<" "<<a[i].h<<" "<<a[i].k;
     }
      cout<<endl;
   }
}

 

描述

实现一个算法,可以将小写数字转换成大写数字。

输入

输入一个整数。范围在0~450亿之间。

输出

输出对应的大写数字,以“元整”结尾。 大写数字要符合汉语读写习惯。

输入样例

0
5
233
1001
40607
8900000000

输出样例

零元整
伍元整
贰佰叁拾叁元整
壹仟零壹元整
肆万零陆佰零柒元整
捌拾玖亿元整

AC代码:

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

char* num[] = {"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};
string func1(string s)
{
    bool isZero = false;
    int k = 0;
    /*while(s[k]-'0'==0)
    {
        s[k]='*';
        k++;
    }*/
    k = s.size()-1;
    while(s[k]-'0'==0)
    {
        s[k]='*';
        k--;
    }
    for(int i = 0; i<s.size(); i++)
    {
        if(s[i]-'0' != 0)
        {
            isZero = false;
        }
        else if(s[i]-'0' == 0 && isZero == true)
        {
            s[i] = '*';
        }
        else if(s[i]-'0' == 0 && isZero == false)
        {
            isZero = true;
        }
    }
    return s;
}


string func(string s)
{
    string result = "";
    int  k = 0;
    for(int i = s.size()-1; i>=0; i--)
    {
        if(s[i] =='*')
        {
            k++;
            continue;
        }
        if(s[i]-'0' >= 0 && s[i]-'0' <= 9)
        {
            if(k == 1 &&s[i]-'0' != 0)
            {
                result ="拾" +result;
            }
            else if(k == 2 &&s[i]-'0' != 0)
            {
                result ="佰" +result;
            }
            else if(k == 3 &&s[i]-'0' != 0)
            {
                result ="仟" +result;
            }
            result =  num[s[i]-'0'] + result ;
            k++;
        }

    }
    return result;

}



int main()
{
    //  char *unit[] = {"十","百","千","万","亿"};仟佰拾
    string s;
    bool isZero = false;
    while(cin>>s)
    {
        string s1 ="";
        string s2 = "";
        string s3 = "";
        string result = "";
        if(s == "0")
        {
            cout<<"零元整"<<endl;
            continue;
        }
        if(s.length()> 0 && s.length()<=4)
        {
            s1 = func1(s);
            s1 = func(s1);
            cout<<s1;
        }
        else if(s.length()> 4 && s.length()<=8)
        {
            s1 = s.substr(s.length()-4,4);
            s1 = func1(s1);
            s1 = func(s1);
            s2 = s.substr(0,s.length()-4);
            s2 = func1(s2);
            s2 = func(s2);
            cout<<s2<<"万";
            cout<<s1;
        }
        else if(s.length()> 8 && s.length()<=12)
        {
            int num = s.length();
            s1 = s.substr(s.length()-4,4);
            s1 = func1(s1);
            s1 = func(s1);
            s2 = s.substr(s.length()-8,4);
            s2 = func1(s2);
            s2 = func(s2);
            s3 = s.substr(0,s.length()-8);
            s3 = func1(s3);
            s3 = func(s3);
            cout<<s3<<"亿";
            if(s2!="")
            {
                cout<<s2<<"万";
            }
            cout<<s1;
        }
        cout<<"元整"<<endl;
    }
}

 

描述

实现一个算法,可以进行任意非负整数的加减乘除组合四则运算。

请注意运算符的优先级。

输入

请输入一行算式,使用空格分隔数字与运算符。

数字为任意非负整数,运算符为+ – * /,不考虑括号。

输出

输出算式的运算结果。如果是小数,请向下取整(包含中间步骤结果)。 如果出现“除0异常”,输出err。

输入样例

3 + 5
12 + 45 / 9
1 / 2
1 / 0
12 + 34 * 56 - 78

输出样例

8
17
0
err
1838

小提示

可以使用栈来解决此类问题。

AC代码:

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

int main()
{
    stack<string>a;
    string num;
    bool flag = false;
    bool err = false;
    string s;
    while(getline(cin,s))
    {
        vector<string>symbol;//用来存符号
        vector<string>number;//用来存数字
        num = "";
        for(int i = 0; i<=s.length(); i++)
        {
            if(s[i] =='+' || s[i] =='-' || s[i] =='*' || s[i] =='/' )
            {
                if(s[i] == '+')
                {
                    symbol.push_back("+");
                }
                else if(s[i] == '-')
                {
                    symbol.push_back("-");
                }
                else if(s[i] == '*')
                {
                    symbol.push_back("*");
                }
                else if(s[i] == '/')
                {
                    symbol.push_back("/");
                }
                continue;
            }
            while(s[i] >='0' && s[i] <= '9')
            {
                num = num + s[i];
                i++;
                flag = true;

            }
            if(flag == true)
            {
                number.push_back(num);
                num  = "";
                flag = false;
            }
        }
        vector<string>b; //存中缀表达式
        vector<string>c;//存后缀表达式
        stack<string>d;
        for(int i = 0; i < symbol.size(); i++)
        {
            b.push_back(number[i]);
            b.push_back(symbol[i]);
        }
        b.push_back(number[number.size()-1]);
        for(int i = 0; i<b.size(); i++)
        {
            if(b[i] == "+" || b[i] == "-" || b[i] == "*" || b[i] == "/")
            {
                if(d.empty())
                {
                    d.push(b[i]);
                }
                else if(d.top() == "+" || d.top() == "-")
                {
                    if(b[i] == "*" || b[i] == "/")
                    {
                        d.push(b[i]);
                    }
                    else
                    {
                        c.push_back(d.top());
                        d.pop();
                        d.push(b[i]);
                    }
                }
                else if(d.top() == "*" || d.top() == "/")
                {

                    if(b[i] == "*" || b[i] == "/")
                    {
                        c.push_back(d.top());
                        d.pop();
                        d.push(b[i]);
                    }
                    else
                    {

                        c.push_back(d.top());
                        d.pop();
                        if(d.empty())
                        {
                            d.push(b[i]);
                        }
                        else
                        {
                            c.push_back(d.top());
                            d.pop();
                            d.push(b[i]);
                        }

                    }

                }
            }
            else
            {
                c.push_back(b[i]);
            }
        }
        while(!d.empty())
        {
            c.push_back(d.top());
            d.pop();
        }
        stack<string>think;
        int num1 = -1;
        int num2 = -1;
        int res = 0;
        string resStr ;
        stringstream ss;
        for(int i = 0; i<c.size(); i++)
        {
            err = false;
            if(c[i] == "+")
            {
                ss << think.top();
                ss >>num2;
                ss.clear();
                think.pop();
                ss << think.top();
                ss >> num1;
                ss.clear();
                think.pop();
                res = num1 + num2;
                ss << res;
                ss >> resStr;
                ss.clear();
                think.push(resStr);
            }
            else if(c[i] == "-")
            {
                ss << think.top();
                ss >>num2;
                ss.clear();
                think.pop();
                ss << think.top();
                ss >> num1;
                ss.clear();
                think.pop();
                res = num1 - num2;
                ss << res;
                ss >> resStr;
                ss.clear();
                think.push(resStr);
            }
            else if(c[i] == "*")
            {
                ss << think.top();
                ss >>num2;
                ss.clear();
                think.pop();
                ss << think.top();
                ss >> num1;
                ss.clear();
                think.pop();
                res = num1 * num2;
                ss << res;
                ss >> resStr;
                ss.clear();
                think.push(resStr);
            }
            else if(c[i] == "/")
            {
                ss << think.top();
                ss >>num2;
                ss.clear();
                think.pop();
                ss << think.top();
                ss >> num1;
                ss.clear();
                think.pop();
                if(num2 == 0){
                    err = true;
                    break;
                }
                res = num1 / num2;
                ss << res;
                ss >> resStr;
                ss.clear();
                think.push(resStr);
            }
            else
            {
                think.push(c[i]);
            }
        }
        if(err){
            cout<<"err"<<endl;
        }
        else{
        cout<<think.top()<<endl;
        err = false;
        }
    }
}

 

描述

给出一个整数数组, 数组中是否存在任意 3 个数 a, b, c 满足 a + b + c = 0? 找出数组中所有满足以上条件的三元组,最后输出这些三元组的个数(包含相同元素的三元组只计算一次)。

输入

一个包含多个整数(正或负)的字符串,每个整数之间用逗号(,)分隔,如:-1,0,1,2,-1,-4。

输出

输入满足加和结果正好等于 0 的三元组的个数,如对于 -1,0,1,2,-1,-4 有 [-1, 0, 1] 和 [-1, -1, 2],所以输出 2

输入样例

-1,0,1,2,-1,-4

输出样例

2

AC代码:

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

int main()
{
    int k ;
    int num;
    string s;
    while(cin>>s)
    {
        bool symbol = true;
        vector<int>a(0);
        int result = 0;
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int a1 = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] =='-'){
                symbol = false;
                i++;
            }
            if(s[i] ==',')
            {
                if(s[k] =='-'){
                symbol = false;
                k++;
            }
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                j = i+1;
            }
            if(flag == true)
            {
                if(symbol == false){
                    b = b*(-1);
                    symbol = true;
                }
                a.push_back(b);


            }
        }
        sort(a.begin(),a.end());
        for(int i = 0;i<a.size()-2;i++){
                if(a1 == a[i] && i!= 0){//防止重复
                    continue;
                }
            a1 = a[i];
            int temp1 = i+1;
            int temp2 = a.size()-1;
            while(temp1 < temp2){
                    if(a[temp1]+a[temp2] + a1==0){
                       // cout<<a1<<" temp1:"<<temp1<<" temp2:"<<temp2<<endl;
                        result ++;
                        while(a[temp1] == a[temp1+1]){//防止重复
                            temp1++;
                        }
                        while(a[temp2] == a[temp2-1]){//防止重复
                            temp2++;
                        }
                        temp1++;
                        temp2--;
                    }
                    else if(a[temp1]+a[temp2] + a1>0){
                        temp2--;
                    }
                    else if(a[temp1]+a[temp2] +a1<0){
                        temp1++;
                    }
            }
        }
        cout<<result<<endl;
    }
}