劍指Offer——小米 小紅書筆試題 知識點總結

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

這裡寫圖片描述
這裡寫圖片描述
這裡寫圖片描述