2016小米-小米Git-Java

說明：當時看到這道題目的時候，直接就有點MB了，後來仔細研究看了一些關于此題的一些說明，在加上使用過git，可能就熟悉了題目的要求。本質上就是在一個多叉樹（git結構）找到兩個子節點的最近公共父節點（就是合并git時找兩個分支的最近的分割點）。

解題思路：

1、将字元串數組轉換為字元數組；

2、周遊字元找到每個節點的父節點，記錄每個節點的深度；

3、根據兩個給定的索引值，周遊找到他們最近的公共父節點，記得每一次替換是将父節點指派給indexA/B。

import java.util.LinkedList;
import java.util.Queue;

/** 
 * 題目描述 git是一種分布式代碼管理工具，git通過樹的形式記錄檔案的更改曆史，
 * 比如： base'<--base<--A<--A' ^ | ---B<--B' 小米工程師常常需要尋找兩個分支最近的分割點，即base.
 * 假設git 樹是多叉樹，請實作一個算法，計算git樹上任意兩點的最近分割點。（假設git樹節點數為n,
 * 用鄰接矩陣的形式表示git樹：字元串數組matrix包含n個字元串，每個字元串由字元'0'或'1'組成，長度為n。
 * matrix[i][j]=='1'當且僅當git樹種第i個和第j個節點有連接配接。節點0為git樹的根節點。）
 * 輸入例子: [01011,10100,01000,10000,10000],1,2
 * 
 * 輸出例子: 1
 * @author 崔洪振367
 * @version 建立時間：2017年6月29日 下午10:22:30 
 */
public class 小米Git_ {
	/**
     * 傳回git樹上兩點的最近分割點
     * 即求多叉樹的兩個節點的公共父節點,
     * 從樹的跟節點按層往下周遊多叉樹,記錄每個節點的父節點和深度
     * 
     * @param matrix 接鄰矩陣，表示git樹，matrix[i][j] == '1' 當且僅當git樹中第i個和第j個節點有連接配接，節點0為git樹的跟節點
     * @param indexA 節點A的index
     * @param indexB 節點B的index
     * @return 整型
     */
    public int getSplitNode(String[] matrix, int indexA, int indexB) {
        int n = matrix.length;
        //每個節點的父節點
        int[] parent = new int[n];
        //記錄每個節點的深度
        int[] depth = new int[n];
        //将字元串數組轉換為字元數組
        char[][] tree = new char[n][];
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            tree[i] = matrix[i].toCharArray();
            parent[i] = -1;//初始化父節點，設定為獨立的節點
            depth[i] = 1;//初始化每個節點的深度，将其值設定為1
        }
        que.add(0);//第一個節點存入到隊列中
        parent[0] = 0;
        //從跟節點往下周遊多叉樹,按層周遊
        while (!que.isEmpty()) {
            int v = que.poll();
            for (int i = 0; i < n; i++) {//将v看作父節點，i看作是孩子節點
            	//從v-->i看作是節點的v的初度值，進而判斷v節點的孩子節點個數就是i滿足i的值個數
                if (tree[v][i] == '1' && parent[i] == -1) {
                    que.add(i);
                    parent[i] = v;
                    depth[i] = depth[v] + 1;//節點的深度是父節點的深度+1
                }
            }
        }
        
        //下面的操作就是找到兩個值indexA和indexB最近公共父節點，主要是通過判斷兩個值的父節點值是否相等
        while (depth[indexA] > depth[indexB]) {
            indexA = parent[indexA];
        }
        while (depth[indexA] < depth[indexB]) {
            indexB = parent[indexB];
        }
        while (indexA != indexB) {
            indexA = parent[indexA];
            indexB = parent[indexB];
        }
        return indexA;
    }

}