一些常见的算法题目

合法的出栈序列

已知1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，返回等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法？

bool check(stack<int> &s){
    stack<int> s1;
    int n = s.size();
    for(int i=1;i<=n;i++){
        s1.push(i);
        while (s1.size() > 0 && s1.top() == s.top()){
            s1.pop();
            s.pop();
        }
    }
    if(s.size() == 0){
        return true;
    }
    return false;
}

大数的加法和乘法

这个感觉还是挺常见，说是算法，其实就是模拟手工运算加法乘法，其实并不难。但后来看到别人写的程序，才发现自己写的程序太复杂了，并且思维不是很清晰，所以，参照大佬的算法，又重写写了一下。
大数加法的代码如下。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
using namespace std;

int main(int argc, char const *argv[])
{
    string s1,s2;
    while(cin>>s1>>s2){
        regex number("[0-9]*");
        if(!regex_match(s1,number) || !regex_match(s2,number)){
            cout<<"error"<<endl;
            continue;
        }
        reverse(s1.begin(),s1.end());
        reverse(s2.begin(),s2.end());
        if(s1.size() > s2.size()){
            for(int i=0;i<s1.size() - s2.size();i++){
                s2.push_back('0');
            }
        }else if(s1.size() < s2.size()){
            for(int i=0;i<s2.size() - s1.size();i++){
                s1.push_back('0');
            }
        }
        vector<int> v( s1.size() + 1,0);
        for(int i=0;i<s1.size();i++){
            v[i] += s1[i] -  '0' + s2[i] - '0'; 
        }
        for(int i=0;i<v.size() - 1;i++){
            if(v[i] >= 10){
                v[i+1] += v[i] /10;
                v[i] %= 10;
            }
        }
        string res;
        int i;
        for(i=v.size()-1;i>0 && v[i] == 0;i--)
            ;
        for(;i>=0;i--){
            res += (char)(v[i] + '0');
        }
        cout<<res<<endl;
    }
    return 0;
}

大数乘法的代码如下。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(int argc, char const *argv[])
{
    string s1,s2;
    while(cin>>s1>>s2){
        reverse(s1.begin(),s1.end());
        reverse(s2.begin(),s2.end());
        vector<int> v(s1.size() + s2.size(),0);
        for(int i=0;i<s1.size();i++){
            for(int j=0;j<s2.size();j++){
                v[i+j] += (s1[i] - '0') * ( s2[j] - '0' );
            }
        }
        for(int i=0;i<v.size() - 1;i++){
            if(v[i] >= 10){
                v[i+1] += v[i] /10;
                v[i] %= 10;
            }
        }
        string res;
        int i;
        for(i=v.size()-1;i>0 && v[i] == 0;i--)
            ;
        for(;i>=0;i--){
            res += (char)(v[i] + '0');
        }
        cout<<res<<endl;
    }
    return 0;
}

这些代码都是在牛客网上做题的代码，所以代码中有一些和题目相关的内容。