# 2021/4/10
目錄
3的幂
【題目】
【我的方法】
執行結果：
【其他方法】
執行結果：
回文連結清單
【題目】
【我的方法】
執行結果#1：
執行結果#2：
【其他方法】
執行結果：
【整理之快慢指針】
何為快慢指針
1、找中間值
2、判斷連結清單中的環
3、删除倒數第n個節點
3的幂
【題目】
給定一個整數，寫一個函數來判斷它是否是 3 的幂次方。如果是，傳回 true ；否則，傳回 false 。
整數 n 是 3 的幂次方需滿足：存在整數 x 使得 n == 3x
示例 1：
輸入：n = 27
輸出：true
示例 2：
輸入：n = 0
輸出：false
提示：
-231 <= n <= 231 - 1
進階：
你能不使用循環或者遞歸來完成本題嗎？
【我的方法】
循環。。。
class Solution:
def isPowerOfThree(self, n: int) -> bool:
i = 1
while(i<n):
i *= 3
if i!=n:
return False
else:
return True
執行結果：
執行用時：92 ms, 在所有 Python3 送出中擊敗了66.06%的使用者
記憶體消耗：14.8 MB, 在所有 Python3 送出中擊敗了72.25%的使用者
【其他方法】
@水滴 的評論：
通過檢視相關解析，發現了這個解法，用到了數論的知識，3的幂次的質因子隻有3，而所給出的n如果也是3的幂次，故而題目中所給整數範圍内最大的3的幂次的因子隻能是3的幂次，1162261467是3的19次幂，是整數範圍内最大的3的幂次。
# 借鑒該思路的代碼：
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n>0 and 1162261467%n == 0
執行結果：
執行用時：92 ms, 在所有 Python3 送出中擊敗了66.06%的使用者
記憶體消耗：14.9 MB, 在所有 Python3 送出中擊敗了15.60%的使用者
回文連結清單
【題目】
請判斷一個連結清單是否為回文連結清單。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進階：
你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？
【我的方法】
1、利用棧暴力解決
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head.next:
return True
n = 1
temp = head
while(temp.next):
temp = temp.next
n += 1
# print(n)
if n == 2:
if head.val!= head.next.val:
return False
else:
return True
temp = head
stack = []
i = 0
while(i<n//2):
stack.append(temp.val)
temp = temp.next
i += 1
print(stack)
if n%2!=0:
temp = temp.next
while(temp):
a = stack.pop()
# print(a,temp.val)
if temp.val != a:
return False
temp = temp.next
return True
執行結果#1：
執行用時：1056 ms, 在所有 Python3 送出中擊敗了5.09%的使用者
記憶體消耗：48.6 MB, 在所有 Python3 送出中擊敗了11.27%的使用者
2、利用連結清單的生成方式（前向插入），減小空間複雜度：
如連結清單1->2->3->4->5：
1）先找出中節點3，然後pre指向3，temp指向後面的4
2）開始建立一條新連結清單，即反轉後半截鍊條，具體思路如下圖：
3）兩條鍊條進行比對
【2021/4/10 刷題筆記】Leetcode之容易等級題3的幂回文連結清單
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head.next:
return True
n = 1
temp = head
while(temp.next):
temp = temp.next
n += 1
if n == 2:
if head.val!= head.next.val:
return False
else:
return True
i = 0
pre = head
while(i<n//2-1):
pre = pre.next
i += 1
if n%2!=0:
pre = pre.next
temp = pre.next
head2 = ListNode()
while(temp):
pre.next = temp.next
temp.next = head2.next
head2.next = temp
temp = pre.next
while(head2.next):
if head2.next.val != head.val:
return False
head2 = head2.next
head = head.next
return True
執行結果#2：
執行用時：808 ms, 在所有 Python3 送出中擊敗了27.55%的使用者
記憶體消耗：40.3 MB, 在所有 Python3 送出中擊敗了40.18%的使用者
【其他方法】
@Albert 的評論也是類似的思路：
其一，find mid node 使用快慢指針找到連結清單中點。
其二，reverse 逆序後半部分。
其三，check 從頭、中點，開始比較是否相同。
# 借鑒其思路整理出的代碼
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head.next:
return True
slow = head
fast = head
prev = None
while(fast): # find mid node
slow = slow.next
if fast.next:
fast = fast.next.next
else:
fast = fast.next
while(slow): # reverse
temp = slow.next
slow.next = prev
prev = slow
slow = temp
while(head and prev): # check
if head.val!= prev.val:
return False
head = head.next
prev = prev.next
return True
執行結果：
執行用時：720 ms, 在所有 Python3 送出中擊敗了44.51%的使用者
記憶體消耗：40.3 MB, 在所有 Python3 送出中擊敗了40.93%的使用者
【整理之快慢指針】
何為快慢指針
快慢指針就是定義兩根指針，移動的速度一快一慢，以此來制造出自己想要的內插補點。這個內插補點可以讓我們找到連結清單上相應的節點。
1、找中間值
一般的思路是：先周遊一次連結清單，記錄住一共有多少個節點，然後，再次周遊找尋中點。
利用快慢指針，我們來看看這個問題會變成什麼樣。思路如下：我們把一個連結清單看成一個跑道，假設a的速度是b的兩倍，那麼當a跑完全程後，b剛好跑一半，以此來達到找到中間節點的目的。
最開始，slow與fast指針都指向連結清單第一個節點，然後slow每次移動一個指針，fast每次移動兩個指針。
2、判斷連結清單中的環
還是把連結清單比作一條跑道，連結清單中有環，那麼這條跑道就是一條圓環跑道，在一條圓環跑道中，兩個人有速度差，那麼遲早兩個人會相遇，隻要相遇那麼就說明有環。
快慢指針中，因為每一次移動後，快指針都會比慢指針多走一個節點，是以他們之間在進入環狀連結清單後，不論相隔多少個節點，慢指針總會被快指針趕上并且重合，此時就可以判斷必定有環。
3、删除倒數第n個節點
删除倒數第n個節點，那就等于是要我們先找出待删除元素前一個元素，也就是第n-1個節點。又把這個問題轉化為找連結清單上的某個節點的問題，這是快慢指針最擅長的場景。
那如何找第(n-1)個元素呢？我們一開始就讓fast指針比slow指針快n+1個元素，接下來，兩個指針都是一步一步來往下走。那麼當fast指針走完時，slow指針就剛剛好停留在第(n-1)個元素上。
（參考自：https://www.jianshu.com/p/21b4b8d7d31b）
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)