描述

给出一个无序的数列，找出其中缺失的第一个正数，要求复杂度为 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;
        }
    }
}

好设计是简单的设计。
好设计是解决主要问题的设计。
好的设计并非一定要有趣，但是很难想象完全无趣的设计会是好设计。——Paul Graham《黑客与画家》

描述

两个长度超出常规整形变量上限的大数相减，请避免使用各语言内置大数处理库，如 Java.math.BigInteger 等。

输入

有 N 行测试数据，每一行有两个代表整数的字符串 a 和 b，长度超过百位。规定 a>=b，a, b > 0。 测试结果可以用 linux 小工具 bc进行测试是否正确。

输出

返回表示结果整数的字符串。

输入样例

1231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739870-89513312312312378127398789513312312312378127398789513312312312378127398789513
1231231237812739878951331231231237812739878951331231231237812739878951331230000000000000000000000001-331231231237812739878951331231231

输出样例

1231231237812739878951331231231237812739878951331231231237812650365639018918853110413950365639018918853110413950365639018918853110413950357
1231231237812739878951331231231237812739878951331231231237812739878620099998762187260121048668768770

AC代码：

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

string ASubB(string a,string b){//默认A比B大
     int i = a.size();
     int j = b.size();
     string c;
     for(int k = 0;k<i-j;k++){
        c = c+"0";
     }
     c = c+b;
     //转化为位数相同的A-C的问题
     for(int k = c.size();k>=0;k--){
        if(a[k] == -1){
            a[k] = 0;
            a[k-1] = a[k-1] - 1;
        }
        if(a[k] < c[k]){
            a[k-1]--;
            a[k] = a[k] +10;
        }
        a[k] = a[k] - c[k]+48;
     }
     return a;
}


int main()
{
    string s;
    while(cin>>s){
      int k = s.find("-");
      //cout<<k<<endl;
      string a = s.substr(0,k);
      string b = s.substr(k+1,s.size());
      //cout<<a<<endl;
      //cout<<b<<endl;
cout<<ASubB(a,b)<<endl;
    }
}

It’s not a bug, it’s a feature.——Null

描述

给出N个数字。其中仅有一个数字出现过一次，其他数字均出现过两次，找出这个出现且只出现过一次的数字。要求时间和空间复杂度最小。

输入

输入多个数字，每个数字以空格分开。数字数量 N < 20，输入数字的最大值小于 256.

输出

输出内容为只出现过唯一一次的数字

输入样例

10 10 11 12 12 11 16

输出样例

16

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;
          }
	}
}