每周刷题202010_12_16

前言

一开始刷题，不看题解，根本不会😂。开始思路的积累。所有的代码提交在 some_thing_python
斐波那契数
零钱兑换
分割等和子集
从前序与中序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树
二叉搜索树的最小绝对差
两两交换链表中的节点
查找常用字符
填充每个节点的下一个右侧节点指针
填充每个节点的下一个右侧节点指针 II
有序数组的平方
N皇后 II
删除链表的倒数第N个节点

题解

• 斐波那契数
  递归解决，dp table 剪枝。

• 零钱兑换
  动态规划，加一个 dp 函数，明确 base 状态，状态转移为 min(res, 1 + dp(n-coin))，明确边界及子问题无解的情况

• 分割等和子集
  明确等和的条件

  • 等和子集，和一定是偶数
  • 等和子集，列表中最大元素肯定要小于等于二分之和
  • 等于二分之和，一定可以切割
  • 大于二分之和，一定不能切割
  • 小于二分之和，排序后依据最大元素找寻子集

• 从前序与中序遍历序列构造二叉树
  递归解决，其实就是找到根节点，得到左子树长度，划分左右子树，切割出左右子树的前中序遍历，开始递归。

• 二叉搜索树的最小绝对差
  一棵 BST，前序遍历是递增序列。最小值的话肯定是两两相邻最小。直接前序遍历，对差值及初始节点赋值一个初始值

• 两两交换链表中的节点
  依赖哑节点，temp -> node1 -> node2 => temp -> node2 -> node1， tmep 初始为哑结点

• 查找常用字符

  res = []
  base_char = array(0)
  for k in base_char:
  	nums = [a.count(k) for a in array]
  	res += [k]*nums

• 填充每个节点的下一个右侧节点指针
  BFS 广度优先遍历，利用 queue 来存储每一层的节点，然后遍历修改指针

• 有序数组的平方
  这个最简单了，sorted + 列表生成式。

• N皇后II
  符合条件做选择 -> backtrack 递归 -> 撤销选择。N 皇后横竖斜不能选择转换为皇后可以放置在哪一列

• 删除链表的倒数第N个节点
  快慢指针

总结

简单的动归问题就是未剪枝后的递归

for status in status_list:
	subproblem
	base_statsu 与 subproblem 求最值

链表相关，哑节点是个不错的选择

树相关，比如 BST 本质就是前序遍历，在遍历的过程中做一些操作。BFS 依靠队列