【刷题】 重难点备忘录
目录
各种操作
链表反转：
数据结构
OrderedDict 有序字典（哈希表 + 双向链表）
PriorityQueue 部分排序
各种操作 链表反转：
206. 反转链表
#怎么突然报错了 哦 while(head) 应该是head1 可是 这俩变量不应该一样吗 #不一样！ head还剩1 head1是空#怎么突然报错了
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#原地逆置 头插法
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
rev=None
head1=copy.deepcopy(head) # 直接修改head会破坏链表结构 这样修改也会的 #而你自己写的头插法 是不会修改head的
while(head1):
#第一次head就断开了
# print_list('head',head)
# print_list('head1',head1)
rev,rev.next,head1=head1,rev,head1.next #因为rev=head1？还是因为你的头插法是用val新建node 不是直接赋值 可是那样空间复杂度更大？
#上面head1=copy.deepcopy(head) 就不会修改原链表了 因为先把head赋值给rev 又rev.next=None 所以head只剩第一个元素
# print_list('rev',rev)
# print_list('head',head)
# print_list('head1',head1)
return rev
#链表输出
def print_list(s,head):
print(s,end=" ")
while(head):
print(head.val,end=' ')
head=head.next
print()
234. 回文链表
#cleaned11 45 ->
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#翻转前一半 对比
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
slow,fast=head,head
rev=None
while(fast and fast.next):
fast=fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast:
slow = slow.next
while(slow and slow.val==rev.val):
slow,rev=slow.next,rev.next
return not slow
数据结构
OrderedDict 有序字典（哈希表 + 双向链表）
146. LRU缓存机制
class LRUCache(OrderedDict):
def __init__(self, capacity: int):
self.capacity=capacity
def get(self, key: int) -> int:
if key in self:
self.move_to_end(key)
return self[key]
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key) #已经在字典里了 就移到最后
self[key]=value #因为可能key已经有了 但是value的值是新的 即改写
# else:
# self[key]=value #重写不会改变顺序 但这样写清楚 不对 放在else里就错了 why
if len(self)>self.capacity:
self.popitem(last=False)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
PriorityQueue 部分排序
LeetCode 中的 PriorityQueue 总结：https://www.dazhuanlan.com/2019/12/06/5de9e52da6794/
面试题40. 最小的k个数
from queue import PriorityQueue
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if not arr or not k: return []
n=len(arr)
pq=PriorityQueue()
for i in arr:
# print(pq.queue)
pq.put((-i,i))
if pq.qsize()>k: #超出后 弹出最小的
pq.get()
# print(pq.queue)
re=[] #[1,2] 或者 [2,1] 输出逆序也可以
while not pq.empty(): #不能直接pq来判断空 否则会死循环
re.append(pq.get()[1]) #虽然pq.queue是无序 但是出队时是有序 怎么看有序的列表呢
return re
# Solution().getLeastNumbers( [3,2,1],
# 2 )
347. 前 K 个高频元素
#80 29 哇 和用heapq一模一样 heapq的复杂度 到底是知乎里说的logn 还是leetcode题解里的logk 但是明明python库里写了是和sorted(...)[:k]一样 那应该就是logn 可是为啥提交 时间一样
#用pq
from queue import PriorityQueue
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counter=Counter(nums)
# print(counter)
# print(dict(counter))
pq=PriorityQueue()
for key,freq in counter.items():
# print(pq.queue)
if len(pq.queue)pq.queue[0][0]: #只保存freq最大的k个数哦
head=pq.get()
# print('head',head)
pq.put((freq,key))
return [e[1] for e in pq.queue] #取出key
# Solution().topKFrequent( [1,1,1,2,2,3,4,4,4] ,2)
239. 滑动窗口最大值
作者：梯度提升决策树
