Posts

刷题网站： LeetCode大神_灵茶山艾府 LeetCode_Hot100 python常用数据结构：点击展开：Python常用数据结构及其基本操作 """ Python 常用数据结构（对应 C++ STL）及基本操作 ================================================ C++ Python ------------------------- vector list stack list queue collections.deque unordered_map dict unordered_set set """ # ========================================================== # 1. 数组 / 动态数组 # C++: vector # Python: list # ========================================================== arr = [1, 2, 3] # 创建数组 # 插入元素 arr.append(4) # 尾部插入 O(1) # 在指定位置插入 arr.insert(1, 10) # index=1 插入 10 -> O(n) # 删除尾部 arr.pop() # 删除最后一个元素 O(1) # 删除指定位置 arr.pop(1) # 删除 index=1 # 修改元素 arr[0] = 100 # 查找元素 print(arr[1]) # 遍历数组 for x in arr: print(x) # ========================================================== # 2. 栈 (Stack) # C++: stack # Python: list # ========================================================== stack = [] # 入栈 push stack.append(1) stack.append(2) stack.append(3) # 查看栈顶 print(stack[-1]) stack.top() # 出栈 pop stack.pop() # 判断是否为空 if not stack: print("stack empty") # ========================================================== # 3. 队列 (Queue) # C++: queue # Python: collections.deque # ========================================================== from collections import deque q = deque() # 入队 q.append(1) q.append(2) q.append(3) # 出队 q.popleft() # 查看队首 print(q[0]) # 查看队尾 print(q[-1]) # BFS常用 while q: node = q.popleft() # ========================================================== # 4. 哈希表 / 字典 # C++: unordered_map # Python: dict # ========================================================== mp = {} # 插入 mp["a"] = 1 mp["b"] = 2 # 修改 mp["a"] = 100 # 查询 print(mp["a"]) # 判断key存在 if "a" in mp: print("exist") # 删除 del mp["a"] # 遍历key for k in mp: print(k) # 遍历key-value for k, v in mp.items(): print(k, v) # ========================================================== # 5. 集合 # C++: unordered_set # Python: set # ========================================================== s = set() # 插入 s.add(1) s.add(2) s.add(3) # 删除 s.remove(2) # 删除（如果不存在不会报错） s.discard(10) # 查询 if 1 in s: print("exist") # 遍历 for x in s: print(x) # ========================================================== # 6. 初始化技巧（刷题常用） # ========================================================== # 初始化数组 arr = [0] * 10 # 初始化二维数组 grid = [[0]*5 for _ in range(5)] # 初始化dict mp = {"a": 1, "b": 2} # 初始化set s = {1,2,3} # 初始化队列 q = deque([1,2,3]) # ========================================================== # 7. 常见复杂度总结 # ========================================================== """ list ---- append O(1) pop() O(1) insert O(n) 访问 O(1) stack ----- push O(1) pop O(1) deque ----- append O(1) popleft O(1) dict ---- insert O(1) find O(1) delete O(1) set --- insert O(1) find O(1) delete O(1) """ DAY 1 1.两数之和 O(n^2): class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i,num1 in enumerate(nums): if target-num1 in nums[i+1:]: j=nums[i+1:].index(target-num1)+1+i return [i,j] 哈希表O(n): ...