基礎編程題
二分搜索
-
經典二分搜索
需要注意的點
- 循環(huán)條件
left <= right還是left < right- 需要看
left == right是不是可以進入循環(huán) 可能是target嗎 - 需要防止程序死循環(huán) 如果
left == right == mid在循環(huán)體內不能出去 就會構成死循環(huán)
- 需要看
- 左右邊界更新
right = mid - 1還是right = mid
class Solution: def bs(self, nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid + 1 elif nums[mid] < target: left = mid + 1 # 為什么可以+1 因為mid不可能是target else: right = mid - 1 # 同理 這樣也保證了算法可以收斂 不會死循環(huán) return -1 - 循環(huán)條件
-
一個有重復元素的數組中查找 key 的最左位置
跟第一題的區(qū)別：
- 循環(huán)條件
- 邊界更新
- 循環(huán)體內不判斷是否找到目標 循環(huán)體外才判斷 需要考慮出循環(huán)的兩種情況
class Solution: def bs(self, nums, target): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] < target: # 左半部分可以丟掉 并且mid不可能是target left = mid + 1 else: # nums[mid] >= target right = mid # 因為mid可能是target return right if nums[right] == target else -1 # 因為走到這里有兩種情況 找到目標 或者沒有目標
鏈表
-
O(1)時間復雜度刪除鏈表節(jié)點
題目描述：給定單向鏈表的頭指針和一個節(jié)點指針嫉拐，定義一個函數在O(1)時間刪除該節(jié)點。
解題思路：常規(guī)的做法是從鏈表的頭結點開始遍歷，找到需要刪除的節(jié)點的前驅節(jié)點福压，把它的 next 指向要刪除節(jié)點的下一個節(jié)點，平均時間復雜度為O(n)较性，不滿足題目要求呵晚。
那是不是一定要得到被刪除的節(jié)點的前一個節(jié)點呢？其實不用的。我們可以很方面地得到要刪除節(jié)點的下一個節(jié)點怎栽，如果我們把下一個節(jié)點的內容復制到要刪除的節(jié)點上覆蓋原有的內容，再把下一個節(jié)點刪除沮脖，那就相當于把當前要刪除的節(jié)點刪除了塌忽。單向鏈表不能回頭 只能往后面走
class Solution: def deleteNode(self, pHead, Node): if pHead == None or Node == None: return if Node.next: Node.val = Node.next.val Node.next = Node.next.next # 此時確定 Node 位于鏈表尾 elif pHead == Node: # 鏈表只有一個元素 pHead = None else: while pHead.next.next: pHead = pHead.next pHead.next = None return pHead
-
翻轉鏈表
定義兩個指針
pre和cur拍埠，每反轉一個節(jié)點涉及到三個操作：- 連接
cur指針的next - 分別移動指針
pre和cur
關于Python 等號左右多個變量同時賦值
兩個原則：- 等號右邊的變量存放的都是舊的值 等號左邊的變量存放的都是新的值
- 等號左邊的變量會被刷新 注意先后順序 先取值后賦值
class Solution: def ReverseList(self, pHead): prev = None # 輔助節(jié)點 while pHead: pHead.next, prev, pHead = prev, pHead, pHead.next return prev正常的代碼
class Solution: def reverse(self, pHead): prev = None while pHead: tp = pHead.next # 存下下一個節(jié)點 pHead.next = prev prev = pHead pHead = tp return prev遞歸版本：
class Solution: def ReverseList(self, pHead): if not pHead or not pHead.next: # 停止向下遞歸 往回返 return pHead res = self.ReverseList(pHead.next) pHead.next.next = pHead # 連接 pHead.next = None # 尾節(jié)點 return res - 連接
-
判斷鏈表是否有環(huán)
快慢指針 如何證明？
感想： while循環(huán)內部作為函數return出口很常見 while循環(huán)體外往往代表著另外一種情況
class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ fast, slow = head, head while fast and fast.next: fast = fast.next.next slow = slow.next if fast == slow: return True return False
-
找到環(huán)形鏈表的入口
先判斷有沒有環(huán) 代碼同上
之后將快指針移動到鏈表頭 兩個指針同時移動 如何證明土居？枣购？
使用while - else語法區(qū)分出循環(huán)的兩種情況
class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: # 因為出循環(huán)存在兩種情況 所以需要區(qū)分 這里使用while else語法作區(qū)分 return None while head != slow: # 直接移動頭指針 slow = slow.next head = head.next return head
-
計算環(huán)的長度
快慢指針在環(huán)內相遇之后 讓滿指針繼續(xù)移動 再次相遇經過多少步就可以計算環(huán)的長度
-
刪除單鏈表倒數第n個節(jié)點
class Solution: def FindKthToTail(self, head, k): # write code here if head == None or k <= 0: return None # 設定兩個指針 第一個指針指向頭節(jié)點 第二個指向k-1節(jié)點 p1, p2 = head, head i = 0 while p2.next and i < k - 1: p2 = p2.next i += 1 # while 循環(huán)結束 一定要對各種不同的情況進行判斷 if i != k - 1: # 鏈表沒有K個元素 return None while p2.next: p1, p2 = p1.next, p2.next return p1
for循環(huán)版本
class Solution:
def FindKthToTail(self, head, k):
if not head or k <= 0:
return
fast = slow = head
for i in range(k - 1):
if not (fast and fast.next): # 為了保證fast指針最后停下的位置也是非空的 所以加上fast.next
return
fast = fast.next
while fast and fast.next:
fast = fast.next
slow = slow.next
return slow
求鏈表中間節(jié)點
判斷兩個鏈表是否相交
隊列和棧
字符串
排序
-
插入排序
- 左側已排序
- 右側未排序
- 將未排序部分的第一個元素插入到已排序部分的合適的位置
- 插入排序穩(wěn)定 相同值的元素的相對順序不會改變
image.png
def insertionSort(nums):
for i in range(1, len(nums)):
cur, p = nums[i], i # 取出當值位置的數值 因此當前位置可以被填充
while p - 1 >= 0 and nums[p - 1] > cur:
nums[p] = nums[p - 1]
p -= 1
nums[p] = cur
return nums
-
歸并排序
image.png
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right) # 合并左右兩個已經排序的部分
def merge(left, right):
l, r = 0, 0
result = [] # 需要開辟新空間存放排完序的結果
while l < len(left) and r < len(right):
if left[l] < right[r]: # 將left與right較小元素按序加入新序列
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
-
快速排序
效率底 但是容易理解的版本 生成了新的數組
def quicksort(nums): size = len(nums) if not nums or size < 2: # 遞歸出口，空數組或者只有一個元素的數組都是有序的 return nums idx = 0 # 標定點 pivot = nums[idx] # 標定值 less_part = [nums[i] for i in range(size) if nums[i] <= pivot and idx != i] great_part = [nums[i] for i in range(size) if nums[i] > pivot and idx != i] return quicksort(less_part) + [pivot] + quicksort(great_part)正常 版本 直接在原始數組上修改
image.pngdef quickSort(nums, first, last): splitpoint = partition(nums, first, last) quickSort(nums, first, splitpoint - 1) quickSort(nums, splitpoint + 1, last) def partition(nums, first, last): rand = randint(first, last) # 優(yōu)化擦耀，隨機取標定點棉圈，以解決近乎有序的列表 nums[first], nums[rand] = nums[rand], nums[first] pivot = nums[first] left = first + 1 right = last while True: # 這里使用了雙路快排，以解決有大量相同值的列表 while left <= right and nums[left] < pivot: left += 1 while right >= left and nums[right] > pivot: right -= 1 if left > right: break else: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 # 這兩行代碼必須有 否則程序可能死循環(huán) 測試樣例 [3,2,2,2,3] nums[first], nums[right] = nums[right], nums[first] # right處于<=v部分最后一個元素 return right
