经典思路题

算法

141. 环形链表

  1. 题意: 判断链表是否有环
  2. 思路: 快慢指针
  3. 代码:
1
2
3
4
5
6
7
8
9
def hasCycle(self, head: Optional[ListNode]) -> bool:
	slow = fast = head

	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if slow == fast:
			return True
	return False
  1. 备注: 边界情况难以判断，建议背模板

121. 买卖股票的最佳时机

  1. 题意: 只能买卖一次
  2. 思路: 维护 min_price 和 max_profit
  3. 代码:
1
2
3
4
5
6
7
def maxProfit(self, prices: List[int]) -> int:
	min_price = prices[0]
	max_profit = 0
	for p in prices:
		max_profit = max(max_profit, p-min_price)
		min_price = min(min_price, p)
	return max_profit

122. 买卖股票的最佳时机 II

  1. 题意: 可以买卖多次
  2. 思路: 假设一直买卖，把 prices[i+1] - prices[i] 为正值的都加起来
  3. 代码:
1
2
3
4
5
6
7
def maxProfit(self, prices: List[int]) -> int:
    max_profit = 0
    for i in range(len(prices)-1):
        diff = prices[i+1]-prices[i]
        if diff > 0:
            max_profit += diff
    return max_profit

215. 数组中的第K个最大元素

  1. 思路: 堆
    1. 维护一个大小为 K 的最小堆, 里面存着到目前为止的前 K 大元素
      • 多了就移除堆顶元素 (最小值)
    2. 完成遍历后, 堆顶元素就是前 K 大元素的最小值, 即第 K 大元素
  2. 代码:
1
2
3
4
5
6
7
def findKthLargest(self, nums: List[int], k: int) -> int:
    min_heap = []
    for x in nums:
        heapq.heappush(min_heap, x)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]