面经问题整理Part5~9：散装知识&项目&智力算法题

反转链表

prev = cur
while cur:
	temp = cur.next
  cur.next = prev
  prev = cur
	cur = temp

合并链表

dummy = ListNode(-1)
cur = dummy
while cur1 and cur2:
	if cur1.val < cur2.val:
		cur.next = cur1
		cur1 = cur1.next
	else:
		cur.next = cur2
		cur2 = cur2.next
	cur = cur.next
	
if cur1:
	cur.next = cur1
if cur2:
	cur.next = cur2
return dummy.next

二分

找最左满足的值

if nums[mid] ≥ target , right= mid -1 ,return left

找最右满足

if nums[mid] ≤ target, left = mid + 1, return right

插入到比当前大的最小值

插入到比当前小的最大值

买卖股票i

只允许交易一次，利润最大 = 当前价格 -历史最低价

def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        minPrice = float('inf')
        n = len(prices)
        profit = [0] * n
        for i in range(n):
            minPrice = min(minPrice, prices[i])
            profit[i] = prices[i] - minPrice
        return max(profit)

LRU

字典+双向链表

get 注意每次 get 如果存在，要更新到最前