【leetcode】哈希、树、二叉树、堆、二叉堆入门级练习题242 49 194 144 590 589 429 剑指offer40 239剑指offer49347

242.有效的字母异位词（亚马逊、Facebook、谷歌在半年内面试中考过）

class Solution: def isAnagram(self, s: str, t: str) -> bool: return collections.Counter(s) == collections.Counter(t)

49.字母异位词分组（亚马逊在半年内面试中常考）

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: dic = {} for item in strs: key = tuple(sorted(item)) dic[key] = dic.get(key,[]) + [item] return list(dic.values())

1.两数之和（亚马逊、字节跳动、谷歌、Facebook、苹果、微软、腾讯在半年内面试中常考）

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for i,num in enumerate(nums): if num in dic: return [dic[num],i] dic[target - num] = i

94.二叉树的中序遍历（亚马逊、微软、字节跳动在半年内面试中考过）

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: # recursively res = [] self.helper(root,res) return res def helper(self,root,res): if root: self.helper(root.left,res) res.append(root.val) self.helper(root.right,res)

144.二叉树的前序遍历（谷歌、微软、字节跳动在半年内面试中考过）

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] self.helper(root,res) return res def helper(self,root,res): if root: res.append(root.val) self.helper(root.left,res) self.helper(root.right,res)

590.N 叉树的后序遍历（亚马逊在半年内面试中考过）

class Solution(): def postorder(self, root: 'Node') -> List[int]: res = [] self.helper(root,res) return res def helper(self,root,res): if root: for child in root.children: self.helper(child,res) res.append(root.val)

589.N 叉树的前序遍历（亚马逊在半年内面试中考过）

class Solution: def preorder(self, root: 'Node') -> List[int]: res = [] self.helper(root,res) return res def helper(self,root,res): if root: res.append(root.val) for child in root.children: self.helper(child,res)

429.N 叉树的层序遍历

class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: q, res = [root], [] while any(q): res.append([_.val for _ in q]) q = [child for node in q for child in node.children if child] # 利用俩层列表推导式，把每层元素放在一个列表里面 return res

剑指 Offer 40. 最小的k个数（字节跳动在半年内面试中考过）

import heapq class Solution: def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: return heapq.nsmallest(k,arr)

239.滑动窗口最大值（亚马逊在半年内面试中常考）

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: d = collections.deque() out = [] for i,n in enumerate(nums): while d and nums[d[-1]] < n: d.pop() d.append(i) if d[0] == i - k: d.popleft() if i >= k - 1: out.append(nums[d[0]]) return out

剑指 Offer 49. 丑数（字节跳动在半年内面试中考过） 法一：最小堆的方法 O(n logn) 法二：动态规划的办法

# 法一： import heapq class Solution: def nthUglyNumber(self, n: int) -> int: h = [(1, 1)] for _ in range(n): # heapq.heappop(heap)：将heap的最小值pop出heap，heap为空时报IndexError错误 val, fact = heapq.heappop(h) for x in 2, 3, 5: if fact <= x: # heapq.heappush(heap,item):将item，推入heap heapq.heappush(h, (val * x, x)) return val # 法二:动态规划 class Solution: def nthUglyNumber(self, n: int) -> int: dp,a,b,c = [1] * n,0,0,0 for i in range(1,n): n2,n3,n5 = dp[a] * 2,dp[b] * 3,dp[c] * 5 dp[i] = min(n2,n3,n5) if dp[i] == n2:a += 1 if dp[i] == n3:b += 1 if dp[i] == n5:c += 1 return dp[-1]

347.前 K 个高频元素（亚马逊在半年内面试中常考）

import collections import heapq class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count_num = collections.Counter(nums) return heapq.nlargest(k,count_num,key = lambda x:count_num[x])