描述

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

输入

输入一个整数。范围在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;
    }
}

 

描述

假设一个有序的数组,经过未知次数的旋转(例如0 1 2 4 5 6 7 被旋转成 4 5 6 7 0 1 2),从中查找一个目标值,如果存在,返回其下标,不存在,返回-1。注:假设数组无重复数字

输入

输入一个有序经过旋转的数组和要查找的目标数字,数组中各数字用“逗号”分隔,数组和目标数字用“空格”分隔

输出

一个整数,表示该目标数字的下标(不存在返回-1)

输入样例

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

输出样例

2

AC代码:

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

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

 

描述

有一个不为空且仅包含正整数的数组,找出其中出现频率最高的前 K 个数,时间复杂度必须在 O(n log n) 以内。

输入

一行数据包括两部分,一个正整数数组(数字间 ‘,’ 分隔)和一个正整数 K (1 ≤ K ≤ 数组长度),数组和 K 之间有一个空格。

输出

输出包含前 K 个出现频率最高的数(出现频率相同时,较小的数在前),用 ‘, ‘ 分隔,保证升序排列。

输入样例

1,1,1,2,2,3 2

输出样例

1,2

AC代码:

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

struct  key_value
{
    int num;
    int cnt;
};

int comp(const key_value &a,const key_value &b)
{
    if(a.cnt == b.cnt)
    {
        return a.num<b.num;
    }
    else
        return a.cnt>b.cnt;
}

int main()
{
    vector<int>a(0);
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
        sort(a.begin(),a.end());
        struct key_value book[a.size()+1];
        temp = a[0];
        j = 0;
        for(int i = 0; i<a.size(); i++)
        {
            if(temp == a[i])
            {
                cnt++;
            }
            else
            {
                book[j].num = temp;
                book[j].cnt = cnt;
                j++;
                temp = a[i];
                cnt = 1;
            }
        }
        book[j].num = temp;
        book[j].cnt = cnt;
        j++;
        sort(book,book+j,comp);
        if(num>0)
        {
            for(int i = 0; i<num-1; i++)
            {
                cout<<book[i].num<<",";
            }
            cout<<book[num-1].num<<endl;
        }
    }
}

 

描述

给出一组不重复的正整数,从这组数中找出所有可能的组合使其加合等于一个目标正整数 M,如:

一组数为 1, 2, 3,目标数为 4,那么可能的加合组合为: 1, 1, 1, 1 1, 1, 2 1, 2, 1 1, 3 2, 1, 1 2, 2 3, 1 注意相同的组合数字顺序不同也算一种,所以这个例子的结果是 7 种。

输入

一组连续不重复的 N 个正整数(, 隔开,0<N<100)以及目标正整数(与数组之间用空格隔开)

输出

所有可能的加合等于目标正整数 M 的组合种数

输入样例

1,2,3 4

输出样例

7

AC代码:

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

vector<int>a(0);
int findComb(int k){
    int sum = 0;
    for(int i = 0; i < a.size();i++){
        if(k-a[i] == 0){
            sum++;
            break;
        }
        if(k-a[i]>0){
            sum = sum +findComb(k-a[i]);
        }
        if(k-a[i]<0){
            break;
        }
    }
    return sum;
}


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

 

描述

给定任意一个较短的子串,和另一个较长的字符串,判断短的字符串是否能够由长字符串中的字符组合出来,且长串中的每个字符只能用一次。

输入

一行数据包括一个较短的字符串和一个较长的字符串,用一个空格分隔,如: ab aab bb abc aa cccc uak areuok

输出

如果短的字符串可以由长字符串中的字符组合出来,返回字符串 “true”,否则返回字符串 “false”,注意返回字符串类型而不是布尔型。

输入样例

a b
aa ab
aa aab
uak areuok

输出样例

false
false
true
true

AC代码:

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

string createStr(string str2,string str1)
{
       int a[130];
       string result = "true";
       memset(a,0,sizeof(a));
       for(int i = 0;i<str1.length();i++){
          a[int(str1[i])]++;
       }
       for(int i = 0;i<str2.length();i++){
          a[int(str2[i])]--;
          if(a[int(str2[i])] < 0){
             result =  "false";
          }
       }
       return result;

}

int main()
{
    int k = 0;
    string s1,s2;
    while(cin>>s1>>s2)
    {
         cout<<createStr(s1,s2)<<endl;
    }
}

 

描述

在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。 请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入

一个正整数,表示这个楼梯一共有多少阶

输出

一个正整数,表示有多少种不同的方式爬完这个楼梯

输入样例

5
10

输出样例

8
89

AC代码:

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


int climbStairsWays(int num)
{
    int res = 0;
    if(num == 1)
    {
        res = 1;
    }
    else if(num == 2)
    {
        res = 2;
    }
    else if(num == 3)
    {
        res = 3;
    }
    else
    {
        int temp1 = 1;
        int temp2 = 2;
        int temp3 = 3;
        num = num - 3;
        while(num--)
        {
            res = temp2 + temp3;
            temp1 = temp2;
            temp2 = temp3;
            temp3 = res;
        }
    }
    return res;
}

int main()
{
    int k = 0;
    while(cin>>k)
    {
        cout<< climbStairsWays(k)<<endl;
    }
}

 

描述

有一行由 N 个数字组成的数字字符串,字符串所表示的数是一正整数。移除字符串中的 K 个数字,使剩下的数字是所有可能中最小的。

假设:

  • 字符串的长度一定大于等于 K
  • 字符串不会以 0 开头

输入

一行由 N 个数字组成的数字字符串(0 < N < 20),和一个正整数 K(K < N),两个数据由空格隔开,如:1432219 3。

输出

移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219,为所有可能中的最小值。

输入样例

1432219 3
10200 1

输出样例

1219
200

AC代码:

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


string removeKdigits(string num, int k)
{
    bool flag = false;//判断是否有前缀0
    string res = "";
    string result = "";
    int temp = 0;
    stack<int>a;
    for(int i = 0; i < num.size(); i++)
    {
        int number = num[i] - '0';
        while( !a.empty() && a.top() > number && k>0)
        {
            a.pop();
            k--;
        }

        a.push(number);
    }
    while(!a.empty() && k>0)
    {
        a.pop();
        k--;
    }
    while(!a.empty())
    {
        temp = a.top();
        stringstream s1;
        string s2;
        s1<<temp;
        s1>>s2;
        res = res+s2 ;
        a.pop();
    }
    for(int i = res.length()-1; i>=0; i--)
    {
        if(res[i]!='0')
        {
            flag = true;
        }
        if(flag)
        {
            result = result + res[i];
        }
    }
    if(result.size() == 0){
        result = "0";
    }
    return result;
}

int main()
{
    string s;
    vector<int>a;
    int k = 0;
    int cnt = 0;
    while(cin>>s>>k)
    {
        cout<< removeKdigits(s,k)<<endl;
    }
}

 

描述

给出一个无序数列,每次只能交换相邻两个元素,求将原数列变成递增数列的最少交换次数。 如:数列:2,3,1,交换3和1后变成:2,1,3;交换1和2之后变成:1,2,3。总共交换2次。

输入

逗号隔开的正整数数列

输出

正整数

输入样例

2,3,1

输出样例

2

思路:

只能交换相邻的数字的话,本质上就是寻找有多少对逆序数对

AC代码:

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

int mySwap(int &a,int &b)
{
    int t;
    t = a;
    a = b;
    b = t;
}

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                if(b>0)
                {
                    a.push_back(b);
                }
            }
        }
        int sum = 0;
        for(int i = 0;i<a.size()-1;i++){
            for(int j = i+1;j<a.size();j++){
                if(a[j] < a[i]){
                    sum++;
                }
            }
        }
       cout<<sum<<endl;
    }
}