文章目錄
-
- NO.141 環形連結清單 簡單
- NO.142 環形連結清單II 中等
- NO.202 快樂數 簡單
- NO.287 尋找重複數 中等
NO.141 環形連結清單 簡單
思路一：HashSet p指針周遊連結清單，将每個節點存入 set ，如果通路的節點 set 中存在，說明有環。
時間複雜度：O(n) 空間複雜度：O(n)
思路二：快慢指針 其實就是 Floyd 算法，如果快指針走到了結尾，說明不是環形連結清單；如果是環形連結清單快慢指針一定會相遇，因為入環之後每次移動快慢指針，就相當于讓兩個指針的距離 -1 。
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
//相遇說明有環
if (fast == slow) return true;
fast = fast.next.next;
slow = slow.next;
}
return false;
}
時間複雜度：O(n) 空間複雜度：O(1)
NO.142 環形連結清單II 中等
和其姊妹題NO.141的解題思路一樣，稍微一些調整變化。
思路一：HashSet p指針周遊連結清單，将每個節點存入 set ，如果通路的節點 set 中存在，說明有環并傳回此時的節點p。線性周遊，第一次重複一定是入環的第一個節點。
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
HashSet<ListNode> set = new HashSet<>();
ListNode p = head;
while (p != null) {
if (set.contains(p)) {
return p;
}
set.add(p);
p = p.next;
}
return null;
}
時間複雜度：O(n) 空間複雜度：O(n)
思路二：快慢指針 快慢指針如何進行不在贅述。重點在于如何找到入環的第一個節點。
先看一下最終實作：如果快指針周遊完成，沒有環；
如果有環，當快慢指針第一次相遇後，慢指針原地不動，重置快指針回到表頭節點，此時快慢指針都保持每次移動一個節點，當快慢指針第二次相遇的時候，此時相遇節點就是入環的第一個節點。
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
//無環
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
//第一次相遇
if (slow == fast) break;
}
//重置fast
fast = head;
//第二次相遇
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
時間複雜度：O(n) 空間複雜度：O(1)
為什麼兩次相遇一定是入環的第一個節點？
設連結清單有環，且連結清單共有 a+b 個節點，其中 連結清單頭部到連結清單入口 有 a 個節點（不計連結清單入口節點）， 連結清單環 有 b 個節點；設兩指針分别走了 f，s 步，則有：
-
fast
slow
-
fast
slow
fast
slow
- 以上兩式相減得：f = 2nb，s = nb，即
fast
slow
如果一個指針 k 周遊這個有環連結清單一次需要走 k = a + nb 步 (此時 n=1)，此時 k 會回到入環節點。
而目前，
slow
指針走過的步數為 nb 步。是以，我們隻要想辦法讓
slow
再走 a 步停下來，就可以到環的入口節點。
但是此時我們并不知道參數連結清單的 a 是多少！
是以讓
fast
和
slow
第一次相遇後(此時 s = nb)，
fast
從頭節點開始每次走一步，同時
slow
也在環内每次走一步，當
fast
走 a 步到達入環節點時，
slow
共走了 s = a + nb 步，即
slow
也到達入環節點。
是以隻需要第二次
fast
和
slow
相遇即可，此時一定是在入環節點。
NO.202 快樂數 簡單
思路一：HashTable 用一個 HashSet 對每一個數字的每一位求平方相加，結果 num 如果是 1 則說明 n 是快樂數；如果不是 1，判斷 HashSet 中是否已經存在相同的 num，如果存在說明出現閉環，不存在則結果放入 Set 并繼續按位平方求和，判斷結果。
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<>();
//還沒有證明n是快樂數,也沒有發生循環
while (n != 1 && !set.contains(n)) {
set.add(n);
n = helper(n);
}
return n == 1;
}
//按位平方求和
private int helper(int n) {
int num = 0;
while (n > 0) {
int temp = n%10;
num+=temp*temp;
n/=10;
}
return num;
}
不需要考慮平方求和之後的結果num超出範圍，因為 999 的結果是 243 、9999 的結果 324 、、、 9999999999999 的結果 1053 。。。發現，三位數最大的按位平方求和結果還是個三位數，是以無論怎麼求下去，都是三位數。
時間複雜度：O(logn) 空間複雜度：O(n)
思路二：快慢指針 不斷地生成 num ，num 生成下一個 num ，這是一種鍊式的遞減，如果鍊上的某個節點出現了 1 ，說明 n 是快樂數，如果鍊上出現了環，說明 n 不是快樂數。
這種思路下，本問題就轉換成了判斷連結清單是否有環的問題，在判斷的途中順便檢測是否有節點為 1 。
慢指針一次走一個節點，快指針一次走兩個節點，如果存在循環，那麼快慢一定會相遇。
public boolean isHappy(int n) {
int slow = n, fast = helper(n);
while (fast != 1 && slow != fast) {
slow = helper(slow);
fast = helper(helper(fast));
}
return fast == 1;
}
//按位平方求和
private int helper(int n) {
int num = 0;
while (n > 0) {
int temp = n % 10;
num += temp * temp;
n /= 10;
}
return num;
}
時間複雜度：O(logn) 空間複雜度：O(1)
NO.287 尋找重複數 中等
思路一：快慢指針 讀完題并不能立刻想到判環問題。如果将數組建圖，下标位置 i 都有一個連接配接 nums[i] 的邊。本題說有且隻有一個重複元素 num，那麼 num 這個位置至少有兩條邊指向他，是以圖裡一定有環，而這個重複元素 num 就是環的入口。
問題變成了找環的入口問題，就變成了上面的 NO.142 環形連結清單 II。差別僅在于本題是數組而已。
依然快慢指針，雖然本題不是一個連結清單，但是根據前面所說的建圖後有了連結清單的性質(下标 i -> nums[i])，是以移動一步就是
slow = nums[slow]
，同樣的走兩步就是
fast = nums[nums[fast]]
。
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
//第一次相遇
if (slow == fast) break;
}
//重置一個指針,快慢指針都每次一個步長
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
//第二次相遇就是環入口
return slow;
}
時間複雜度：O(n) 空間複雜度：O(1)
本人菜鳥，有錯誤請告知，感激不盡！
更多題解源碼和學習筆記：github 、CSDN 、M1ng