就这?搞了半天还没通过,猿辅导算法笔试题

承志
承志
承志
23
文章
0
评论
2021-04-2915:50:18 评论 132 4246字
摘要

本文来看看猿辅导的两道算法笔试题,这两题的难度不大,但是要都做出来却也不简单,废话不多说了,让我们一起来看题目吧。

第一题

时间限制:C/C++ 5秒,其他语言10秒

空间限制:C/C++ 32M,其他语言64M

用全部N(N<=10)个0-9的数字组成一个"有效"整数(即没有前置0的整数),求这些组成的数中能被K(0<K<10^10)整除的最小数字。

输入描述:
输入分两行,第一行输入N, K,第二行输入N个数字。
输出描述:
输出满足条件的最小的数(不含前置0),如果没有满足条件的数输出 -1。
输入例子1:
4 74 0 1 3
输出例子1:
1043
例子说明1:
413 % 7 = 0, 但是有前置0,所以满足条件的最小数是 1043 % 7 = 0。
输入例子2:
1 1420
输出例子2:
0

解法

乍一看这道题很复杂,要把若干数排列到一起,然后还必须是K的倍数,并且要找到最小的这样的组合。

但仔细分析一下会发现全部的难点都集中在找排列上,只要我们能找到全部的组合,哪怕是一个一个枚举也一定可以找到答案。所以剩下的问题就是怎么找到全排列呢?

关于全排列的问题,在LeetCode当中非常常见,前两百题就有好几道,既有递归的算法也有非递归的方法,大家感兴趣可以自行去调研一下。我们之所以不用关心全排列的问题,是因为在C++的STL库当中已经为我们提供了现成的库函数,可以自动生成下一个排列,我们只需要直接调用即可。

在STL中这个函数叫做next_permutation,存放的位置是algorithm这个包,我们只需要在开头将它include进来就可以使用了。

由于这题当中需要找到最小的排列,所以我们可以先将题目给我们的元素进行排序,之后从最小的排列开始枚举,直到找到答案。每次调用next_permutation这个函数,它会返回一个bool值,表示是否还有下一个排列,当返回false的时候表示已经生成了最大的排列。我们可以用一个do while循环来实现,具体细节可以查看代码。

这题有一个小trick,就是K的范围,题目给的范围是,这个范围已经超过了int的界限,所以要用long long。

代码

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <cstdlib>#include <string>#include <map>#include <set>#include <algorithm>#include "time.h"#include <functional>#define rep(i,a,b) for (int i=a;i<b;i++)#define Rep(i,a,b) for (int i=a;i>b;i--)#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)#define mid ((l+r)>>1)#define lson (k<<1)#define rson (k<<1|1)#define MEM(a,x) memset(a,x,sizeof a)#define L ch[r][0]#define R ch[r][1]#define pii pair<int, int>#define LL long long using namespace std;const int N=500005;const long long Mod=99997867;int main() {    LL n, k;    cin >> n >> k;    vector<intv(n);    rep(i, 0, n) {        cin >> v[i];    }    // 排列,从最小排列开始    sort(v.begin(), v.end());    LL res = -1;    do {        // 跳过首位为0的情况        if (v[0] == 0 && n != 1continue;        LL ret = 0;        // 将排列转化成数        rep(i, 0, n) {            ret = ret * 10 + v[i];        }        // 当整除的时候跳出循环        if (ret % k == 0) {            res = ret;            break;        }    }while (next_permutation(v.begin(), v.end()));    printf("%lld
", res);    return 0;}

第二题

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 256M,其他语言512M

小猿在加载一个网页,这个网页共需要N个相关资源,这些资源之间有一些依赖关系。如果这些资源中存在循环依赖,我们认为这个网页不能加载成功,否则可以加载成功。存在循环依赖是指,这些资源中存在资源X,X依赖的资源Y直接或间接依赖于X。

你能帮助小猿判断一下这个网页能否加载成功吗?

输入描述:
第一行输入T(T ≤ 10),表示输入T组数据。每组数据第1行,输入一个数N(1 ≤ N ≤ 500)表示该组case有编号为1~N的N项资源。每组数据第2到 N+1 行,输入一个 N*N 的零一矩阵。矩阵第 i 行第 j 列数字为 a[i][j] 表示编号为 i 的资源是否依赖于编号为 j 的资源,1表示依赖,0表示不依赖。数据保证a[i][i] = 0。
输出描述:
输出包含T行,每行输出对应每组case中是否存在循环依赖。存在输出1,不存在输出0。
输入例子1:
230 1 00 0 11 0 030 1 00 0 00 0 0
输出例子1:
10
例子说明1:
第一组数据:1依赖于2,2依赖于3,3依赖于1,存在循环依赖。第二组数据:只有1依赖于2,不存在循环依赖。

解法

寻找循环依赖的问题,很容易可以想到将依赖看成边来建图,这样循环依赖其实就转化成了有环图,所以这题本质上是一个判断是否有环的问题。判断有环的方式非常简单,我们只需要判断是否存在一个点它存在一条路径可以返回它本身,如果存在,那么就说明有环。

这里的难点在于很多人想不到要将它转化成图来做,也不知道如何存储一张图。不过好在这题的范围不大,只有500,我们用二维数组也存储得下。

当转化成图之后就是一个简单的递归,没有什么难度,不展开细讲了,具体细节可以查看代码。

代码

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <cstdlib>#include <string>#include <map>#include <set>#include <algorithm>#include "time.h"#include <functional>#define rep(i,a,b) for (int i=a;i<b;i++)#define Rep(i,a,b) for (int i=a;i>b;i--)#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)#define mid ((l+r)>>1)#define lson (k<<1)#define rson (k<<1|1)#define MEM(a,x) memset(a,x,sizeof a)#define L ch[r][0]#define R ch[r][1]#define pii pair<int, int>#define LL long long using namespace std;const int N=500005;const long long Mod=99997867;int n, t;int mp[505][505];bool dfs(int target, int cur) {    bool flag = false;    if (mp[cur][target]) return true;    rep(i, 0, n) {        if (mp[cur][i] == 0continue;        flag |= dfs(target, i);        if (flag) return 1;    }    return 0;}int main() {    scanf("%d", &t);    rep(z, 0, t) {        scanf("%d", &n);        MEM(mp, 0);        rep(i, 0, n) {            rep(j, 0, n) {                scanf("%d", &mp[i][j]);            }        }        bool flag = true;        rep(i, 0, n) if (dfs(i, i)) {            puts("1");            flag = false;            break;        }        if (flag) puts("0");        }        return 0;}

这题还有一个坑点在于我的代码提交之后会报内存超界的错误,但实际上我只存储25w个int,不至于内存超界,我检查了很久做了很多尝试也没有发现问题所在,非常恼火。如果有同学知道内存超界的原因,还请后台给我留言。

End.

爱数据网专栏作者:承志

作者介绍:前阿里人,推荐算法专家,一年更新400篇博文的勤奋作者

个人微信公众号:TechFlow(ID:techflow2019)

本文为爱数据网站专栏作者原创文章,未经允许禁止转载,需要转载请微信联系授权(微信号:lovedata0520)

更多文章前往首页浏览http://www.itongji.cn/

  • 我的微信公众号
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: