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

男娘i 2021-09-20 20:18 197阅读 0赞

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

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

**【思路】**

1、**设置快慢指针**，假如有环，他们最后一定**相遇**。  
2、两个指针分别从**链表头和相遇点**继续出发，每次走一步，最后一定**相遇与环入口**。  
证明结论 1：设置快慢指针 fast 和 low，fast 每次走两步，low 每次走一步。假如有环，两者一定会相遇（因为 low 一旦进环，可看作 fast 在后面追赶 low 的过程，每次两者都接近一步，最后一定能追上）。  
证明结论 2：  
设：  
链表头到环入口长度为 --a  
环入口到相遇点长度为 --b  
相遇点到环入口长度为 --c  
![在这里插入图片描述][format_png]  
则：相遇时  
**快指针路程 = 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;
        }

[format_png]: /images/20210920/d190c08badd14aad9e37c9287ca4160c.png