算法题整整理

1.链表是否有环，找出环的入口

答：

是否有环，快慢指针，最后两个指针重合了，就有环。

环入口：思路如下，设head到入口的距离为a，入口到交点的距离为x，环长为r

则，慢指针走了a + x，快指针走了a+x+nr，因为快指针走的是2倍的慢指针，有

a+x+nr = 2(a + x) ->nr = a + x -> a = nr - x;由于一个指针从相交点开始走了nr-x时，正好走到了环的入口（可画图看一下），而这个距离恰巧等于从头结点到环入口的距离。因此，寻找入口，就用两个指针，一个在头结点，一个在相交点，走到两指针相遇，则是环的入口。

2.LRU cache

双向链表 + hashmap 

或者linked hashmap

linkedhashmap做法：初始化，第三个参数（accessOrder = true），重写removeEldest方法，return size() > capacity

3.数组中出现次数超过一半的数字

根据数组特点，数组中一个数组出现的次数超过数组长度的一半，即它出现的次数比其他所有数字出现次数的和还要多。

因此，遍历数组时，保留两个值，一个是数组中的一个数字，一个是次数。

当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1,；如果下一个数字和我们之前保存的数字不同，则次数减1,。如果次数为0，我们需要保存下一个数字，并把数字设为1,。由于我们要找的数字出现的次数比其他所有数字出现的次数还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

4.超过1/3的数字：同理，用两个变量来保留

5.数组中除了一个数，其他数字都出现2次，找出这个数

方法，异或 符号是^；

6。数组中除了一个数，其他数字都出现3次，找出这个数

转成二进制，然后按位加在一起，在mod 3，得到结果