1.鏈表是否有環(huán)，找出環(huán)的入口

答：

是否有環(huán)，快慢指針，最后兩個(gè)指針重合了，就有環(huán)。

環(huán)入口：思路如下，設(shè)head到入口的距離為a，入口到交點(diǎn)的距離為x，環(huán)長(zhǎng)為r

則，慢指針走了a + x，快指針走了a+x+nr，因?yàn)榭熘羔樧叩氖?倍的慢指針，有

a+x+nr = 2(a + x) ->nr = a + x -> a = nr - x;由于一個(gè)指針從相交點(diǎn)開(kāi)始走了nr-x時(shí)，正好走到了環(huán)的入口（可畫(huà)圖看一下），而這個(gè)距離恰巧等于從頭結(jié)點(diǎn)到環(huán)入口的距離。因此，尋找入口，就用兩個(gè)指針，一個(gè)在頭結(jié)點(diǎn)，一個(gè)在相交點(diǎn)，走到兩指針相遇，則是環(huán)的入口。

2.LRU cache

雙向鏈表 + hashmap?

或者linked hashmap

linkedhashmap做法：初始化，第三個(gè)參數(shù)（accessOrder = true），重寫(xiě)removeEldest方法，return size() > capacity

3.數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

根據(jù)數(shù)組特點(diǎn)，數(shù)組中一個(gè)數(shù)組出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，即它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)次數(shù)的和還要多。

因此，遍歷數(shù)組時(shí)，保留兩個(gè)值，一個(gè)是數(shù)組中的一個(gè)數(shù)字，一個(gè)是次數(shù)。

當(dāng)我們遍歷到下一個(gè)數(shù)字的時(shí)候，如果下一個(gè)數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加1,；如果下一個(gè)數(shù)字和我們之前保存的數(shù)字不同，則次數(shù)減1,。如果次數(shù)為0，我們需要保存下一個(gè)數(shù)字，并把數(shù)字設(shè)為1,。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的數(shù)字。

4.超過(guò)1/3的數(shù)字：同理，用兩個(gè)變量來(lái)保留

5.數(shù)組中除了一個(gè)數(shù)，其他數(shù)字都出現(xiàn)2次，找出這個(gè)數(shù)

方法，異或 符號(hào)是^；

6。數(shù)組中除了一個(gè)數(shù)，其他數(shù)字都出現(xiàn)3次，找出這個(gè)數(shù)

轉(zhuǎn)成二進(jìn)制，然后按位加在一起，在mod 3，得到結(jié)果