首页 > 阿里8.19笔试题求第二题AC代码或思路
头像
kakad
编辑于 2020-08-19 23:29
+ 关注

阿里8.19笔试题求第二题AC代码或思路


1.给两个数组a,b和一个数组c,问c是否能由a,b按顺序合并而成
AC代码:
void solution(){
    int N;
    cin>>N;
    std::vector<string> res;
    while(N--){
        int a_size,b_size;
        cin>>a_size>>b_size;
        int c_size = a_size+b_size;
        vector<int> a,b,c;
        while(a_size--){
            int temp;
            cin>>temp;
            a.emplace_back(temp);
        }
        while(b_size--){
            int temp;
            cin>>temp;
            b.emplace_back(temp);
        }
        while(c_size--){
            int temp;
            cin>>temp;
            c.emplace_back(temp);
        }
        int p_a = 0;
        int p_b = 0;
        int p_c = 0;
        if(back(p_a,p_b,p_c,a,b,c))
            res.emplace_back("possible");
        else
            res.emplace_back("not possible");

    }
    for(auto& s:res){
        std::cout<<s<<std::endl;
    }

}
bool back(int p_a, int p_b, int p_c, vector<int>& a,vector<int>& b,vector<int>& c){
    if(p_c>=a.size()+b.size())
        return true;
    if(p_a<a.size()&&a[p_a] == c[p_c]){
        if(back(p_a+1,p_b,p_c+1,a,b,c))
            return true;
    }
    if(p_b<b.size()&&b[p_b] == c[p_c]){
        return back(p_a,p_b+1,p_c+1,a,b,c);
    }
    return false;

}
2.给定一个数组,数组中的每个数字只能和连续相邻的数字组队,且队伍实力由木桶效应决定,即队伍里最小的数代表队伍的实力,求每个队伍人数为i(1<=i<=nums,size())时的实力最强队伍的实力.
30%代码,动态规划,每次求以nums[j]为起点队伍人数为i的队伍的实力时都是根据人数为i-1时转移而来的,dp[j] = std::min(dp[j],nums[j+k-1]),不知道为什么只能过30%,求解答
void solution2(){
        int n;
        cin>>n;
        std::vector<long int> res;
        vector<long int> nums;
        while(n--){
            int temp;
            cin>>temp;
            nums.emplace_back(temp);
        }
        std::vector<long int> dp(nums.size(),INT_MAX);

        for (int i = 1; i <= nums.size(); ++i) {
            long int max_num = INT_MIN;
            for (int j = 0; j < nums.size()-i+1; ++j) {
                dp[j] = std::min(dp[j],nums[j+i-1]);
                max_num = std::max(max_num,dp[j]);
            }
            res.emplace_back(max_num);
        }
        for(int i=0;i<res.size()-1;i++){
            std::cout<<res[i]<<" ";
        }
        std::cout<<res.back();

    }



全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐