描述

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

输入

一行数据包括一个较短的字符串和一个较长的字符串，用一个空格分隔，如： 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;
    }
}

描述

给出一个无序的数列，找出其中缺失的第一个正数，要求复杂度为 O(n) 如：[1,2,0]，第一个缺失为3。 如：[3,4,-1,1]，第一个缺失为2。

输入

1,2,0

输出

3

输入样例

1,2,0
3,4,-1,1
-1,-3,-5
1,2,3
-1,-10,0

输出样例

3
2
1
4
1

AC代码：

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

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a;
        a.push_back(0);
        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);
                }
            }
        }

        vector<int>c(a.size()+1);

        for(int i = 0; i < a.size(); i++)
        {
            if(a[i]<=a.size())
                c[a[i]] = a[i];
        }
        for(int i = 1; i < c.size(); i++)
        {
            if(c[i] == 0)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
}

描述

给出三个队列 s1，s2，s3 ，判断 s3 是否是由 s1 和 s2 交叉得来。 如：s1 为 aabcc ， s2 为 dbbca。 当 s3 为 aadbbcbcac 时，返回 true（即将 s1 拆成三部分： aa，bc，c 分别插入 s2 对应位置） 否则返回 false。

输入

aabcc,dbbca,aadbbcbcac

输出

true

输入样例

aabcc,dbbca,aadbbcbcac
aabcc,dbbca,aadbbbaccc
a,b,ab
a,b,ba
a,b,ac
abc,bca,bcaabc
abc,bca,aabbcc

输出样例

true
false
true
true
false
true
false

AC代码：

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

bool crossQueue(string s)
{
    int a = 0,b = 0,c = 0;
    int cnt = 0;
    a = 0;
    cnt = 0;
    for(int i = 0; i<s.length(); i++)
    {
        if(s[i] == ',' )
        {
            if(cnt == 0)
            {
                b = i;
                cnt++;
            }
            else
            {
                c= i;
            }
        }
    }
    string arr1 = s.substr(a,b);
    string arr2 = s.substr(b+1,c-b-1);
    string arr3 = s.substr(c+1,s.length()-c-1);
    int len1 = arr1.length();
    int len2 = arr2.length();
    int len3 = arr3.length();
    if(len3 != len1 + len2)
    {
        return false;
    }
    if(len1 == 0)
    {
        return (arr2 == arr3);
    }
    if(len2 == 0)
    {
        return (arr1 == arr3);
    }
    int dp[len1+1][len2+1];
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= len1; i++)
    {
        if (arr1[i-1] == arr3[i-1])
            dp[i][0] = dp[i - 1][0];
    }
    for (int i = 1; i <= len2; i++)
    {
        if (arr2[i-1] == arr3[i-1])
            dp[0][i] = dp[0][i - 1];
    }

    for (int i = 1; i < len1 + 1; i++)
    {
        for (int j = 1; j < len2 + 1; j++)
        {
            int t = i + j;
            if (arr1[i-1] == arr3[t-1])
            {
                dp[i][j] = dp[i - 1][j] || dp[i][    j];
            }
            if (arr2[j-1] == arr3[t-1])
            {
                dp[i][j] = dp[i][j - 1] || dp[i][j];
            }
        }
    }
    /* for(int i = 0;i<len1+1;i++){
             for(int j = 0;j<len2+1;j++){
                 cout<<dp[i][j]<<" ";
             }
             cout<<endl;

     }*/
    if (dp[len1][len2] == 1)
    {
        return true;
    }
    else return false;
}

int main()
{
    string s;

    while(cin>>s)
    {
        if(crossQueue(s))
        {
            cout<<"true"<<endl;
        }
        else cout<<"false"<<endl;

    }
}

描述

给出一个有序数列随机旋转之后的数列，如原有序数列为：[0,1,2,4,5,6,7] ，旋转之后为[4,5,6,7,0,1,2]。 假定数列中无重复元素，且数列长度为奇数。 求出旋转数列的中间值。如数列[4,5,6,7,0,1,2]的中间值为4。

输入

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

输出

4

输入样例

1
1,2,3
4,5,6,7,0,1,2
12,13,14,5,6,7,8,9,10

输出样例

1
2
4
9

AC代码：

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

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a(0);
        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);
            }
        }
        temp = -1;
        for(int i = 0;i<a.size()-1;i++){
            if(a[i] > a[i+1]){
                temp = i;
            }
        }
        if(temp == -1){
            cout<<a[a.size()/2]<<endl;
        }
        else if(temp >= a.size()/2){
            cout<<a[a.size()/2-temp]<<endl;
        }
        else if(temp < a.size()/2){
            cout<<a[a.size()/2+temp+1]<<endl;
        }
    }
}