36.兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)

輸入兩個(gè)鏈表茁影，找出它們的第一個(gè)公共結(jié)點(diǎn)薪韩。

拿到這個(gè)題确沸，試想一下捌锭，如果兩個(gè)鏈表的長度一樣，應(yīng)該怎么做罗捎，當(dāng)然就是兩個(gè)鏈表從頭結(jié)點(diǎn)開始同時(shí)往后遍歷观谦，找到第一個(gè)相同的結(jié)點(diǎn)即可。
那么上升到更一般的情況下桨菜，兩個(gè)鏈表長度不相等豁状，應(yīng)該怎么做，單向鏈表是不可逆的倒得，因此我們沒法從后往前找第一個(gè)公共結(jié)點(diǎn)泻红。我們可以仿照兩個(gè)鏈表長度相同到的情況下進(jìn)行求解，怎么讓兩個(gè)鏈表長度相同呢霞掺，就是分別求出兩個(gè)鏈表的長度谊路，然后讓長的那個(gè)鏈表先往后走兩個(gè)鏈表之間的差值的長度即可。
代碼如下

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        //用兩個(gè)數(shù)字分別記錄兩個(gè)鏈表的長度
        int cnt1 = 0,cnt2 = 0;
        while(cur1!=null){
            cnt1++;
            cur1 = cur1.next;
        }
        while(cur2!=null){
            cnt2++;
            cur2 = cur2.next;
        }
        cur1 = pHead1;
        cur2 = pHead2;
        //如果鏈表1長菩彬，就讓鏈表1走cnt1-cnt2的長度
        //如果鏈表2長缠劝，就讓鏈表2走cnt2-cnt1的長度
        int cnt = 0;
        if(cnt1<cnt2){
            while(cnt<cnt2-cnt1){
                cur2 = cur2.next;
                cnt++;
            }
        }else{
            while(cnt<cnt1-cnt2){
                cur1 = cur1.next;
                cnt++;
            }
        }
        //兩個(gè)鏈表的指針同時(shí)向后走，碰到第一個(gè)相等的結(jié)點(diǎn)就是第一個(gè)公共結(jié)點(diǎn)
        while(cur1!=null&&cur2!=null){
            if(cur1==cur2){
                return cur1;
            }else{
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return null;
        
    }
}

37.數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)骗灶。

最簡單直觀的方法當(dāng)然是按順序統(tǒng)計(jì)惨恭，這樣的時(shí)間復(fù)雜度是O(n)
代碼如下

public class Solution {
    //private int cnt = 0;
    public int GetNumberOfK(int [] array , int k) {
        if(array.length<=0){
            return 0;
        }
        int cnt = 0;
        for(int num:array){
            cnt = num==k?cnt+1:cnt;
        }
        return cnt;
    }
}

但是既然題目中已經(jīng)給了排序這個(gè)信息，我們就應(yīng)該利用好排序這個(gè)信息矿卑，即用BinarySearch進(jìn)行尋找第一個(gè)K出現(xiàn)的位置和第一個(gè)大于K的數(shù)出現(xiàn)的位置喉恋。
在使用二分查找的時(shí)候，我們需要明白幾點(diǎn)：
1.二分查找的原理就是"逼近"母廷，當(dāng)mid指向的數(shù)大于等于target時(shí)隆豹，證明target在前半段數(shù)組中筏勒；反之target在后半段數(shù)組中,直到低位指針與高位指針重合熬北；
2.如果我們要找的數(shù)不在數(shù)組中嚎京，可能存在兩種情況

1.target夾在數(shù)組中間，例如target=4,array={1,3,5,7,9}业舍；這種情況下試想抖拦，
我們通過逼近的方法可以“知道”4在3的后面，而7,9顯然是大于4的舷暮，所以最后夾在中間的只有5
這里可以延伸為我們在數(shù)組中尋找target時(shí)态罪，如果target不存在，則會(huì)找到第一個(gè)大于target的數(shù)下面；
2.target大于數(shù)組中全部的數(shù)复颈，例如target=6，array={1,2,3,4,5}沥割，
我們最好在寫代碼的時(shí)候就將high定義為array.length耗啦，這樣通過逼近的方法凿菩，最后l和h重疊的時(shí)候就出界了，這樣方便判斷帜讲；

根據(jù)以上可以寫出如下流程的代碼

1.對(duì)target進(jìn)行二分查找衅谷，找到target出現(xiàn)的第一個(gè)位置；
2.對(duì)target+1進(jìn)行二分查找似将，這里的意思是找到第一個(gè)大于等于target+1的元素获黔，類似于放縮發(fā)也就找到了第一個(gè)大于target的元素；
3.對(duì)l進(jìn)行判斷是不是上面提到的兩種不存在的情況玩郊，對(duì)于第一種情況需要判斷array[first]和k是否相等肢执，對(duì)于第二種情況需要判斷first是否出界了，滿足以上兩者之一的译红，都需要判定target不存在數(shù)組中，返回0.

代碼如下

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array.length<=0){
            return 0;
        }
        //對(duì)k進(jìn)行二分查找兴溜，找到k第一次出現(xiàn)的位置
        int first = binarysearch(array,k);
        //對(duì)k+1進(jìn)行二分查找侦厚，找到大于等于K+1的數(shù)，即大于K的數(shù)第一次出現(xiàn)的位置拙徽；
        int last = binarysearch(array,k+1);
        //滿足target夾在數(shù)組中某兩個(gè)數(shù)中間或target大于數(shù)組中全部數(shù)情況之一的刨沦，需要返回0
        return (first==array.length||array[first]!=k)?0:last-first;
    }
    //定義簡單二分查找函數(shù)
    private int binarysearch(int [] array,int k){
        int l = 0,h = array.length;
        while(l<h){
            int m = (l+h)/2;
            if(array[m]>=k){
                h = m;
            }else{
                l = m+1;
            }
        }
        return l;
        
    }
}

二叉樹的深度

輸入一棵二叉樹，求該樹的深度膘怕。
從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根想诅、葉結(jié)點(diǎn)）形成樹的一條路徑，最長路徑的長度為樹的深度岛心。

這個(gè)題思路倒是簡單来破，就用一個(gè)變量來保存當(dāng)前最大深度，
然后用深度遍歷的方法統(tǒng)計(jì)各條路線的長度忘古，然后與這個(gè)最大深度進(jìn)行比較取大者徘禁，最后輸出最大值。
代碼如下

public class Solution {
    private int depth = 0;
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //這里要注意不要采坑Ｋ杩啊Ｋ椭臁！
        //我們往下進(jìn)行遞歸的時(shí)候會(huì)使計(jì)數(shù)+1
        //以單個(gè)根節(jié)點(diǎn)為例干旁，左右結(jié)點(diǎn)為空驶沼，但是計(jì)數(shù)+1了，層數(shù)為0+1=1,這才是符合實(shí)際情況到的
        //所以在入口的時(shí)候傳遞的初始層數(shù)應(yīng)該為0
        find_depth(root,0);
        return depth;
    }
    //對(duì)二叉樹進(jìn)行深度遍歷
    public void find_depth(TreeNode root,int cnt){
        //當(dāng)遞歸到結(jié)點(diǎn)為null的時(shí)候争群，將當(dāng)前的cnt與depth進(jìn)行比較取大者
        if(root==null){
            depth = cnt>depth?cnt:depth;
            return;
        }
        //對(duì)左右子樹進(jìn)行遞歸處理
        find_depth(root.left,cnt+1);
        find_depth(root.right,cnt+1);
    }
}

39.平衡二叉樹

輸入一棵二叉樹回怜，判斷該二叉樹是否是平衡二叉樹。

這個(gè)題的思路還是判斷左右子樹的高度差是否小于1祭阀，我們可以采用這樣的方式鹉戚，即初始化一個(gè)布爾變量為true,全局中只要出現(xiàn)一個(gè)位置不滿足平衡二叉樹的條件鲜戒，就會(huì)使這個(gè)變量被賦值為false，如果全局都滿足平衡二叉樹抹凳，最后的輸出也就是true;同時(shí)遏餐，在計(jì)算樹的深度的時(shí)候要學(xué)會(huì)通過遞歸返回值，具體步驟如下

1.初始化一個(gè)全局布爾變量boolean res = true赢底；
2.構(gòu)建一個(gè)整型返回值的函數(shù)用來計(jì)算樹的高度失都，注意這個(gè)函數(shù)既承擔(dān)了在遞歸中不斷計(jì)算樹的深度的任務(wù)，又承擔(dān)著判斷各子樹是否為平衡二叉樹幸冻，當(dāng)然只要判定一次不為平衡二叉樹粹庞，其它也就無所謂了。

有了這個(gè)思路洽损，代碼如下

public class Solution {
    //初始化一個(gè)全局布爾變量
    private boolean res = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        //height函數(shù)無需返回值庞溜，因?yàn)橹恍枰诋?dāng)中判定res是否會(huì)變成false即可
        height(root);
        return res;
    }
    private int height(TreeNode root){
        //如果結(jié)點(diǎn)為空則返回0，這既是對(duì)根節(jié)點(diǎn)的判定碑定，也是一個(gè)遞歸計(jì)算深度的初始值
        if(root==null){
            return 0;
        }
        //對(duì)左右子樹進(jìn)行遞歸
        int left = height(root.left);
        int right = height(root.right);
        if(Math.abs(left-right)>1){
            res = false;
        }
        //這里承擔(dān)著一層層往上遞歸樹的深度的任務(wù)
        //可以這樣看流码，root的深度是多少？是1加上左子樹的深度和右子樹的深度中的大者
        //那么左子樹深度left和右子樹深度right是多少呢延刘？
        //就是又要用到這個(gè)height函數(shù)來求解了漫试，left = height(root.left);right=height(root.right);
        //當(dāng)遞歸到葉子結(jié)點(diǎn)的時(shí)候，可以看到左右都為null碘赖，即葉子結(jié)點(diǎn)的深度為1驾荣，這也是一層層往上遞歸的
        return 1+Math.max(left,right);
    }
}

40.數(shù)組中只出現(xiàn)一次的數(shù)字

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次普泡。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字播掷。

之前做的簡單難度的是找出一個(gè)只出現(xiàn)一次的數(shù)字，這次要找兩個(gè)劫哼，要學(xué)會(huì)將復(fù)雜問題拆分成簡單的子問題來求解叮趴，如果我們能根據(jù)某些特征將這些數(shù)字分成兩組，第一組只包含第一個(gè)數(shù)权烧，第二組只包含第二個(gè)數(shù)眯亦，然后再用只出現(xiàn)一次的一個(gè)數(shù)這個(gè)思路來求解不就行了嗎？
假設(shè)這兩個(gè)只出現(xiàn)一次的數(shù)為a,b我們對(duì)數(shù)組中所有的數(shù)求異或般码，最后得到的結(jié)果就是a^b妻率，異或異或顧明思意這個(gè)結(jié)果肯定會(huì)包含1，因?yàn)閍,b肯定是不相等板祝，我們找到第一個(gè)為1的位宫静，例如00100這個(gè)數(shù)，整個(gè)數(shù)組就被劃分成兩個(gè)部分了，1.該位為1孤里；2該位不為1伏伯；
該位為1的數(shù)與上00100肯定不為0,該位為0的數(shù)與上00100肯定為0
按照這個(gè)思路，流程如下

1.求出這兩個(gè)數(shù)相異或的結(jié)果
2.求出這個(gè)結(jié)果中第一位為1的這個(gè)數(shù)
3.根據(jù)這個(gè)判定條件捌袜，分別不同條件下的數(shù)不斷求異或運(yùn)算说搅，得到最終的兩個(gè)數(shù)

代碼如下

//num1,num2分別為長度為1的數(shù)組。傳出參數(shù)
//將num1[0],num2[0]設(shè)置為返回結(jié)果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int diff = 0;
        for(int num:array){
            diff ^= num;
        }
        //找到第一個(gè)不為1的數(shù)
        //負(fù)數(shù)的二進(jìn)制是取反加1
        //以diff=10100為例虏等，-diff = 01011+1=01100
        //10100&01100=00100弄唧，正好就是我要求的
        diff &= -diff;
        for(int num:array){
            //這里就是分為了兩個(gè)元素區(qū)，第一個(gè)為在該位上為0霍衫，則與diff后全部為0,我們異或所有的這些數(shù)即可
            //相反得到到的就是另外一個(gè)數(shù)
            if((num&diff)==0){
                num1[0] ^=num;
            }else{
                num2[0] ^=num;
            }
        }
    }
}