网易笔试
时间：2小时
题型：10单选，4算法，2问答
单选
涉及范围：SQL，数据结构，注解，复杂度等
算法题
一
题目大意
给长度为b的数组，求一个最大的正整数d，使得所有的a_{i+1}-a_{i}都能被d整除，若没有则输出-1，n的范围是1e5，数组内数字的范围是1e18
思路
GCD
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
ll a[maxn];
ll gcd(ll a, ll b)
{
return b==0 ? a : gcd(b, a%b);
}
int main()
{
IO;
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ll ans = a[2]-a[1];
int f = 1;
for(int i=3;i<=n;i++)
{
if(a[i]-a[i-1]<=0)
{
f = 0;break;
}
ans = gcd(ans, a[i]-a[i-1]);
}
if(f && ans>0) cout<<ans<<"\n";
else cout<<"-1\n";
return 0;
}
二
题目大意
你是个英雄，需要去打怪，现在有n个怪物，每个怪物都有一个破防能力a和一个伤害值b，打怪的顺序随意，你有个初始的防御值d，若你当前的防御值d大于等于怪物的破防能力，则能够打爆他，不会受到伤害，否则将会受到和怪物伤害值等同的伤害，没经过一次打怪，你的防御值都会+1，问受到的最小伤害总和是多少？
思路
贪心乱搞，只过了80%，后面不够时间了就没搞了
三
题目大意
一个城市有n个人，每个有都有一个编号，从0开始。共有m次聚会，现在有一个病源母体，编号为f，若某个聚会有带有病毒的人才加，则这个聚会所有的人都会被感染，并且它们也会感染别人，问最后有多少人被感染？n的范围是1e5，m是5e3
思路
并查集，将一次聚会的所有人都并在一起，最后统计有多少人的father是病源母体的father即可
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int n, m, f;
int fa[maxn];
int find(int x)
{
int k = x;
while(fa[k] != k)
{
k = fa[k];
}
while(x != fa[x])
{
int t = x;
x = fa[x];
fa[t] = k;
}
return x;
}
void join(int x, int y)
{
fa[find(x)] = find(y);
}
int main()
{
IO;
cin>>n>>m>>f;
for(int i=0;i<=n;i++) fa[i] = i;
while(m--)
{
int q;
cin>>q;
int fi;
cin>>fi;
for(int i=2;i<=q;i++)
{
int x;
cin>>x;
join(fi, x);
}
}
int ans = 0;
int t = find(f);
for(int i=0;i<=n;i++)
{
if(find(i) == t)
ans++;
}
cout<<ans<<"\n";
return 0;
}
四
题目大意
有一个n*m的地图，地图上要么是0要么是1，0是怪物，1是英雄，求每个英雄最近的怪物的距离，若当前点是怪物，则距离为0，最后输出每个点的距离。n和m的范围都是1000
思路
bfs
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int n, m;
char mp[1005][1005];
int ans[1005][1005];
int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
void slove(int x, int y)
{
queue<P> q;
q.push(P(x, y));
while(!q.empty())
{
P p = q.front();
q.pop();
int cx = p.first, cy = p.second;
if(mp[cx][cy] == '0')
{
ans[x][y] = abs(cx-x) + abs(cy-y);
break;
}
for(int i=0;i<4;i++)
{
int nx = cx+dir[i][0], ny = cy+dir[i][1];
if(cx<1 || cx>n || cy<0 || cy>m)continue;
q.push(P(nx, ny));
}
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%s", mp[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j] == '1')
slove(i, j);
for(int i=1;i<=n;i++)
{
printf("%d", ans[i][1]);
for(int j=2;j<=m;j++)
printf(" %d", ans[i][j]);
printf("\n");
}
return 0;
}
问答题
一
函数式编程和面向对象编程的区别，为什么Java8一反常态引入函数式编程？
二
什么是单例模式双重检查加锁机制？解决什么问题？