LeetCode算法题解存档：动态规划与树型结构

资源摘要信息:"Leetcode走方格起点到终点的编程题目是Leetcode上的经典问题，涉及多种编程技巧和算法。在此存档备份自己的Leetcode做题记录，主要涉及到的知识点包括双指针、动态规划、贪心算法、拓扑排序、字典树、树型动态规划、深度优先搜索（dfs）、滑动窗口、中序遍历、图的深拷贝、字符串处理等。" 知识点详细说明： 1. 双指针：通常指在同一个数据结构（如数组或链表）中使用两个变量作为指针来遍历或比较元素的一种方法，常见于数组或链表操作中，能够提高算法效率。 2. 动态规划（Dynamic Programming, DP）：一种算法思想，通过将问题分解为更小的子问题，并存储这些子问题的解（通常存储在数组或其他数据结构中），避免重复计算，从而减少计算量。本记录中的动态规划问题强调了状态转移的邻近性质，即状态转移只依赖于相邻的状态。 3. 贪心算法：在对问题求解时，总是做出在当前看来是最好的选择，即局部最优解，目的是希望通过对局部最优解的选择，最终能导致全局最优解的算法。贪心算法并不保证会得到最优解，但是效率很高。 4. 拓扑排序：在有向图中对顶点进行排序，使得对于任何一条有向边(u, v)，顶点u都在顶点v之前。常用于解决任务调度、课程安排等问题。 5. 字典树（Trie）：一种树形数据结构，用于高效地存储和检索字符串数据集中的键，常用于处理字符串相关问题，如字符串匹配、前缀查询等。 6. 树型动态规划：动态规划的一种形式，特别适用于解决树状结构的问题，其中状态转移往往与相邻节点的状态有关。 7. 深度优先搜索（dfs）：一种用于遍历或搜索树或图的算法。该方法沿着树的分支进行深度探索直到目标节点，再回溯到上一节点继续探索，直到所有的节点都被访问过。 8. 滑动窗口+HashMap：在数组或字符串处理中，滑动窗口算法用于在数组或字符串上定义一个窗口，然后在这个窗口上进行各种操作，HashMap（哈希表）用于存储窗口内的元素频率等信息。 9. 二分排序树（Binary Search Tree, BST）的中序遍历：二分排序树是一种特殊类型的树，其中每个节点都具有左子树和右子树，左子树的所有节点值小于其根节点值，右子树的所有节点值大于其根节点值。中序遍历这种树会以递增的顺序访问所有节点。 10. 图的深拷贝：指复制图的每一个节点，同时复制节点之间的所有连接。深拷贝会创建一个新的图副本，其中包含原图节点的复制以及节点间连接的复制。 11. 字符串处理：包括字符串数字求和、字符串数字相乘、验证括号匹配、字符数组的DFS涂色等。这些问题是字符串处理领域的经典算法问题，考查对字符串操作的掌握程度。 12. 快速幂（Fast Powering）：一种高效计算整数幂的算法，通常利用幂的性质，通过迭代或递归的方式减少计算次数。特别需要注意的是最小负数加负号仍为其本身的问题。 13. 后序遍历确定树是否平衡：后序遍历是二叉树遍历的一种方式，遍历顺序是左子树、右子树、根节点。通过后序遍历可以检测二叉树的平衡性，即对于每个节点，左子树和右子树的高度差不超过1。 Leetcode题目记录提供了丰富的算法和数据结构应用场景，能够帮助开发者在实际编程中更熟练地运用这些知识点。通过这些做题记录，可以加深对算法思想的理解和实践应用，提升编程解决问题的能力。