每周刷题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 初始为哑结点

  • 查找常用字符

    1
    2
    3
    4
    5
    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个节点
    快慢指针

总结

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

1
2
3
for status in status_list:
subproblem
base_statsu 与 subproblem 求最值

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

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

使用搜索:谷歌必应百度