剑指Offer——网易校招内推笔试题+模拟题知识点总结
前言
2016.8.2 19:00网易校招内推笔试开始进行。前天晚上利用大约1小时时间完成了测评(这个必须做，关切到你能否参与面试)。上午利用2小时时间做了下模拟题，模拟题中编程题占用时间比较多，可以先在自己电脑中的IDE编程测试。待测试完成后再将代码拷贝至OJ，运行所给测试案例。考察的知识点范围比较广泛，设计操作系统，Linux、java多线程、网络编程等。模拟题主要考查知识点如下(可能存在遗漏某些知识点的情况):
1.求给出叶子节点时哈夫曼树的带权路径长度。
构造赫夫曼树
1.构造森林全是树。
2.选用两小造新树。
3.删除两小添新人。
4.重复2、3剩单根。
树的带权路径长度 WPL = W1L1+...+WkLk
2.问答题。内部类访问外部变量为何加final关键字？
因为生命周期的原因。方法中的局部变量在方法结束后就要被释放掉，final保证这个变量始终指向一个对象。
首先，内部类和外部类其实是处于同一个级别，内部类不会因为定义在方法中就会随着方法的执行完毕而跟随着被销毁。问题就来了，如果外部类的方法中的变量不定义final，那么当外部类方法执行完毕的时候，这个局部变量肯定也就被GC(Garbage Collection)了，然而内部类的某个方法还没有执行完，这个时候他所引用的外部变量已经找不到了。如果定义为final，java会将这个变量复制一份作为成员变量内置于内部类中，这样的话，由于final所修饰的值始终无法改变，所以这个变量所指向的内存区域就不会变。
但是为什么这里用final却又可以访问呢？
因为Java采用了一种copy local variable的方式来实现，也就是说把定义为final的局部变量拷贝过来用，而引用的也可以拿过来用，只是不能重新赋值。从而造成了可以access local variable的假象，而这个时候由于不能重新赋值，所以一般不会造成不可预料的事情发生。
3.Java泛型的作用，实现原理？List<String> 对象可否赋给List<Object>类型引用？
在引入范型之前，Java类型分为原始类型、复杂类型，其中复杂类型分为数组和类。引入范型后，一个复杂类型就可以在细分成更多的类型。
例如原先的类型List，现在在细分成List<Object>, List<String>等更多的类型。
注意，现在List<Object>, List<String>是两种不同的类型，
他们之间没有继承关系，即使String继承了Object。下面的代码是非法的
List<String> ls = new ArrayList<String>();
List<Object> lo = ls;
这样设计的原因在于，根据lo的声明，编译器允许你向lo中添加任意对象（例如Integer），但是此对象是List<String>，破坏了数据类型的完整性。
4.TCP如何保障消息顺序及可靠到达？TIME_WAIT状态是怎么产生的？作用？在哪端产生？原因？
5.编程题。数字黑洞问题
6.发行唱片问题。
7.下厨房
源码
package cn.edu.ujn.demo;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
* 下厨房
* 1.正则分割
* 2.统计未重复出现的单词个数
*/
public class Food {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
Scanner in = new Scanner(System.in);
Pattern pattern = Pattern.compile("[ ]+");
while (in.hasNextLine()) {// 注意while处理多个case
String a = in.nextLine();
if(a.length() == 0){
break;
}
String[] strs = pattern.split(a);
for (int i = 0; i < strs.length; i++) {
if(!list.contains(strs[i])){
list.add(strs[i]);
}
}
}
System.out.println(list.size());
}
}
这道编程题还算简单，最后通过了测试。
8.地牢逃脱
这道题真的没有读懂题意，就连给的示例都没有搞明白。Σ( ° △ °|||)︴
解题思路:原来题目中合法步长数k下的k行数据代表可供选择的移动方法，自己当时理解错了。注意到该问题与迷宫问题有一拼，使用回溯法应该可以得到解决。若大家有好的解决方法，还望不吝赐教。
9.分田地
这道题目刚开始时误以为读懂了题目，心想不就是找最小值嘛，不过测试之后才发现，自己想的过于过于简单了。
解题思路:前提是所划分的田地数是16的倍数。最简单的情形是共计16块田地(以上例为例)，每人一块，以4*4矩阵为例，每个位置均存在权重值。可采用按行读取，正则分割，寻找最小值的思路解决。当矩阵为n*m(n*m必为16的倍数)数值足够大时，效率问题就会凸显，此时可以考虑使用动态规划算法。以8*8矩阵为例，每人分得4块土地，可按照4个4*4矩阵进行处理。待每个4阶方阵得出最小值后相加即为所得结果。具体如何解决，待后续。已解决的朋友望不吝赐教。
示例代码
package cn.edu.ujn.demo;
import java.util.Scanner;
/**
*
* @author SHQ
* 分田地
* 1.化整为零
* 2.找16个数中的最小值
*/
public class DivideLand {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int min = 99;
int i = 0;
int m = 0;
int n = 0;
while(in.hasNextInt()){
m = in.nextInt();
n = in.nextInt();
break;
}
while (in.hasNextLine()) {//注意while处理多个case
i++;
char [] a = in.nextLine().toCharArray();
for(int j = 0; j < a.length; j++){
if(a[j] < min){
min = a[j];
}
}
if(i == m+1){
break;
}
}
System.out.println(min-48);
}
}
10.根据二叉树的先序遍历:a,e,b,d,c;后续遍历:b,c,d,e,a.得出根节点的孩子节点。
二叉树前序：根节点、左子树、右子树；
中序：左子树、根节点、右子树；
后序：左子树、右子树、根节点。
可以发现，二叉树前序中的第一个节点为树的根节点root，然后找出root在中序里面的位置，就可以把前序和中序分别划分为左、右子树两个部分，然后递归调用即可。
举个例子，前序: 3 2 4 8 6 10 ；中序: 2 3 4 6 8 10
首先，5肯定是二叉树的根节点，然后5在中序里面的位置是3号（从0开始），此位置前面的是左子树中的节点，右面的是右子树的节点，即5 || 3 2 4 || 8 6 10。
由后序和中序求前序也是像类似的思想。但是仅仅知道前序和后序无法确定二叉的形状。比如前序 1 2 3 后序 3 2 1 则下面两种情况都符合.
11.Linux网络服务接口:/etc/network/interfaces（/etc/init.d/networking）
12.判定织入点与切入点的配置信息
13.问答题。网易云音乐中如何获取3小时，1天，1周播放次数最多的K首歌曲，请叙述数据结构算法和框架设计。
吐槽
由于牛客网承接的网易内推笔试，结果人数过多判题机直接宕掉了~延长一小时。
一直显示正在提交...严重怀疑自己的程序存在问题
最终.....还是宕掉了