题目一 前缀树

6.2 1分
image.png

思路

  • 把路径构造成前缀树的形式，然后每一层的节点空格树是相同的，越往深空格越多
  • 对前缀树进行深度优先遍历

image.png

代码实现

  1. 前缀树节点定义 节点保存文件夹名，然后节点的路径保存在TreeMap这个有序表里 key为路径 value为节点，使用有序表的原因是要有序打印
  2. 为什么有四个\\来分隔字符串，因为转义加上正则表达式的需要

image.png

  1. 深度优先遍历

image.png

题目二 二叉树

6.2 20m
image.png

树型DP解法

  • 可以定义一个信息结构体 ，为这颗树所构成有序双向链表的第一个节点和最后一个节点
  • 头结点 的last指向左子树的最后一个节点 next指向右子树的最后一个节点

image.png

题目三 树型dp

6.2 33m
image.png
并且返回最大搜索二叉子树的根节点

思路

  1. 这道题从根节点思考往左树右树要信息的角度考虑，首先考虑没有根节点的情况那么最大子树一定存在左右子树之中，如果根节点参与并且根节点的树是搜索二叉树那么这个树是最大的。
  2. 那么我们需要 左树给我们返回最大搜索子树的node 最大子树的节点个数 以及左树中最大值 最后是左树isBST（是否是搜索树可以省略，因为如果返回最大子树node是它的左孩子的话 就必定是搜索二叉树）
  3. 右树还需要最小值，但是递归行为返回的数据要求一致 所以一共需要5个信息

image.png

实现

  • 如果为空返回null，然后拿黑盒（两个子树的信息）
  • 接着需要拆黑盒返回信息，首先获得最小值和最大值

image.png

  • 然后获取最大搜索子树的节点个数和node，假设左面最大（可能1），如果右面不为null，并且比左面大（可能2）那么保存右面的值

image.png

  • 可能性3，当前node是最大搜索树，满足左右子树都是搜索树并且左面最大值小于x，右面最小值大于x，那么把答案全变重新赋值

image.png
image.png

题目四 二叉树

7.2 24min
image.png

题目五 (贪心 动态规划)

7.2 2m

贪心法

  • 考虑i位置，如果i位置是X的话不放灯，如果i位置是。的话要确保前面的灯不会影响到i位置（避免讨论前面的情况），下个位置是X的话，i位置放灯跳到i+2位置，越界的话break。
  • 下个位置也是点的话，应该在i+1位置放灯然后跳到i+3位置

image.png

题目六 连续子数组最大和 假设答案

6.2 1h 34m
image.png

  1. 定义流程 cur保存累加的数组元素，cur每到一个位置变大了，max就跟踪它，比max大就保存到max，如果cur变为负数则重新置为0，重新累加。

image.png

假设答案找时间最少的流程

  • 假设数组全是负数或0 那么上面流程符合答案
  • 假设从i到j的数组是最大的连续子数组，并且最长，那么有如下两个性质，可以用来判断流程是对的
  • 做这种题 要先假设答案 然后寻找流程 流程的时间复杂度尽可能低

image.png

题目七 子矩阵

6.2 1h 54m
image.png
image.png

  • 把子矩阵转换成单行子数组最大和问题，考虑从第0行开始只包括第0行，然后是第0行~第1行，第0行~第2行，以此类推，两个for循环，每一轮用一个压缩数组保存上面一行累加的值然后计算当前行的最大值。

image.png

代码

image.png