Java面试剑指offer系列八_编程设计

36.输入两个链表，找出它们的第一个公共结点。

　　解题思路：这里主要是把两个链表的节点都放入两个栈中，这样就可以按照出栈的方式来比较节点，因为单链表只要是有相同的节点，那么之后的节点也都是一样的，所以如果出栈的节点不相同的话就可以返回之前保存的commonNode变量，这么变量的值就是第一个共同的节点。

import java.util.Stack; 
/* 
public class ListNode { 
    int val; 
    ListNode next = null; 
 
    ListNode(int val) { 
        this.val = val; 
    } 
}*/ 
 
public class Solution { 
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
        if(pHead1 == null || pHead2 == null) 
            return null; 
         
        ListNode commonNode = null; 
        Stack<ListNode> s1 = new Stack<ListNode>(); 
        Stack<ListNode> s2 = new Stack<ListNode>(); 
         
        s1.push(pHead1); 
        s2.push(pHead2); 
         
        ListNode p1 = pHead1; 
        ListNode p2 = pHead2; 
        while(p1.next != null){ 
            s1.push(p1.next); 
            p1 = p1.next; 
        } 
        while(p2.next != null){ 
            s2.push(p2.next); 
            p2 = p2.next; 
        } 
        while(s1.peek() == s2.peek()){ 
            commonNode = s1.peek(); 
            if(s1.peek() != null) 
                s1.pop(); 
            if(s2.peek() != null) 
                s2.pop(); 
            //如果s1或者s2为空就直接跳出循环 
            if(s1.empty() || s2.empty()) 
                break; 
        }  
         
         
        return commonNode; 
    } 
}

37.统计一个数字在排序数组中出现的次数。

public class Solution { 
    public int GetNumberOfK(int [] array , int k) { 
        int len = array.length; 
        int first = -1; 
        int last = -1; 
        int num = 0; 
         
        for(int i = 0; i < len; i++){ 
            if(array[i] == k){ 
                first = i; 
                break; 
            } 
        } 
        for(int i = len-1; i >= 0; i--){ 
            if(array[i] == k){ 
                last = i; 
                break; 
            } 
        } 
         
        //如果first和last为-1的话，证明数组中没有和k相同的 
        if(first != -1 && last != -1){ 
            num = last - first +1; 
        } else{ 
            num = 0; 
        } 
         
        return num; 
    } 
}

38.输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

/* 
public class TreeNode { 
    int val = 0; 
    TreeNode left = null; 
    TreeNode right = null; 
    public TreeNode(int val) { 
        this.val = val; 
    } 
};*/ 
public class Solution { 
    public int TreeDepth(TreeNode pRoot) 
    { 
        if(pRoot == null) 
            return 0; 
         
        int nLeft = TreeDepth(pRoot.left); 
        int nRight = TreeDepth(pRoot.right); 
         
        return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); 
    } 
}

39.输入一棵二叉树，判断该二叉树是否是平衡二叉树。

　　这一种方法使用了递归的方式，虽然十分简洁，但是节点会被重复遍历多次，所以时间效率不高。

public class Solution { 
    public boolean IsBalanced_Solution(TreeNode root) { 
        //空二叉树也是平衡二叉树 
        if(root == null) 
            return true; 
         
        int left = TreeDepth(root.left); 
        int right = TreeDepth(root.right); 
         
        int diff = left - right; 
        if(diff > 1 || diff < -1) 
            return false; 
         
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); 
    } 
     
    public int TreeDepth(TreeNode pRoot) 
    { 
        if(pRoot == null) 
            return 0; 
         
        int nLeft = TreeDepth(pRoot.left); 
        int nRight = TreeDepth(pRoot.right); 
         
        return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); 
    } 
}

40.一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数 
//将num1[0],num2[0]设置为返回结果 
public class Solution { 
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
        int length = array.length; 
        if(array==null ||length<2) 
            return ; 
        int resultExclusiveOR = 0; 
        for(int i=0;i<length;i++) 
            resultExclusiveOR ^= array[i]; 
          
        int indexOf1 = findFirstBitIs1(resultExclusiveOR); 
        for(int i=0;i<length;i++){ 
            if(isBit1(array[i], indexOf1)) 
                num1[0]^=array[i]; 
            else 
                num2[0]^=array[i]; 
        } 
    } 
    public int findFirstBitIs1(int num){ 
        int indexBit = 0; 
        while(((num & 1)==0) && (indexBit)<8*4){ 
            num = num >> 1; 
            ++indexBit; 
        } 
        return indexBit; 
    } 
    public boolean isBit1(int num,int indexBit){ 
        num = num >> indexBit; 
        return (num & 1) == 1; 
    } 
}

本文参考链接：https://www.cnblogs.com/wgl1995/p/5828432.html