Java面试知识点（七十七）剑指offer精彩算法题（上）

一、剑指offer第56题【链表中环的入口节点】

【题目】
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null。

【思路】

1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
证明结论 1：设置快慢指针 fast 和 low，fast 每次走两步，low 每次走一步。假如有环，两者一定会相遇（因为 low 一旦进环，可看作 fast 在后面追赶 low 的过程，每次两者都接近一步，最后一定能追上）。
证明结论 2：
设：
链表头到环入口长度为 --a
环入口到相遇点长度为 --b
相遇点到环入口长度为 --c

则：相遇时
快指针路程 = a+(b+c) k+b ，k>=1 其中 b+c 为环的长度，k 为绕环的圈数（k>=1, 即最少一圈，不能是 0 圈，不然和慢指针走的一样长，矛盾）。
慢指针路程 = a+b
快指针走的路程是慢指针的两倍，所以：
（a+b）*2=a+(b+c)k+b
化简可得：
a=(k-1)(b+c)+c 这个式子的意思是： **链表头到环入口的距离 = 相遇点到环入口的距离 +（k-1）圈环长度。**其中 k>=1, 所以 k-1>=0 圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

对于判断是否有环，这个问题很简单，如果有环，无论如何遍历，都不会出现null节点的，判断快节点是否是null就可以判断了

【代码】

public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 设置快慢节点
        ListNode slow,quick;
        slow = pHead;
        quick = pHead;
        // 在有环的情况下一直循环，无环跳出循环
        while (quick != null && quick.next !=null) {
            quick = quick.next.next;
            slow = slow.next;
            // 相遇之后跳出循环
            if (slow == quick) {
                break;
            }
        }
        // 如果无环
        if (quick == null || quick.next == null) {
            return null;
        }
        // slow从头节点开始遍历
        slow = pHead;
        while (slow != quick) {
            slow = slow.next;
            quick = quick.next;
        }
        return slow;
    }

二、剑指offer第44题【扑克牌的顺子】

【题目】

LL 今天心情特别好，因为他去买了一副扑克牌，发现里面居然有 2 个大王，2 个小王 (一副牌原本是 54 张 ^_)… 他随机从中抽出了 5 张牌，想测测自己的手气，看看能不能抽到顺子，如果抽到的话，他决定去买体育彩票，嘿嘿！！“红心 A, 黑桃 3, 小王，大王，方片 5”,“Oh My God!” 不是顺子…LL 不高兴了，他想了想，决定大 \ 小 王可以看成任何数字，并且 A 看作 1,J 为 11,Q 为 12,K 为 13。上面的 5 张牌就可以变成 “1,2,3,4,5”(大小王分别看作 2 和 4),“So Lucky!”。LL 决定去买体育彩票啦。 现在，要求你使用这幅牌模拟上面的过程，然后告诉我们 LL 的运气如何， 如果牌能组成顺子就输出 true，否则就输出 false。为了方便起见，你可以认为大小王是 0。

【题解】

可以这么理解，简单来说就是要是 5 个数字，最大和最小差值在 5 以内，并且没有重复数值。用一个 set 来填充数据（可以把重复的去掉），0 不要放进去。set 的大小加上 0 的个数必须为 5 个。此外 set 中数值差值在 5 以内。

【代码】

    /**
     * 参考思路：
     * 1.依次录入数组，把0剔除并记录个数
     * 2.剩下的数组排序
     * 3.存在相同的数字返回false
     * 4.不存在相同的数字，最大值-最小值<5 返回true
     * */
    public boolean success(int[] numbers) {
        int n = numbers.length;
        int count = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i=0; i<n; i++) {
            if (numbers[i] == 0) {
                count ++;
            } else {
                set.add(numbers[i]);
            }
        }

        // set有去重的功能，若小于5则代表有重复内容
        if ((set.size()+count) < 5){
            return false;
        }

        // TreeSet方法有last和first方法，可以快速获取最大值和最小值
        if ((set.last()-set.first())<5) {
            return true;
        }

        return false;
    }