劍指offer java實作合集（8）第36~40題

36.兩個連結清單的第一個公共節點

兩個連結清單的節點同步移動，如果走到連結清單尾，則繼續走另外一個連結清單，這樣當兩個節點相遇時，他們都走了len(表1)+len(表2)-公共段長度

public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

         ListNode p1 = pHead1;

        ListNode p2 = pHead2;

        while(p1!=p2){

            p1=p1==null?pHead2:p1.next;

            p2=p2==null?pHead1:p2.next;

        }

        return p1;

    }

}

37.數字在排序數列中出現的次數

從左記錄第一個等于該值的下标，從右記錄第一個等于該值的下标，二者相減，注意加一。

public class Solution {

    public int GetNumberOfK(int [] array , int k) {

       if(array.length==0){

           return 0;

       }

        if(k>array[array.length-1]||k<array[0]){

            return 0;

        }

       int i =0;

       int j =array.length-1;

       while(array[i]<k&&i<array.length){

           i++;

        }

        while(array[j]>k&&j>0){

            j--;

        }

        return j-i+1;

    }

}

38.二叉樹的深度

遞歸求法

public class Solution {

    public int TreeDepth(TreeNode root) {

        if(root==null){

            return 0;

        }

        int left = TreeDepth(root.left);

        int right = TreeDepth(root.right);

        return left>right?left+1:right+1;

    }

}

39.平衡二叉樹

平衡二叉樹的條件之一就是左右子樹深度不能超過1，依此進行判斷。

public class Solution {

    public boolean IsBalanced_Solution(TreeNode root) {

        return getDep(root)!=-1;

    }

    public int getDep(TreeNode root){

        if(root==null){

            return 0;

        }

        int left = getDep(root.left);

        if(left==-1){

            return -1;

        }

        int right = getDep(root.right);

        if(right==-1){

            return -1;

        }

        return Math.abs(left-right)>1?-1:Math.max(left,right)+1;

    }

}

40.數組中隻出現一次的數字

借用了棧，根據相鄰的值是否相同，判斷是否出棧，最後剩餘的就是所求的兩個隻出現一次的數。

//num1,num2分别為長度為1的數組。傳出參數

//将num1[0],num2[0]設定為傳回結果

import java.util.*;

public class Solution {

    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        Arrays.sort(array);

        Stack<Integer> st = new Stack();

        for(int x :array){

            if(st.isEmpty()){

                st.push(x);

            }else if(st.peek()==x){

                st.pop();

            }else{

                st.push(x);

            }

        }

        num1[0]=st.pop();

        num2[0]=st.pop();

    }

}