从 2022 年开始，我将做题的进度全都会移到我的个人网站上。
当中的解法可能不是最优解，就当作是找做题的感觉。
| Title | Difficulty | Category | Finished | Solution |
|---|---|---|---|---|
| 剑指 Offer II 001. 整数除法 | Easy | 位运算 | ✔️ | Solution(Python) |
| 剑指 Offer II 002. 二进制加法 | Easy | 位运算, 数学, 字符串 | ✔️ | Solution(Python) |
| 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 | Easy | 位运算, 数学, 递归 | ✔️ | Solution(Go) |
| 剑指 Offer 30. 包含min函数的栈 | Easy | 栈, 数组 | ✔️ | Solution(Go) |
| 剑指 Offer II 004. 只出现一次的数字 | Medium | Hash表 | ✔️ | Solution(Go) |
| 剑指 Offer II 005. 单词长度的最大乘积 | Medium | 位运算 | ✔️ | Solution(Go) |
| 剑指 Offer II 006. 排序数组中两个数字之和 | Easy | Hash表 | ✔️ | Solution(Go) |
| 剑指 Offer II 007. 数组中和为 0 的三个数 | Medium | 双指针 | ✔️ | Solution(Python) |
| 剑指 Offer II 008. 和大于等于 target 的最短子数组 | Medium | 二分查找, 前缀和; 滑动窗口 | ✔️ | Solution(Java) |
| 剑指 Offer II 009. 乘积小于 K 的子数组 | Medium | 滑动窗口 | ✔️ | Solution(Go) |
| 剑指 Offer II 010. 和为 k 的子数组 | Medium | 前缀和+HashTable | ✔️ | Solution(Java), Solution(Go) |
| 剑指 Offer II 011. 0 和 1 个数相同的子数组 | Medium | 前缀和+HashTable | ✔️ | Solution(Java) |
| 剑指 Offer II 012. 左右两边子数组的和相等 | Easy | 前缀和 | ✔️ | Solution(Java) |
| 剑指 Offer II 013. 二维子矩阵的和 | Medium | 二维数组前缀和 | ✔️ | Solution(Java) |
| 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 | Medium | 数据结构, Hash表, 链表 | ✔️ | Solution(Java) |
Hard难度，该题为典型的序列DP类型的题
假设 dp[i][j] 为考虑了 [1, i] 前 i 个数字，逆序对为 j 的方案数
Medium 难度，使用滑动窗口可以解决
字符串的字母从左往右一个一个包括进滑动窗口，并将每个字符和其索引用Map存放起来。使用 left 字段记录窗口最左端。
当遇到了之前遇到过的字符，即遇到重复字符，则将此时的长度与前一次滑动窗口长度比较取大的值（ans = max(ans, i - left + 1)），并且将left索引设置为当前这次重复的字符的索引 + 1，并将该字符的索引替换成重复字符的索引（较大索引）。
知道循环结束，返回 ans 为最大不重复子串长度。
Medium 难度，稍微有一些变化的动态规划
这道题需要我们变换一下动态规划的思路，从后往前做动态规划。
Hard 难度，稍微比较难想出状态转移方程。如果找到状态转移方程，则很容易解决。
因为这道题限制我们最多交易两次，所以我们创建四个变量（buy1, sell1, buy2, sell2）分别代表（第一回购买股票时的最大收益，第一回卖出股票时的最大收益，第二回购买股票时的最大收益，第二回卖出股票时的最大收益）。这时候就要找出这四个变量之间的关系以及4各变量间的状态是如何转移的（这部分应该算是比较难的部分了）。
从字面意思上可以看出，sell2 = max(sell2, buy2 + 当前售卖天的股票价格), buy2 = (buy2, 第一回售卖股票的最大收益 - 当前售卖天的股票价格), sell1 = max(sell1, buy1 + 当前售卖天的股票价格), buy1 = max(buy1, 0-当前售卖天的股票价格)
也就是说我们需要找出第一次买卖股票的最大收益和第二次买卖股票的最大收益。
假设第一天购入股票，我们可以初始化四个变量的初始状态：buy1 = -prices[0] (因为第一次购入，收益会是负数), sell1 = 0(还没有卖出过股票，所以卖出时收益初始化为0), buy2 = -prices[0] (和buy1解释一样，因为有可能只有一次交易), sell2 = 0。
根据以上的分析，我们就能写出对应的代码了：
public int maxProfit(int[] prices) {
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}这道题是国外站的 2021/11/22 每日一题，中等难度，主要考察对二叉搜索树的熟悉程度
从题解可以看出来这是一道二叉搜索树的题，针对树这类题，我们首先能想到的解法就是递归。
当我们删除一个节点时，该怎么重构才能让其保持为二叉搜索树呢？这里可以列举出三种情况：
- 需要删除的节点没有左子树但存在右子树：
我们可以简单的将该节点替换为右节点。
-
需要删除的节点没有右子树但存在左子树： 简单的将该节点替换为左节点。
-
需要删除的节点既存在左子树也存在右子树：
如果左右子节点都存在的情况，咱们看一下下面这张图，大家应该都能找到规律：
如果要删除上图中值为15的节点，则需要将它的右节点中的左子树中的最小值替换上来，这样我们就能保持一个完整的二叉搜索树。找到规律后，我们就可以写出来代码了：
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return root;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
return root;
}
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode min = root.right;
while (min.left != null) {
min = min.left;
}
root.val = min.val;
root.right = deleteNode(root.right, min.val);
return root;
}Medium - 主要用到了Prefix Sum思路，关键是如何找出前缀和数组中各项的关系