剑指Offer——小米+小红书笔试题+知识点总结
情景回顾
- 时间:2016.9.23 19:00-21:00
2016.9.24 15:00-17:00 - 地点:山东省网络环境智能计算技术重点实验室
- 事件:小米笔试、小红书笔试
- 注意事项:要有大局观,该舍弃的还是要舍弃,不要在一道编程题上占用超过30分钟的时间。当你思考了15分钟,还没有好的解决方式的时候,毅然舍弃!
public static void main(String[] args) {
// 错误声明方式
// int a [][3];
// 正确声明方式
int a [][];
// 输出 "50.1",字符串拼接
System.out.println("5" + 0.1);
// 输出 "0.15",字符串拼接
System.out.println(0.1 + "5");
}
构造函数是由jvm创建类实例时自动调用,故其修饰符为private demo(){}
二分查找的时间复杂度:O(logn)
完全二叉树第一个叶子节点的编号
解法1
深度为6的满二叉树的节点数为 2^6 - 1 = 63;
深度为7的满二叉树的节点数为 2^7 - 1 = 127;
或者根据log2n(往下取整)+1
因此含有100个节点的完全二叉树的深度为7,叶子节点分布在第6层和第7层。
第七层叶子节点数为:100 - 63 = 37;
37 / 2 = 18余1;
因此,第6层的前18个节点是2度节点,第19个节点是1度节点即只有左子树,没有右子树,即第6层前19个节点为非叶子节点,之后为叶子节点。
因此编号最小的叶子节点编号为:2^5 - 1 + 19 + 1 = 51.
其中,2^5 - 1位前5层非叶子节点数(由满二叉树的节点计算公式得出)。
解法2
根据二叉树性质5:
- 如果对于一棵有n个节点的完全二叉树(其深度depth=log2n+1下取整)的节点按层序编号(从第一层到第depth层,每层从左到右),对任一节点i(1
<= i <= n):
1.如果i=1,则节点i是二叉树的根,无双亲;如果i>1,则其双亲节点是i/2(下取整)。
2.如果2i>n,则节点i无左孩子(节点i为叶子节点);否则其左孩子是节点2i;
3.如果2i+1>n,则节点i无右孩子;否则其右孩子节点为2i+1。
完全二叉树中,对于编号为i的父结点,左孩子编号为2*i,右孩子编号为2*i+1;
编号为100的节点(为左孩子)对应的父节点编号为50,故最小叶子节点编号为51。
简答题
高可用技术及原理(网络、程序、开源软件)
单例设计模式
// 懒汉式
public class Singleton {
// 延迟加载保证多线程安全
Private volatile static Singleton singleton;
private Singleton(){}
public static Singleton getInstance(){
if(singleton == null){
synchronized(Singleton.class){
if(singleton == null){
singleton = new Singleton();
}
}
}
return singleton;
}
}
// 饿汉式
class SingletonHungry{
private final static SingletonHungry singletonHungry = new SingletonHungry();
private SingletonHungry(){}
// 务必使用static声明为类所属方法
public static SingletonHungry getInstance(){
return singletonHungry;
}
}
线程与进程的特征及区别
详见博文《Java进阶(四十四)线程与进程的特征及区别》。
编程题
表达式合法判断(栈的运用)
public static boolean chkLegal(String A) {
Stack<Character> stack = new Stack<Character>();
for(int i = 0; i < A.length(); i++){
Character ch = A.charAt(i);
if(ch == '{' || ch == '[' || ch == '('){
stack.push(ch);
continue;
}
if(!stack.isEmpty()){
Character c = stack.peek();
if(ch == '}' && c == '{')
stack.pop();
else if(ch == ']' && c == '[')
stack.pop();
else if(ch == ')' && c == '(')
stack.pop();
}
}
if (stack.isEmpty())
return true;
return false;
}