Sofie 舒霏的部落格

因為這系列做起來很快，所以就索性一次貼在一篇文了！
PART 1－344. Reverse String (Easy)

今天要來解的題目是 Leetcode－7. Reverse Integer，難度為 Easy，
而我所使用的語言是 python3

今天要來解的題目是 Leetcode－152. Maximum Product Subarray，難度為 Medium，
而我所使用的語言是 python3

Kadane's Algorithm for solving Maximum Subarray
如果你已經知道某 array A 從 「頭」 加到「第 i 個數字」的最大值，

今天要來解的題目是 Leetcode－238. Product of Array Except Self，難度為 Medium，
而我所使用的語言是 python3

今天來做一點有趣的實作吧！
 

Queen's Gambit 已經紅了一陣子了，
或許你還在觀望，「關於西洋棋的影集？」聽起來不是特別有趣，

今天要來解的題目是 Leetcode－42. Trapping Rain Water ，難度為 Hard，
而我所使用的語言是 python3

今天要來解的題目是 Leetcode－142. Linked List Cycle II ，難度為中等，
而我所使用的語言是 python3
 
壹、理解題目
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Notice that you should not modify the linked list.
簡單而言，就是
如果有 cycle：回傳 cycle 的起始點
如果沒有：回傳 None
 
其實這題是 141 的延伸題（如何判斷有沒有 cycle？）
在做這題之前，可以先點進這裡看 141 的解法喔！
同樣會使用到此演算法：Floyd's Tortoise and Hare (Cycle Detection)
 
貳、開始解題
解決 141 後，你應該就知道如何判斷是否有 cycle 了！
就是龜兔第二次相遇的時候，但
他們第二次相遇的 node 不一定會是 cycle 的起始點 (cycle head)，
 
那麼 要如何找到 cycle head 呢？
在結束第一階段－讓兩者相遇之後，
讓 tortoise 回到原點，而 hare 每次只走一步 (just like tortoise)，
直到兩者再次相遇，那個點就會是 cycle head！
 
Why？
所有的 case 都可以簡化成以下的圖
L 是起始點和 cycle head 的距離、x 是 cycle head 到第一次見面的距離、C 是整個 cycle 的長度

今天要來解的題目是 Leetcode－141. Linked List Cycle，難度為易，
而我所使用的語言是 python3