网易2016研发工程师编程题详解

发表于   |   分类于   |     |   阅读次数

enter description here

今天刷了一下网易2016研发工程师的编程题，也不觉得太难啊。为什么当时找实习做笔试的时候就那么觉得时间不够用呢！下面就看看总结一下今天的战果吧。

<第一题>小易的升级之路

题目描述是这样子滴，/**

  • 小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.
  • 在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3…bn.
  • 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物
  • 并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.
  • 那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?
  • @author henry
    /

网易的题目很有趣味性吧，就跟玩游戏一样–打关卡。

输入描述：

对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值.
第二行n个整数,b1,b2…bn(1≤bi≤n)表示每个怪物的防御力

输出描述：

对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值

输入的例子：

3 50
50 105 200
5 20
30 20 15 40 100

输出的例子：

110
205

解题思路

只要认真读题，相信大部分人都能理解，这个可比小学的奥数简单多了。唯一有点卡人的地方就是求两个数的最大公约数，这也是本题的考点。
伪代码：
　　初始值a;
　　while(n个怪物){
　　　　if(bi<=当前能力值c){
　　　　　　增加自身能力值bi
　　　　　　更新c
　　　　}
　　　　else{
　　　　 t=bi与c的最大公约数
　　　　　　增加自身能力值t
　　　　　　更新c
　　　　}
　　}
　　最终能力值c
怎么样求最大公约数？有几个方法，就不赘述了，贴几个链接看看吧——
三种算法求最大公约数
求最大公约数最小公倍数
笔者使用的就是辗转相除法。
好了，直接代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Scanner;
import java.util.ArrayList;
public class Wangyi_1 {
	public static void main(String[] args) {
		//读取数据
		Scanner scanner=new Scanner(System.in);
		int counts=scanner.nextInt();//counts个怪物
		int power=scanner.nextInt();//初始能力
		ArrayList<Integer> defense=new ArrayList<Integer>();//各个防御力
		for(int i=0;i<counts;i++){
			defense.add(scanner.nextInt());
		}
		//System.out.println(counts+"..."+power);
		//System.out.println(defense);
		scanner.close();
		//
		for(int i=0;i<counts;i++){
			//轻松打败怪物
			if(power>=defense.get(i)){
				power+=defense.get(i);
			}
			//也能打败,加上最大公约数
			else{
				power+=maxCommonDiv(power,defense.get(i));
			}
		}
		System.out.println(power);
	}
	/**
	 * 求出两个数的最大公约数（辗转相除法）
	 * 始终用较大数（被除数）除以较小数（除数），然后用除数代替较大数（被除数），
	 * 余数代替较小数（除数），代替完后继续让新的被除数除以除数。直到相除余数为0时。
	 * 最后的除数就是最大公约数
	 * @param m
	 * @param n
	 * @return 最大公约数
	 */
	public static int maxCommonDiv(int m,int n){
		//确保最大的数是m
		 if (m < n) {// 保证m>n,若m<n,则进行数据交换  
	            int temp = m;  
	            m = n;  
	            n = temp;  
	        }  
	        while (m % n != 0) {// 在余数不能为0时,进行循环  
	            int temp = m % n;  
	            m = n;  
	            n = temp;  
	        }  
	        return n;// 返回最大公约数  
	}
}

<第二题>炮台攻击

题目描述：
/**

  • 炮台攻击
  • 兰博教训提莫之后,然后和提莫讨论起约德尔人,谈起约德尔人,自然少不了一个人,
  • 那 就是黑默丁格——约德尔人历史上最伟大的科学家.
  • 提莫说,黑默丁格最近在思考一个问题:黑默丁格有三个炮台,炮台能攻击到距离它R的敌人
  • (两点之间的距离为两点连续的距离,例如(3,0),(0,4)之间的距离是5),
  • 如果一个炮台能攻击 到敌人,那么就会对敌人造成1×的伤害.黑默丁格将三个炮台放在N*M方格中的点上,
  • 并且给出敌人 的坐标. 问:那么敌人受到伤害会是多大?
  • @author henry
    /

输入描述：
第一行9个整数,R,x1,y1,x2,y2,x3,y3,x0,y0.R代表炮台攻击的最大距离,(x1,y1),(x2,y2),
(x3,y3)代表三个炮台的坐标.(x0,y0)代表敌人的坐标.
输出描述：
输出一行,这一行代表敌人承受的最大伤害,(如果每个炮台都不能攻击到敌人,输出0×)
输入例子：
1 1 1 2 2 3 3 1 2
输出例子：
2x
直接上代码，代码里注释应该看得懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Scanner;
public class Wangyi_2 {
	public static void main(String[] args) {
		//读取数据
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNextInt()){
			int hurtNums=0;
			int maxR=scanner.nextInt();
			int [][] location=new int[4][4];//用来存放4个坐标
			//炮台1的坐标
			location[0][0]=scanner.nextInt();
			location[0][5]=scanner.nextInt();
			//炮台2的坐标
			location[1][0]=scanner.nextInt();
			location[1][6]=scanner.nextInt();
			//炮台3的坐标
			location[2][0]=scanner.nextInt();
			location[2][7]=scanner.nextInt();
			//敌人的坐标
			location[3][0]=scanner.nextInt();
			location[3][8]=scanner.nextInt();
			
		//计算每个炮台距离敌人的距离
			double len_1=Math.sqrt(Math.pow(location[0][0]-location[3][0], 2)+Math.pow(location[0][9]-location[3][10], 2));
			double len_2=Math.sqrt(Math.pow(location[1][0]-location[3][0], 2)+Math.pow(location[1][11]-location[3][12], 2));
			double len_3=Math.sqrt(Math.pow(location[2][0]-location[3][0], 2)+Math.pow(location[2][13]-location[3][14], 2));
			//System.out.println(len_1+"@"+len_2+"@"+len_3);
			//统计收伤害点数
			if(len_1<=maxR)
				hurtNums++;
			if(len_2<=maxR)
				hurtNums++;
			if(len_3<=maxR)
				hurtNums++;
		//scanner.close();
			System.out.println(hurtNums+"x");
			//
		}
		
	}
}

<第三题>多线程打印

题目描述：
/**

  • 一个文件中有10000个数，用Java实现一个多线程程序将这个10000个数输出到5个不同的文件中（不要求输出到每个文件中的数量相同）。
  • 要求启动10个线程，两两一组，分为5组。
  • 每组两个线程分别将文件中的奇数和偶数输出到该组对应的一个文件中，需要偶数线程每打印10个偶数以后，就将奇数线程打印10个奇数，如此交替进行。
  • 同时需要记录输出进度，每完成1000个数就在控制台中打印当前完成数量，并在所有线程结束后，在控制台打印”Done”.
  • @author henry
    /

贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
public class Wangyi_3 {
	public static void main(String[] args) {
		try{
			//创建一个文件包含10000个数
			PrintWriter writer=new PrintWriter(new FileWriter(new File("numsCollection.txt")),true);
			Random random=new Random();
			//往文件里面随机写10000个数字，以逗号分隔
			for(int i=0;i<10000;i++){
				writer.print(Math.abs(random.nextInt())%100+",");
			}
			writer.flush();
			writer.close();
			//创建读文件缓冲区
			BufferedReader reader=new BufferedReader(new FileReader("numsCollection.txt"));
			String str=reader.readLine();//10000个数都在字符串str中
			reader.close();
			//去掉逗号，分隔开来
			String [] nums=str.split(",");
			int j=0;//nums数组中的下标，记录读到的位置
			for(int i=0;i<5;i++){
				int [] readNum=new int[2000];//待写入的2000个数
				for(int k=0;k<2000;k++){
					readNum[k]=Integer.parseInt(nums[j]);
					j++;
				}
				//创建待写入文件
				PrintWriter filewriter=new PrintWriter(new FileWriter(new File("file_"+i+".txt")),true);
				 
				//定义实现的方法
                MyThread group=new MyThread(readNum, filewriter);
                //开启一对儿线程
                new Thread(group).start();
                new Thread(group).start();      
			}
		}catch(Exception e){
			e.printStackTrace();
		}
	}
}

class MyThread implements Runnable{
	//所有类对象共享的同一个计数器count，记录总共输出的记录总数
    private static int count=0;
    //所有的MyThread类对象共享一个锁，用于count变量的同步，任何一个线程需要修改count变量，必须取得该锁
    private static Object lock=new Object();
    public static final int EVEN=0;//代表偶数
    public static final int ODD=1;//代表奇数
     
    //*********以上静态变量，属于整个类所有***********
    private int type;
    private int readNums[];
    private PrintWriter writer;//每组共享一个writer，输出到同一个文件
    private int oddPoint=0;//记录每次打印奇数的起始位置
    private int evenPoint=0;//记录每次打印偶数的起始位置
	
    public MyThread(int[] readNums,PrintWriter writer){
    	this.readNums=readNums;
    	this.writer=writer;
    	this.type=EVEN;
    }
    
	@Override
	public void run(){
		while(print());
	}
	
	 private synchronized boolean print(){
		 //偶数打印10个，接着奇数打印10个，交替进行 
		 for(int i=0;i<10;){
	            //如果奇数和偶数都打印完成以后，就直接停止打印循环，等待该线程自己结束
	            if (oddPoint>=readNums.length&&evenPoint>=readNums.length) {
	                notifyAll();
	                return false;
	            }
	            //如果该线程该打印奇数，但奇数已经打印晚了，就直接停止本次10个数的打印，
	            //同理偶数，等下次切换打印类型后，再开始打印另外一种类型
	            if ((oddPoint>=readNums.length&&type==ODD)||(evenPoint>=readNums.length&&type==EVEN)) {
	                break;
	            }
	            //判断开始打印偶数
	            if (type==EVEN) {
	                if ((readNums[evenPoint]&1)==0) {
	                    i++;
	                    writer.print(readNums[evenPoint]+",");
	                    writer.flush();
	                    //锁定全局变量方便线程输出后计数
	                    synchronized (lock) {
	                        count++;
	                        if (count%1000==0) {
	                            System.out.println("当前完成数量："+count);
	                            if (count==10000) {
	                                System.out.println("Done!");
	                            }
	                        }
	                    }
	                }
	                //无论是否是偶数，打印成功一个后，偶数的起始位置都要后移
	                evenPoint++;
	            }else {
	                //打印奇数
	                if ((readNums[oddPoint]&1)==1) {
	                    i++;
	                    writer.print(readNums[oddPoint]+",");
	                    writer.flush();
	                    //锁定全局变量方便线程输出后计数
	                    synchronized (lock) {
	                        count++;
	                        if (count%1000==0) {
	                            System.out.println("当前完成数量："+count);
	                            if (count==10000) {
	                                System.out.println("Done!");
	                            }
	                        }
	                    }
	                }
	                //无论是否是奇数，打印成功一个后，偶数的起始位置都要后移
	                oddPoint++;
	            }  
	        }
		  type=~type;//切换打印类型
	      notifyAll();//一组中的任一线程打印完后唤醒另一个线程
	      try {
	            wait();//释放锁进入等待状态，等待另一线程打印
	        } catch (Exception e) {
	            // TODO: handle exception
	        	e.printStackTrace();
	        }
	      return true;
	 }
}

enter description here
弄完这些东西，觉得今天过的还满充实的，因为做题目多线程交替打印有点不熟悉，又去翻翻书了，果然书到用时方恨少。

热评文章