剑指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");
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

  构造函数是由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; }
}
  
 

  
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
 

线程与进程的特征及区别

  详见博文《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; }
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52766554