[数据结构与算法]剑指offer 2021/8/6

52. 两个链表的第一个公共节点

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //若其中一个链表为空，则没有公共节点，返回null
        if(headA==null || headB==null)
            return null;
        //设置两个指针分别指向两个链表的头节点
        ListNode pA=headA, pB=headB;
        //当两个指针指向同一个节点或者同为空时跳出循环
        while(pA!=pB){
            pA= pA==null ? headB : pA.next;
            pB= pB==null ? headA : pB.next;
        }
        return pA;
    }
}

改进：

双指针法。
假设两个链表相交之前的节点数目分别为a,b，相交之后的节点数目为c。若a==b，显然两个指针指向同一个节点时该节点为所求节点；否则，当第一个指针指向空时，指针重新指向B的首节点，当第二个指针指向空时，指针重新指向A的首节点。若两个链表相交，则他们最终都会经过a+b+c步指向相交的节点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //若其中一个链表为空，则没有公共节点，返回null
        if(headA==null || headB==null)
            return null;
        //设置两个指针分别指向两个链表的头节点
        ListNode pA=headA, pB=headB;
        //当两个指针指向同一个节点或者同为空时跳出循环
        while(pA!=pB){
            //pA为空时，指向B的首节点
            pA= pA==null ? headB : pA.next;
            //pB为空时，指向A的首节点
            pB= pB==null ? headA : pB.next;
        }
        return pA;
    }
}

68 - I. 二叉搜索树的最近公共祖先

代码：

递归。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q||root==null)    return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left==null)  return right;
        if(right==null) return left;
        return root;
    }
}

方法二：

迭代。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //保证p.val<q.val，这样可以在下面的循环中减少判断
        if(p.val>q.val){
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }
        while(root != null){
            //root.val>q.val代表root的值大于两个节点中较大的节点，则两个节点都在左子树中
            if(root.val > q.val)
                root=root.left;
            //root.val<p.val代表root的值大于两个节点中较小的节点，则两个节点都在右子树中
            else if(root.val<p.val)
                root=root.right;
            //否则，说明root的值介于两个节点之间，或者root的值等于其中一个节点的值，此时root即为最近公共祖先
            else    break;
        }
        return root;
    }
}

方法三：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //root.val大于两个节点的val，说明两节点在root的左子树中
        if(root.val>p.val&&root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        //root.val大于两个节点的val，说明两节点在root的左子树中
        if(root.val<p.val&&root.val<q.val)
            return lowestCommonAncestor(root.right,p,q);
        //否则，说明两节点在root两侧/其中一个节点的值等于root/root==null
        return root;
    }
}

44. 数字序列中某一位的数字

代码：

解题思路

class Solution {
    public int findNthDigit(int n) {
        //设置位数为1，从1开始计数，该位数共有9个数字
        int digit=1;
        long start=1, count=9;
        //当num<=count时，说明num位于该位数区间
        while(n>count){
            n-=count;
            digit+=1;
            start*=10;
            count = 9*start*digit;
        }
        //计算对应的数字
        long num =start + (n-1)/digit;
        //计算对应该数字的第几位
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }
}

53 - I. 在排序数组中查找数字 I

代码：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]<target)
                left=mid+1;
            //为了找到最左边的target
            else
                right=mid-1;
        }
        //边界条件：
        //1.nums数组为空
        //2.target大于数组中所有元素
        //3.数组中不存在target（其中包括了target小于数组中所有元素的情况）
        if(nums.length ==0 || left==nums.length || nums[left]!=target)
            return 0;
        int res=0;
        //计算target个数
        while(++right<nums.length && nums[right]==target)
            res++;
        return res;
    }
}

法二：

class Solution {
    public int search(int[] nums, int target) {
        //分别查找左边界left和右边界right，出现的次数即为right-left-1
        int i=0, j=nums.length-1;
        //查找右边界，保存在i中
        while(i<=j){
            int m=(i+j)/2;
            if(nums[m]>target)
                j=m-1;
            else
                i=m+1;
        }
        //若nums中不存在target，则提前返回
        if(j>=0 && nums[j]!=target)
            return 0;
        int right=i;
        i=0;
        j=nums.length-1;
        //查找左边界，保存在j中
        while(i<=j){
            int m=(i+j)/2;
            if(nums[m]<target)
                i=m+1;
            else
                j=m-1;
        }
        int left=j;
        return right-left-1;
    }
}

法三：

class Solution {
    public int search(int[] nums, int target) {
        //分别找到target和target-1的右边界，两者相减，即target出现的次数
        return helper(nums,target)-helper(nums,target-1);
    }
    int helper(int[] nums, int target){
        int i = 0, j=nums.length-1;
        while(i<=j){
            int m = (i+j)/2;
            if(nums[m]>target)
                j=m-1;
            else
                i=m+1;
        }
        return j;
    }
}

31. 栈的压入、弹出序列

代码：

创建一个栈模拟进栈出栈操作。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i=0;
        for(int num:pushed){
            //将pushed数组中的元素放入堆栈中
            stack.push(num);
            //当栈顶元素与popped数组中元素相等时，执行出栈操作，popped指针后移
            while(!stack.isEmpty() && stack.peek()==popped[i]){
                stack.pop();
                i++;
            }
        }
        //栈为空，第二个序列是该栈的弹出顺序
        return stack.isEmpty();
    }
}