首页 > 8.19上午9点阿里笔试 做题结果统计
头像
Miller_next
编辑于 2020-08-19 11:30
+ 关注

8.19上午9点阿里笔试 做题结果统计 投票

请各位带佬帮忙看下,第一题用dfs遍历C数组里A数组所有可能出现的位置,这个代码咋错了?,顺便搞个得分投票:


#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <algorithm>
#include <unordered_set>
#include <cmath>
using namespace std;
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)

int T, n, m, tmp;
vector<int> a, b, c;
vector<vector<int>> allp;
vector<int> path;

bool same(vector<int> a, vector<int> b) {
    if (a.size() != b.size())
        return false;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i])
            return false;
    }
    return true;
}
// 遍历C中A可能的位置
void dfs(int idx, int step) {
    if (step > n)
        return ;
    if (step == n) {
        allp.push_back(path);
        return ;
    }
    for (int i = idx+1; i < n+m; ++i) {
        if (c[i] == a[step]) {
            path.push_back(i);
            dfs(i, step+1);
            path.pop_back();
        }
    }
}

int main()
{
    cin>>T;
    while (T--) {
        cin>>n >> m;
        for (int i = 0; i < n; ++i) {
            cin>>tmp;
            a.push_back(tmp);
        }
        for (int j = 0; j < m; ++j) {
            cin>>tmp;
            b.push_back(tmp);
        }
        for (int k = 0; k < n+m; ++k) {
            cin>>tmp;
            c.push_back(tmp);
        }
        for (int i = 0; i < n+m; ++i) {
            if (c[i] == a[0]) {
                vector<int> newpath;
                path = newpath;
                path.push_back(i);
                dfs(i, 1);
            }
        }
        string ans = "not possible";
        // 对于C数组所有可能的A的位置进行遍历
        for (auto curp:allp) {
            vector<int> curb;
            vector<int> flag(n+m);
            for (auto i:curp)
                flag[i] = 1;
            for (int i = 0; i < n+m; ++i) {
                if (flag[i] == 0)
                    curb.push_back(c[i]);
            }
            if (same(curb, b))  {
                ans = "possible";
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}    


全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐