Hust_YangXian
Hust_YangXian
## 0.1 学习数据结构和算法的框架思维 ```cpp //数组遍历框架 void traverse(int[] arr){ for(int i=0;i
## 二叉搜索树操作集锦 ```cpp void traverse(TreeNode root) { // root 需要做什么？在这做。 // 其他的不用 root 操心，抛给框架 traverse(root.left); traverse(root.right); } ``` - 98. 验证二叉搜索树 - 100. 相同的树 #### 在 BST 中查找一个数是否存在 ```cpp boolean...
## 0.3 动态规划 动态规划的一般形式是求最值, 最长递增子序列, 最小编辑距离等等 求解动态规划的核心问题是 穷举 动态规划的特点: - 存在 **重叠子问题**, 如果暴力穷举的效率极其低下, 那么需要 备忘录或者DP table来优化穷举过程, 避免不必要的重复计算; - 具备 **最优子结构**, 通过子问题的最值得到原问题的最值; 子问题之间必须相互**独立**; - 只有列出正确的**状态转移方程**才能正确的穷举; > 明确状态 -> 定义dp数组/ 函数的含义 ->...
## 0.4 回溯算法详解 解决一个回溯问题, 实际上就是一个决策树的遍历过程. 思考三个问题: 1. 路径, 就是已经做出的选择 2. 选择列表: 也就是你当前可以做的选择 3. 结束条件: 也就是到达决策树底层, 无法再做选择的条件 回溯算法的框架: ```python result=[] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表:...
## 0.5 二分 [[二分讲解参考]](https://blog.csdn.net/CCSGTC/article/details/80586181) - 左闭右开 [l,r） ```cpp int l=0,r=n; while(l0) { if(k%1==1)result=result*A; k=k/2; result=result*result; } return result; } ``` - 二分搜索题集 [[leetcode]](https://leetcode-cn.com/tag/binary-search/) - [ ] (困难)Leetcode 4. 寻找两个有序数组的中位数 [[problem]](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)...
## 0.6 滑动窗口 ### 滑动窗口 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。 2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T...
## 最优子结构 符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果 让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。 - 求一棵二叉树的最大值 ```cpp int maxVal(TreeNode root) { if (root == null) return -1; int left = maxVal(root.left); int right = maxVal(root.right); return max(root.val, left, right); }...
## 动态规划设计：最长递增子序列  ### 动态规划解法 动态规划的核心设计思想是数学归纳法。 dp[i]表示以nums[i]这个数结尾的最长上升子序列的长度; 那么我们的最终结果就是求dp[i]的最大值; ```cpp int res=0; for(int i=0;i
## 编辑距离 (递归解法+ DP table) - 递归解法 ```cpp int dp(int i,int j){ if(i==-1)return i+1; if(j==-1)return j+1; if(s1[i]==s2[j]) return dp(i-1,j-1); else{ return min( dp(i-1,j-1), dp(i-1,j), dp(i,j-1) )+1; } return dp(s1.length()-1,s2.length()-1); }...
## 高楼扔鸡蛋问题 题目是这样：你面前有一栋从 1 到 `N` 共 `N` 层的楼，然后给你 `K` 个鸡蛋（`K` 至少为 1）。现在确定这栋楼存在楼层 `0