小米+小红书笔试题知识点总结

2.1 解法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.2 解法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的父结点，左孩子编号为2i，右孩子编号为2i+1；

编号为100的节点(为左孩子)对应的父节点编号为50，故最小叶子节点编号为51。

三、简答题

3.1 高可用技术及原理(网络、程序、开源软件)

四、单例设计模式

// 懒汉式
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进阶(四十四)线程与进程的特征及区别》。

六、编程题

6.1 表达式合法判断(栈的运用)

    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;
    }