网易2019秋季校园招聘编程题真题集合

 

 

俄罗斯方块

小易有一个古老的游戏机，上面有着经典的游戏俄罗斯方块。因为它比较古老，所以规则和一般的俄罗斯方块不同。
荧幕上一共有 n 列，每次都会有一个 1 x 1 的方块随机落下，在同一列中，后落下的方块会叠在先前的方块之上，当一整行方块都被占满时，这一行会被消去，并得到1分。
有一天，小易又开了一局游戏，当玩到第 m 个方块落下时他觉得太无聊就关掉了，小易希望你告诉他这局游戏他获得的分数。
 

输入描述:

第一行两个数 n, m
第二行 m 个数，c1, c2, ... , cm ， ci 表示第 i 个方块落在第几列
其中 1 <= n, m <= 1000, 1 <= ci <= n

输出描述:

小易这局游戏获得的分数

示例1

输入

3 9
1 1 2 2 2 3 1 2 3

输出

2

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] a = new int[n];for (int i = 0; i < m; i++) {++a[in.nextInt() - 1];}int min = a[0];for (int i : a) {if (i < min)min = i;}System.out.print(min);}
}

 

瞌睡

 

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

输入描述:

第一行 n, k (1 <= n, k <= 105) ，表示这堂课持续多少分钟，以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数，a1, a2, ... , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数，t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。

 

输出描述:

小易这堂课听到的知识点的最大兴趣值。

示例1

输入

6 3
1 3 5 2 5 4
1 1 0 1 0 0

输出

16

//主要找出连续k分钟最大的“额外知识点分值”import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);intn = in.nextInt();intk = in.nextInt();inta[] = new int[n];intt[] = new int[n];int sum=0;for(inti=0;i<n;i++)a[i] = in.nextInt();for(int i=0;i<n;i++){t[i] = in.nextInt();if(t[i]==1)sum+=a[i];}int max=0;for(int i=0;i<n-k+1;i++){int m=0;for(int j=0;j<k;j++){if(t[i+j]==0)m+=a[i+j];}if(m>max)max=m;}System.out.println(sum+max);}}

 

丰收

 

又到了丰收的季节，恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果园里有N堆苹果，每堆苹果的数量为ai，小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单，所以希望你来替他回答。
 

输入描述:

第一行一个数n(1 <= n <= 105)。
第二行n个数ai(1 <= ai <= 1000)，表示从左往右数第i堆有多少苹果
第三行一个数m(1 <= m <= 105)，表示有m次询问。
第四行m个数qi，表示小易希望知道第qi个苹果属于哪一堆。

 

输出描述:

m行，第i行输出第qi个苹果属于哪一堆。

示例1

输入

5
2 7 3 4 9
3
1 25 11

输出

1
5
3

public static void main(String [] args)  {//时间换空间的思想try (Scanner input = new Scanner(System.in)) {int n = input.nextInt();int count = 0; //保存苹果总数,用于创建数组int[] apple = new int[n+1]; //用数组保存苹果for (int i = 1; i <= n; i++) {apple[i] = input.nextInt();count += apple[i];}int[] arr = new int[count+1];count = 0;    for (int i = 1; i <= n; i++) {for(int j = count+1; j <= apple[i]+count; j++ ) {arr[j] = i;}count += apple[i];}int m = input.nextInt();for (int i = 0; i < m; i++) {System.out.println(arr[input.nextInt()]);}}}

 

整理房间

 

又到了周末，小易的房间乱得一团糟。

他希望将地上的杂物稍微整理下，使每团杂物看起来都紧凑一些，没有那么乱。

地上一共有n团杂物，每团杂物都包含4个物品。第i物品的坐标用(ai,bi)表示，小易每次都可以将它绕着(xi,yi)逆时针旋转，这将消耗他的一次移动次数。如果一团杂物的4个点构成了一个面积不为0的正方形，我们说它是紧凑的。

因为小易很懒，所以他希望你帮助他计算一下每团杂物最少需要多少步移动能使它变得紧凑。

 

输入描述:

第一行一个数n(1 <= n <= 100)，表示杂物的团数。
接下来4n行，每4行表示一团杂物，每行4个数ai, bi，xi, yi, (-104 <= xi, yi, ai, bi <= 104)，表示第i个物品旋转的它本身的坐标和中心点坐标。

 

输出描述:

n行，每行1个数，表示最少移动次数。

示例1

输入

4
1 1 0 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0

输出

1
-1
3
3

说明

对于第一团杂物，我们可以旋转第二个或者第三个物品1次。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <limits.h>
#include <cstdio>
using namespace std;struct Item{int a, b, x, y, state;Item(){state = 0;}void crot(){state = (state + 1) % 4;int dx = a-x, dy = b-y;a = x - dy;b = y + dx;}void input(){cin>>a>>b>>x>>y;state = 0;}bool operator ==(const Item &item2){return a==item2.a && b==item2.b;}Item operator +(const Item &it2){Item res;res.a = a + it2.a;res.b = b + it2.b;return res;}Item operator -(const Item &it2){Item res;res.a = a - it2.a;res.b = b - it2.b;return res;}static bool ortho(const Item &it1, const Item &it2){if(it1.a==0 && it1.b== 0) return 0;if(it2.a==0 && it2.b == 0) return 0;return it1.a * it2.a + it1.b * it2.b == 0;}
};struct Pack{vector<Item> itemList;vector<Item*> itp;int step;Pack(){itemList = vector<Item>(4);itp = vector<Item*>(4, nullptr);for(int i=0; i<4; ++i) itp[i] = &itemList[i];step = INT_MAX;}void input(){for(int i=0; i<4;++i)itemList[i].input();step = INT_MAX;}bool isSqaure(){for(int i=1; i<4; ++i){if(i!=1) swap(itp[i], itp[1]);if(*itp[0]==*itp[1] || *itp[2]==*itp[3]) return 0;if(!(*itp[0] + *itp[1] == *itp[2] + *itp[3])) continue;if(!Item::ortho(*itp[0]- *itp[1], *itp[2] - *itp[3])) continue;if(Item::ortho(*itp[0]- *itp[2], *itp[0] - *itp[3])) return 1;}return 0;}void trySqaure(int rot_idx){for(int i=0; i<4; ++i){if(rot_idx == 0 && isSqaure()){int tmp_step = 0;for(int j=0; j<4; ++j) tmp_step += itemList[j].state;if(step > tmp_step) step = tmp_step;}if(rot_idx > 0) trySqaure(rot_idx - 1);itemList[rot_idx].crot();}}
};int main()
{int n;cin>>n;Pack eRoom;for(int i=0; i<n; ++i){eRoom.input();eRoom.trySqaure(3);cout<<(eRoom.step > 16 ? -1: eRoom.step)<<endl;}
}

 

表达式求值

 

今天上课，老师教了小易怎么计算加法和乘法，乘法的优先级大于加法，但是如果一个运算加了括号，那么它的优先级是最高的。例如：

1 2 3 4

1+2*3=7 1*(2+3)=5 1*2*3=6 (1+2)*3=9

现在小易希望你帮他计算给定3个数a，b，c，在它们中间添加"+"， "*"， "("， ")"符号，能够获得的最大值。

 

输入描述:

一行三个数a，b，c (1 <= a, b, c <= 10)

 

输出描述:

能够获得的最大值

示例1

输入

1 2 3

输出

9

#include<bits/stdc++.h>
using namespace std;int main()
{int a, b, c;cin >> a >> b >> c;int arr[6];arr[0] = a + b + c;arr[1] = a * b * c;arr[2] = a + b * c;arr[3] = a * b + c;arr[4] = (a + b) * c;arr[5] = a * (b + c);int Max = 0;for(int i = 0; i < 6; i++){if(arr[i] > Max)Max = arr[i];}cout << Max << endl;return 0;
}

 

塔

小易有一些立方体，每个立方体的边长为1，他用这些立方体搭了一些塔。

现在小易定义：这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。

小易想让这些塔尽量稳定，所以他进行了如下操作：每次从某座塔上取下一块立方体，并把它放到另一座塔上。

注意，小易不会把立方体放到它原本的那座塔上，因为他认为这样毫无意义。

现在小易想要知道，他进行了不超过k次操作之后，不稳定值最小是多少。

 

输入描述:

第一行两个数n,k (1 <= n <= 100, 0 <= k <= 1000)表示塔的数量以及最多操作的次数。
第二行n个数，ai(1 <= ai <= 104)表示第i座塔的初始高度。

 

输出描述:

第一行两个数s, m，表示最小的不稳定值和操作次数(m <= k)
接下来m行，每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。

示例1

输入

3 2
5 8 5

输出

0 2
2 1
2 3

import java.util.ArrayList;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();//塔数int k = scan.nextInt();//最多可操作数int[] height = new int[n];//塔的高度for (int i = 0; i < n; i++) {height[i] = scan.nextInt();}int count = 0;ArrayList<Integer> list1 = new ArrayList<Integer>();ArrayList<Integer> list2 = new ArrayList<Integer>();for (int i = 0; i < k; i++) {int h = max(height);//找到最高的int l = min(height);//找到最低的if(balance(height[h],height[l])) {break;}count++;height[h]--;height[l]++;list1.add(h+1);list2.add(l+1);}System.out.println(height[max(height)]-height[min(height)]+" "+count);for (int i = 0; i < list1.size(); i++) {System.out.println(list1.get(i)+" "+list2.get(i));}}public static int max(int[] height) {//返回最高塔的下标int h = 0;int max = height[0];for (int i = 1; i < height.length; i++) {if(max<height[i]) {h = i;max = height[i];}}return h;}public static int min(int[] height) {//返回最低塔的下标int l = 0;int min = height[0];for (int i = 1; i < height.length; i++) {if(min>height[i]) {l = i;min = height[i];}}return l;}public static boolean balance(int hval,int lval){//判断是否平衡boolean flag = false;int x = hval-lval;if(x<=1)flag = true;return flag;    }}

 

小易的字典

小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。

小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。

小易现在希望你能帮他找出第k个单词是什么。

 

输入描述:

输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。

 

输出描述:

输出第k个字典中的字符串，如果无解，输出-1。

示例1

输入

2 2 6

输出

zzaa

说明

字典中的字符串依次为aazz azaz azza zaaz zaza zzaa

排列组合，n个'a'和m个'z'，只能组成$C_{n+m}^n$，记为count(n+m,n) 个单词。

思路：

1. 假设第一个字符为a，则剩下n-1个'a'和m个'z'组成的子序列只能构成count(n-1+m,n-1)个单词，且是字典中前count(n-1+m,n-1)个单词。
2. 比较k和count(n-1+m,n-1)，若k小，说明k是前count(n-1+m,n-1)个单词，则第一个字符必为'a'。子问题化为在子序列(n-1个'a'和m个'z')找到第k个单词
3. 若k大，则说明第一个字符必为'z',单词是以'z'开头的单词中的第k-count(n-1+m,n-1)个。子问题化为在子序列(n个'a'和m-1个'z')找到第k-count(n+m-1,m-1)个单词。

eg:n=2,m=2,k=5

1. 假设第一个字符为a,则剩下1个a,2个z只能构成3个单词，且是字典中前3个单词(aamm,amam,amma)
2. k>3，则第一个字符必为z。原问题化为在n=2,m=1,k=2，即在剩下2个a，1个z中找到第2个单词
    

   链接：https://www.nowcoder.com/questionTerminal/12b1b8ef17e1441f86f322b250bff4c0
   来源：牛客网import java.util.ArrayList;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int m = scan.nextInt();//a的个数int n = scan.nextInt();//z的个数long target = scan.nextInt();//目标第几个long k =0;ArrayList<String> list = new ArrayList<String>();while(m>0&&n>0) {//当a和z均存在时执行k = pz(m-1,n,target);//假设a确定，出去a之后剩余a和z的排列组合个数if(k>=target) {//如果确定a之后，剩余的排列组合数大于目标，则说明a已确定list.add("a");m--;//a的个数减1}else {//如果确定a之后，剩余的排列组合数小于目标，则说明不是a。list.add("z");n--;//z的个数减1target -= k;//目标减掉排列组合数。因为如果a开头可以有k中情况，//减掉k之后即为确定z开头之后，接下来找第target个即可。}}if(target != 1) {//存在经过计算之后必为1System.out.println("-1");return;}else {while(m>0) {//如果z的个数为0，则将a追加到最后即可list.add("a");m--;}while(n>0) {//如果a的个数为0，则将z追加到最后即可list.add("z");n--;}}for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i));}}public static long pz(int m,int n,long target) {//计算假设a确定之后，a之后的部分排列组合数if(m==0||n==0)return 1;long sum = m+n;long k = 1;n = Math.min(m, n);//C(m+n) n=C(m+n) m  取最小即可for (int i = 0; i < n ; i++) {k *= sum-i;k /= (i+1);if(k>target)//防止大数。如果k>target 则只进行list.add("a")和m--//a的个数减1。//没有target -= k;因此不影响break;}return k;}}