12天刷题Sprint

10.15 - 广度优先遍历 BFS - Interview-Oriented Sprint - 6 Days Left

LC 题目：2题
- 打开转盘锁 （Queue， Set）
- 岛屿数量

总结：
- BFS一般用来解决【图】中找到七点start到终点target的最近距离 (Queue核心数据结构， Set避免重复)
- DFS算法其实就是回溯算法 (ArrayList最后一个元素的增减来回溯，递归来调用)

模板题：
- 二叉树的最小深度
- 从上到下打印二叉树

10.16 Review Day - Interview-Oriented Sprint - 5 Days Left

-. 二分查找：每一次比较都使算法搜索范围减半
    1.搜索区间 while（left <= right）
    2.找到target，看情况收缩边界
    3.if检查出界情况
    例：寻找一个数
    code：[left, right] 搜索区间

- 动态规划：存在最优子结构 ，一般形式就是求最值
    0. 暴力的递归解 -> 带备忘录的递归解法 -> 迭代的动态规划解法
    1. 状态定义 + 初始状态 -> 列出状态转移方程
    2.自顶向下：递归 + 备忘录剪枝
    3.自底向上：DP Table（调优:压缩状态）+动态规划
     例：零钱兑换
            最长递增子序列
    code： dp[] 状态定义

- 回溯算法（深度优先遍历）：本质上是决策树的遍历问题
    1. 路径、选择列表、结束条件
    2.set、list、used数组来剪枝已做出的选择
    3.start参数：排除索引start前的选择（组合问题）
    3.全局变量，避免参数过长
    例：全排列（无重复元素数组）
    code： List<Integer> list = new ArrayList<>(); 路径

- 广度优先遍历：一幅‘图’中找到从起点start到终点target的最近距离
    1. 队列queue为核心数据结构去记录每一层的节点
    2.循环条件：队列不为空，且没到达终点，则继续向节点四周扩散，并将curr的相邻节点加入队列，移出curr节点
    3.如果有循环则可用Set避免走回头路
    4.如果要记录最短路径的长度，则记得记录/更新扩散的步数
    例：二叉树的最小深度、二叉树的层序遍历（用list记录结果，最后转array）
    code： Deque<Node> queue = new ArrayDeque<Node>();

- 滑动窗口（双指针技巧）：维护一个窗口，不断滑动，更新答案
    1.扩大窗口右侧边界，收缩窗口左侧边界（维护窗口大小）
    2. 用对列来实现滑动窗口内的单调递减队列，queue.peek（）为窗口内最大值
    例：滑动窗口的最大值
    code：Deque<Integer> queue = new ArrayDeque<Integer>(); 滑动窗口内的单调递减队列
               Set<Character> set = new HashSet<Character>(); 结果去重

- 分治算法：分解 -> 解决（触底）-> 合并
    1.分解：分解原问题为结构相同的子问题
    2.解决：分解到某个容易求解的边界之后，进行递归求解
    3.合并：将子问题合并成原问题的解
    例：归并排序 （在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间）

- 排序：
     1.归并排序 void sort(int[] nums, int left, int right, int[] temp);
                       void merge(int[] nums, int left, int mid, int right, int[] temp);

     2.堆排序 void sort(int[] nums);
                   void heapify(int[] nums, int index, int len);
                   void swap(int[] nums, int a, int b);

     3.快速排序 void sort(int[] nums, int left, int right);
                      int partition(int[] nums, int left, int right);
                      void swap(int[] nums, int a, int b);

10.17 - 面筋日 - Interview-Oriented Sprint - 4 Days Left

笼统的复习了下比较常见的面筋题，大致思路有了，很多细节还是有问题。
btw，今天参加了下夜喵赛，md，哭了。愣是推不出dp状态转移方程，后来看题解说要用前缀和，情景题真的比模板题难好多。

- 215. 数组中第K大个元素 （基于快排、基于堆排）

- 124. 二叉树的最大路径和  (对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况)

- 468. 验证IP地址 (分IPv4和IPv6)

- 236. 二叉树的最近公共祖先 （左右子树递归调用，都不为null，只有一个不为null，均为null）

- 206. 反转链表 （迭代prev，curr，next）

- 91. 解码方法 （分四种情况，第i位与第i-1位能不能组成10-26之间的数字，再细分）

- 94. 二叉树的中序遍历 （中序遍历不忘左链入栈）

- 15. 三数之和 （先对数组进行排序，遍历排序后的数组）

- 121. 买卖股票的最佳时机 （动态规划  前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}）

- 48. 旋转图像 （先转置后镜像对称）

- 543. 二叉树的直径 （类似二叉树中最大路径和）

- 53. 最大子序和 （动态规划/分治）

10.18 - 面筋日2 - Interview-Oriented Sprint - 3 Days Left

- 4.寻找两个正序数组 （二分查找）

-110.平衡二叉树 (从底至顶，前序遍历；从顶至底，计算depth)

-146.LRU缓存机制 (LinkedHashMap; HashMap, DoubleList, Node)

-103.二叉树的锯齿形层次遍历 (BFS, 奇翻偶不翻)

-450.删除二叉搜索树的节点 (分三种情况，待删除的节点在左子树中，在右子树中，就是root)

-415.字符串相加 （BigInteger；carry 计算进位）

-62.不同路径 （动态规划+状态压缩；记忆化递归；组合排列）

-22.括号生成  （回溯算法+剪枝；广度优先遍历）

-1.两数之和 （HashMap）

-79.单词搜索 (回溯算法)

-200.岛屿数量 （BFS；DFS；并查集）

-89.格雷编码 （回溯算法）

-98.验证二叉搜索树 （递归：中序遍历； 迭代）

10.19 - 并查集、前缀和、差分数组 - Interview-Oritened Spirnt - 2 Days Left

- 并查集：解决图论中【动态连通性】问题
            - 联通分量个数、存储树、记录树的“重量”；初始化、union、find、connected
            例：岛屿数量

- 前缀和：开辟一个前缀和数组进行预处理
             -前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累计和
             例：和为k的子数组

- 差分数组：开分一个差分数组进行预处理
            -差分数组的主要使用场景是频繁对原始数组的某个区间元素进行增减

10.19 - 链表、树- Interview-Oritened Spirnt - 2 Days Left

练习了一些基础的数据结构，明天尝试栈（单调栈)，队列（双端队列），堆（大根堆，小根堆)

链表：
    -反转一段链表 (反转前n个链表，需要一个全局变量记录后驱节点)
    -复杂链表的复制（源地址修改法；HashMap，Map中存的是（原节点，拷贝节点））
    -两个链表的第一个公共节点（set；先统计两个链表的长度；双指针）

树:
    -二叉树中和为某一值的路径（回溯）
    -平衡二叉树（后序遍历+剪枝；先序遍历+判断深度）
    - 序列化和反序列化二叉搜索树（序列化：后序遍历，反序列化：通过后序遍历+二叉搜索树的性质）

楼主能附上题号么? 我跟着楼主的节奏, 但是有些题不好找

hzn942 发表于 2020-10-20 03:05
楼主能附上题号么? 我跟着楼主的节奏, 但是有些题不好找

好滴，后面附上题号，我想你应该想问的是反转一段链表吧，这个原题是反转链表II，但是我这个题目名称这样不好记忆，就自己换了一下hhh。别的应该都是lc原题了

BartSu 发表于 2020-10-20 10:18
好滴，后面附上题号，我想你应该想问的是反转一段链表吧，这个原题是反转链表II，但是我这个题目名称这样 ...

谢谢楼主.

不知道楼主是不是用的中文版leetcode..我的是英文版,  所以每次需要猜测对应的英文翻译然后再去搜索, 所以感觉有点难找.

hzn942 发表于 2020-10-20 10:49
谢谢楼主.

不知道楼主是不是用的中文版leetcode..我的是英文版,  所以每次需要猜测对应的英文翻译然后 ...

是的，用的是国区的leetcode-cn