网易2020校招笔试编程参考思路和代码
倒数排列
思路
令给出的排列是，则答案
，可以通过样例和直觉猜出来。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n ; scanf("%d",&n) ;
for(int i = 1;i <= n;i++) {
int x ; scanf("%d",&x) ;
printf("%d ",n - x + 1) ;
}
return 0;
}
小易的英语软件
思路
有多种不同的做法。这里介绍一种比较好理解的：桶排+前缀和。
分数只有 种，考虑对于每一种分数开一个桶
，表示分数等于
的人数，输入的时候就可以搞定。
现在分数不超过 的人数，就是求：
这个用前缀和可以快速求出。
最后要求输出百分数，这个在纸上推一下就好了。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 10000;
int n, m;
int a[MAXN+1];
int buc[151], pre[151];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
++buc[ a[i] ];
}
pre[0] = buc[0];
for (int i = 1; i <= 150; ++i)
pre[i] = pre[i - 1] + buc[i];
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
int x;
scanf("%d", &x);
double ans = 100.0 * (pre[ a[x] ] - 1) / n;
printf("%.6lf\n", ans);
}
return 0;
}
最大公约数
思路
，这是欧几里得算法。那我们只要实现
的计算。
可以直接在输入的时候维护（详见代码）。
参考代码
#include<bits/stdc++.h>
using namespace std;
char s[100005];
long long gcd(long long a,long long b)
{
return a % b == 0 ?b : gcd(b , a % b) ;
}
int main()
{
scanf("%s",s+1) ;
long long a ; cin >> a;
long long b = 0;
for(int i = 1;s[i] != '\0';i++) {
b = (b * 10 + s[i] - '0') % a;
}
cout << gcd(b , a) ;
return 0;
}
按位或
思路
对于每一次询问，我们肯定会选择所有，满足
，即在二进制表达下，
是
的子集。
那么我们可以维护一个数组]，表示所有为
的子集的数字的Or值是多少。每次插入一个数字，如果它没有重复出现过，就枚举它的超集更新答案。询问的时候只需要看
是否等于
就好了。
参考代码
#include<bits/stdc++.h>
using namespace std;
int p[131072] ;
int mx = 131071 ;
int q ;
int main()
{
scanf("%d",&q) ;
while(q--) {
int op , x;scanf("%d%d",&op,&x) ;
if(op == 1) {
if(p[x] == x) continue ;
int s = mx ^ x;
for(int i = s ; i ; i = (i - 1) & s) {
p[i ^ x] |= x ;
}
p[x] = x;
}
else {
if(p[x] == x) puts("YES") ;
else puts("NO");
}
}
return 0;
}
放置货物
思路
枚举货物放置的左上角，剩下的只需要检查某个矩形里面有没有障碍物。 把障碍物看成1，空格看成0，维护二维前缀和，就可以快速查询矩形和。如果矩形和是0则可以放置。
参考代码
#include<bits/stdc++.h>
using namespace std;
int n , m , k;
int a[1005][1005];
int c , d;
void solve()
{
scanf("%d%d%d",&n,&m,&k);memset(a , 0 , sizeof(a)) ;
for(int i = 1;i <= k;i++) {
int x , y;scanf("%d%d",&x,&y);
a[x][y] = 1;
}
scanf("%d%d",&c,&d);
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1] ;
}
}
for(int i = 1;i <= n - c + 1 ; i ++) {
for(int j = 1;j <= m - d + 1 ; j++) {
int s = a[i+c-1][j+d-1] - a[i-1][j+d-1] - a[i+c-1][j-1] + a[i-1][j-1] ;
if(!s) {
puts("YES") ;return ;
}
}
}
puts("NO") ; return ;
}
int main()
{
int t ;scanf("%d",&t) ;
while(t--) solve();
}
最大最小值
思路
首先注意到答案按顺序不减。
考虑把数字从大到小插入，当前插入数字u，那么假设某个k满足ans[k] <= u，则u和u之前的数字把序列分成了一段段，k要满足k <= 这些段中最长的。这样处理完毕之后再填入处理过程中没有填的位置。
参考代码
#include<bits/stdc++.h>
using namespace std;
multiset<int> st ;
int n , k;
struct num
{
int v ;
int id;
}h[100005];
bool cmp(num a,num b)
{
return a.v < b.v;
}
int L[100005] , R[100005];
int ans[100005];
int main()
{
scanf("%d",&n) ;
for(int i = 1;i <= n;i++) {
scanf("%d",&h[i].v) ;
h[i].id = i;
}
sort(h + 1 , h + n + 1, cmp) ;
for(int i = 1;i <= n;i++) {
L[i] = i - 1,R[i] = i + 1; ans[i] = 2e9;
}
for(int i = 1;i <= n;i++) {
int a = h[i].id - L[h[i].id] - 1 , b = R[h[i].id] - h[i].id - 1 ;
if(a) st.erase(st.find(a));
if(b) st.erase(st.find(b)) ;
st.insert(a + b + 1) ;
L[R[h[i].id]] = L[h[i].id] ; R[L[h[i].id]] = R[h[i].id] ;
multiset<int>::iterator it = st.end() ; it--;
ans[*it] = min(ans[*it] , h[i].v) ;
}
for(int i = n ; i >= 1;i--){
if(ans[i] == (2e9)) ans[i] = ans[i + 1];
}
for(int i = 1;i <= n;i++) printf("%d ",ans[i]) ;
return 0;
}
序列交换
思路
只要数组中同时出现了奇数和偶数，那么直接对数组进行排序即可。
参考代码
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
const int N = 1e5 + 10;
int a[N];
using namespace std;
int main()
{
int n;
cin >> n;
int odd = 0,even = 0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]%2==0)
even++;
else
odd++;
}
if(even>0 && odd>0)
sort(a,a+n);
for(int i=0;i<n;i++)
{
printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}
数字圆环
思路
首先对数组进行排序，除了最后一个数字，都满足相邻两个数字大于自己
对于最后一个数字，交换最后两个数字，判断是否满足条件即可。
参考代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
scanf("%d",&n);
for (int i = 0;i < n;i++) scanf("%d",&a[i]);
sort(a,a+n);
swap(a[n-2],a[n-1]);
bool f = 0;
for (int i = 0;i < n;i++)
{
int pre = (i-1+n)%n;
int sub = (i+1) % n;
if (a[pre] + a[sub] <= a[i]) f = 1;
}
if (f) puts("NO");
else
{
puts("YES");
}
}
return 0;
}
优秀的01序列
思路
我们对序列不断执行rev操作，得到的一系列序列
。再依次翻转每个序列的每一位，得到一系列序列
例如"110011"可以生成{"110011","1100","11"}与{"001100","0011","00"}
如果是优秀的，当且仅当
是由这两组序列拼接而成，并且第一组序列中最原始的序列
不能接第二组序列中的序列。
可以使用dp来维护上述过程。令f[i][0/1]表示前i位是否优秀，且拼接的最后一个01串是不是初始序列。按定义转移即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
char s[1005] , t[1005];
int h[1005];
const int base = 773117 , mod = 1e9 + 7;
int pr[1005];
int s1[1005] , s2[1005] , len;
int pos[1005];
int n , m;
int ghash(int l,int r)
{
return ((h[r] - 1LL*h[l-1]*pr[r-l+1]) % mod + mod ) % mod;
}
int dp[1005][2];
void solve()
{
scanf("%s",s+1);
scanf("%s",t+1);
n = strlen(s + 1) , m = strlen(t + 1) ;
for(int i = 1;i <= m;i++) h[i] = (1LL * h[i - 1] * base + t[i] - '0') % mod;
int pc = 0;len = 0;
for(int i = 1;i <= n;i++) {
if(s[i] != s[i - 1]) {
int h1 = 0 , h2 = 0;
for(int j = i;j <= n;j++) {
h1 = (1LL * h1 * base + s[j] - '0') %mod;
h2 = (1LL * h2 * base + 1 + '0' - s[j]) % mod;
}
if(!pc) {
++len ; s1[len] = h1 ; s2[len] = h2;
}
else {
++len ; s1[len] = h2 ; s2[len] = h1 ;
}
pos[len] = (n - i + 1) ;
pc ^= 1;
}
}
memset(dp , 0 , sizeof(dp)) ; dp[0][1] = 1;
for(int i = 1;i <= m;i++) {
if(i >= pos[1] && ghash(i - pos[1] + 1 , i) == s1[1] && (dp[i - pos[1]][0] || dp[i - pos[1]][1])) dp[i][1] = 1;
for(int j = 2;j <= len;j++) {
if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s1[j] && (dp[i - pos[j]][0] || dp[i - pos[j]][1])) {dp[i][0] = 1;break;}
}
for(int j = 1;j <= len;j++) {
if(i >= pos[j] && ghash(i - pos[j] + 1 , i) == s2[j] && dp[i - pos[j]][0]) {dp[i][0] = 1;break;}
}
}
if(dp[m][0] || dp[m][1]) puts("YES");
else puts("NO");
return ;
}
int main()
{
int t;scanf("%d",&t) ;
pr[0] = 1;
for(int i = 1;i <= 1000;i++) pr[i] = 1LL * pr[i - 1] * base % mod;
while(t--) solve() ;
return 0;
}
序列维护
思路
注意到如果，那么不管怎么操作都有
。
于是把数字从小到大排序后，每次询问就二分出对应的位置，并把后面的数字全部减一。具体实现可以用树状数组或者更高级的数据结构。
参考代码
#include<bits/stdc++.h>
using namespace std;
int c[200005];
int n , q;
inline int lowbit(int x)
{
return x & (-x) ;
}
void add(int x)
{
while(x <= n) {
c[x]++ ; x += lowbit(x) ;
}
}
int query(int x)
{
int ans = 0;
while(x) {
ans += c[x] ; x -= lowbit(x) ;
}
return ans;
}
int a[200005];
int main()
{
scanf("%d%d",&n,&q) ;
for(int i = 1;i <= n;i++) scanf("%d",&a[i]) ;
sort(a + 1 , a + n + 1) ;
while(q--) {
int x ; scanf("%d",&x) ;
if(x > a[n] - query(n)) {puts("0");continue ;}
int l = 1 , r = n;
while(l < r) {
int mid = (l + r >> 1) ;
if(a[mid] - query(mid) >= x) r = mid ;
else l = mid + 1;
}
printf("%d\n",n - l + 1) ;
add(l) ;
}
return 0;
}
#网易##校招##笔试题目##题解##笔经#
查看9道真题和解析
投递快手等公司10个岗位