每周刷题202010_26_1101

前言

每月从困难题开始到困难题结束。
二叉树的前序遍历
独一无二的出现次数
连续出现的数字
超过经理收入的员工
查找重复的电子邮箱
从不订购的客户
求根到叶子节点数字之和
部门工资最高的员工
岛屿的周长
O(1) 时间插入、删除和获取随机元素 - 允许重复
单词拆分 II

题解与思路

• 二叉树的前序遍历
  递归方式比较简单，容易理解，也是解决树相关问题最常用的方法。循环迭代的方式实际上就是我们自己实现递归出栈入栈。看的大佬的颜色标记法

  def preorder(root):
  	res = []
  	stack = []
  	while (root or stack):
  		if root:
  			res.append(root.val)
  			stack.append(root)
  			root = root.left
  		else:
  			root = stack.pop().right
  	return res			

• 独一无二的出现次数
  比较简单，count 统计，去重比较长度即可

  def uniqueOccurrences(arr) -> bool:
      counts = [arr.count(i) for i in set(arr)]
      return len(counts) == len(set(counts))

• 求根到叶子节点数字之和
  dfs，每个根节点到叶子节点组成的数字值可以看做是父节点的数字 * 10 + 当前节点的 value。

• 岛屿的周长
  前提条件是岛中不存在湖，从(0, 0) 开始遍历，假设开始处就是岛屿，那么周长加 4，如果其下边或者右边也是岛屿，会合并掉两条边，所以岛屿周长需要减 2。以此往复，遍历所有网格。

• O(1) 时间插入、删除和获取随机元素
  使用 list 维护元素列表，使用 dict 维护元素值索引。list append O(1) 时间复杂度插入，通过将要删除的元素与列表最后一个元素相交换 + pop 来达到 O(1) 删除元素

• 单词拆分 II