摘要： 二叉树的最大深度 解题思路 二叉树的最大深度 = max(左子树的最大深度，右子树的最大深度)+1 代码实现 点击查看代码 class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; 阅读全文

摘要： 大家好，今天我们来学习区间 \(DP\)。 最长回文子序列 解题思路 思路 1 由于回文子序列从左读、从右读都是一样的，所以我们可以求 \(s\) 和其 反转过后的 最长公共子序列。 点击查看代码 class Solution { public: int longestPalindromeSubse 阅读全文

摘要： 买卖股票的最佳时机 解题思路 低价买入，高价卖出。 从左到右枚举卖出价格 \(prices[i]\)。要想获得最大利润，哪天买入最好？在股票价格最低的那天买入。 注意，买入日期必须在卖出日期之前，所以我们求的是从 \(prices[0]\) 到 \(prices[i-1]\) 的最小值，可以用一个变 阅读全文

摘要： 最长公共子序列 解题思路 子序列本质上就是选或不选，考虑最后一对字母，分别为 \(x\) 和 \(y\)，那么根据选或不选，将会出现以下四种情况，分别是： 不选 \(x\) 不选 \(y\) 不选 \(x\) 选 \(y\) 选 \(x\) 不选 \(y\) 选 \(x\) 选 \(y\) 回溯三问 阅读全文

摘要： 0-1背包问题 有 \(n\) 个物品，第 \(i\) 个物品的体积为 \(w[i]\)，价值为 \(v[i]\)。每个物品至多选一个，求体积和不超过 \(capacity\) 的最大价值和。 回溯三问 当前操作？ 枚举第 \(i\) 个物品选或不选。不选，剩余容量不变；选，剩余容量减少 \(w[i 阅读全文

摘要： 状态定义？状态转移方程？ 1. 打家劫舍 1.1 解题思路 理解题目：我需要选择一些数，使它们的和最大，并且选择的数字不能是相邻的。 我们先将这道题看成回溯。 考虑最后一个房子选或不选。 如果不选，问题就变成 \(n-1\) 个房子的问题。 如果选，问题就变成 \(n-2\) 个房子的问题。 回溯三 阅读全文

摘要： 前言 如果要构造长度为\(2\)的字符串，可以写一个二重循环： for x in "abc" for y in "def" 外层枚举第\(1\)个字母，内层枚举第\(2\)个字母，这样可以。 但是如果要构造长度为\(3\)或者\(4\)或者不确定呢？ 原问题：构造长度为\(n\)的字符串\(\rig 阅读全文

摘要： 1. 验证二叉搜索树 1.1 解题思路 1.1.1 方法一：前序遍历 根据定义，二叉树的左右子树一定也是二叉搜索树。 因此： 原问题：判断一棵树是否是二叉搜索树 子问题：判断一棵树的左子树/右子树是否是二叉搜索树 在递归时，除了传入节点，还需要传入该节点所处开区间的范围。 对于每个节点，先判断它的节 阅读全文

摘要： 1. 计算二叉树的最大深度 1.1. 解题思路 所谓二叉树的深度，指的是从根节点到最远叶子结点的最长路径上节点的个数。 思考整棵树与左右子树的关系。 整棵树的最大深度 = \(max\)(左子树的最大深度，右子树的最大深度) + 1 原问题：计算整棵树的最大深度 子问题：计算左/右子树的最大深度 程 阅读全文

摘要： 1 删除链表中的节点 1.1 解题思路 由于要删除的节点一定不是末尾节点，且又不能存在于链表中。所以我们的做法可以是：将node的next指针所指向的下一个节点的值赋值给node，删除node->next即可。 1.2 代码实现 点击查看代码 class Solution { public: voi 阅读全文