没想到“每日 1 题”又延长了一个月。每日 1 题：6 月（部分）。
| 一 | 二 | 三 | 四 | 五 | 六 | 日 |
|---|---|---|---|---|---|---|
| 1 ✅ | 2 ✅ | 3 ✅ | 4 ✅ | 5 ✅ | 6 ✅ | 7 ✅ |
| 8 ✅ | 9 ✅ | 10 ✅ | 11 ✅ | 12 ✅ | 13 ✅ | 14 ✅ |
| 15 ✅ | 16 ✅ | 17 ✅ | 18 ✅ | 19 ✅ | 20 ✅ | 21 ✅ |
| 22 ✅ | 23 ✅ | 24 ✅ | 25 ✅ | 26 ✅ | 27 ✅ | 28 ✅ |
| 29 ✅ | 30 ✅ | 1 | 2 | 3 | 4 | 5 |
打卡完毕 🎉。不知不觉间“每日 1 题”已经持续四个月了，其中的 122 题覆盖了大部分题型，从中学到了很多，但因为“战线”拉得太长，很多解题思想都遗忘了，需要时不时进行复习。
四月底的时候确定了实习地点，之后做“每日 1 题”的动力就有点不足，但出于强迫症不想“断签”，也为以后可以更方便地复习，因此做了一个简单的记录。“每日 1 题” 7 月仍在继续，但接下来就要期末考和实习了，不准备再继续了。
!> 面试题64. 求1+2+…+n
剑指 Offer 中的题，之前做过。题目要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。
这是很有意思的一道题目。若无上述限制，要完成这道题可以有三种做法：等差数列求和，迭代和递归。然而题目规定不能使用乘除和循环语句，因此剩下递归可用，但题目又规定不能使用条件判断语句，那么如何判停呢？
利用逻辑运算符的短路效应，
- “与
&&”。if(A && B)，若 A 为 false ，则 B 的判断不会执行，直接判定 A && B 为 false - “或
||”。if(A || B)，若 A 为 true ，则 B 的判断不会执行，直接判定 A || B 为 true
我们需要在 n == 1 时终止递归，那判停语句为：boolean b = (n > 1) && ((sum = n + sumNums(n - 1)) > 0)，为构成语句，需要添加一个 boolean b；由于 && 右边本身为 int 所以需要一个加一个判断条件变为 boolean。
public int sumNums(int n) {
int sum = n;
boolean b = (n > 1) && ((sum = n + sumNums(n - 1)) > 0);
return sum;
}评论区看到另一种递归做法：
int[] test = new int[]{0};
public int sumNums(int n) {
try {
return test[n];
} catch(Exception e) {
return n + sumNums(n - 1);
}
}官方题解中还有一种“快速乘”的解法。
!> 837. 新21点
想不到思路 0.0。题解给出动规方法，以下摘自题解
爱丽丝获胜的概率只和下一轮开始前的得分有关，因此令
根据规则，当分数达到或超过
- 若分数不超过
$N$ 则获胜。有$dp[x] = 1 \quad K \leq x \leq \min (N, K+W-1)$ 。若$K - 1$ 时抽到的数为$W$ ，且$K - 1 + W < N$ ，因此有$min (N, K+W-1)$ 。 - 若分数超过
$N$ 则失败。有$dp[x] = 0 \quad x>\min (N, K+W-1)$ 。
当
上述解法在
其中
注意到只有当
可在
!> 238. 除自身以外数组的乘积
题目要求不能使用除法，且在
$O(n)$ 时间复杂度内完成此题。
每个位置的结果，为
进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
由于输出数组不被视为额外空间，我们可以暂时用它来存储左边的数的乘积，对于右边数的乘积 nums[] 时，更新
public static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] product = new int[n];
product[0] = 1;
for (int i = 1; i < n; i++) {
product[i] = product[i - 1] * nums[i - 1];
}
int R = 1;
for (int i = n - 1; i >= 0; i--) {
product[i] = product[i] * R;
R *= nums[i];
}
return product;
}!> 面试题29. 顺时针打印矩阵
定义一个“方向”数组 int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} 来控制遍历方向，当下一个位置超出边界或者已访问（设一个 boolean[][] hasVisited 数组）时，就改变方向。
定义一个 i 来记录已遍历的元素数量，并根据总的元素数量来判断是否结束遍历。
参考自题解
可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，剩下的元素都是第 3 层。
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]按下图遍历每一层：
遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止，终止条件为 left > right || top > bottom。
!> 128. 最长连续序列（困难）
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为
$O(n)$ 。
用哈希表存储每个端点值对应连续区间的长度，摘自力扣评论区。
- 若数
num已在哈希表中，则跳过 - 若不在哈希表中，
- 取出其左右相邻数已有的连续区间长度
leftLen和rightLen - 计算当前数的区间长度为：
curLen = leftLen + rightLen + 1 - 根据
curLen更新最大长度maxLen的值 - 更新区间两端点的长度值，即更新
num - leftLen和num + rightLen的在哈希表中的值
- 取出其左右相邻数已有的连续区间长度
!> 126. 单词接龙 II（困难）
相似题目“127. 单词接龙”，都可以用 BFS 解决
从 beginWord 开始，寻找 wordList 中所有符合条件的下一个单词并加入 BFS 队列。值得注意的是，BFS 队列里存储的元素应该是一条“路径”（List<String>），它存储从 beginWord 到该层该元素的路径。一旦某层有元素到达了 endWord，说明该层为最短路径，我们只需在该层所有输出能到达 endWord 的路径，并结束 BFS。
在 BFS 的同时，我们要维护一个 Visited 集合，记录已被加入路径的单词。但是，在把单词添加到某路径的时候，不能直接将该单词在 Visited 中标记为已访问，因为该层的其他路径也有可能会加入这个单词。所以，应该存储一个临时的 subVisited，在该层结束之后，再汇合到总的已访问单词集合中。
看代码更容易懂。
!> 990. 等式方程的可满足性
考查并查集知识
由于等式方程具有传递性，比如 a == b 和 b == c 成立，则 a == c，可以想到用并查集来维护这种关系。
我们可以遍历 equations 数组中的等式，我们把等式两边的变量合并。接着再遍历数组中的不等式，不等式中的两个变量不能属于同一个集合，若查找后是同一个集合，则出现矛盾。
并查集的合并操作：
private static void union(int x, int y, int[] father) {
int faX = findFather(x, father);
int faY = findFather(y, father);
if (faX != faY) {
father[faX] = faY;
}
}并查集的查找操作：
private static int findFather(int x, int[] father) {
while (x != father[x]) {
x = father[x];
}
return x;
}路径压缩后的查找：
private static int findFather(int x, int[] father) {
// 由于 x 在下面的 while 中会变成根结点，因此先把原先的 x 保存一下
int oriX = x;
while (x != father[x]) {
x = father[x];
}
// 下面把路径上的所有结点的 father 都改成根结点
while (oriX != father[oriX]) {
int temp = oriX;
oriX = father[oriX];
father[temp] = x;
}
return x;
}!> 面试题46. 把数字翻译成字符串
DFS 或动态规划都可以。本题和“91. 解码方法”相似，略有不同的是， 91 题的
$1$ 代表$A$ ，而本题的$0$ 代表$a$
DFS 的思路很直观：每次有两种选择，选择一位数字翻译或两位数字翻译，具体情况如代码所示。
if (headNum == '0' || headNum > '2') {
DFS(str.substring(1, len));
} else {
DFS(str.substring(1, len));
if (str.length() > 1) {
if (!(headNum == '2' && str.charAt(1) > '5')) {
DFS(str.substring(2, len));
}
}
}无备忘录的 DFS 会存在重复的计算，时间复杂度并不理想。如下图：
图片来自力扣
若当前数字和前一个数字可以合并翻译（说明既可以单独翻译，又可以合并翻译），那么：$dp[i] = dp[i - 1] + dp[i - 2]$；否则，$dp[i] = dp[i - 1]$。
int[] dp = new int[len + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= len; i++) {
char preChar = str.charAt(i - 2);
char curChar = str.charAt(i - 1);
if (preChar == '1' || (preChar == '2' && curChar >= '0' && curChar <= '5')) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
}!> 739. 每日温度
倒序遍历数组，并维护一个栈。若栈顶温度小于当前温度，则弹出；否则，记录栈顶温度和当前温度相差的天数，并存入结果数组。最后将当前温度入栈。
public static int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] res = new int[len];
LinkedList<Integer> stack = new LinkedList<>();
for (int i = len - 1; i >= 0; i--) {
int curTemperature = T[i];
int daysToWait = 0;
while (!stack.isEmpty()) {
if (T[stack.getLast()] > curTemperature) {
daysToWait = stack.getLast() - i;
break;
}
stack.pollLast();
}
res[i] = daysToWait;
stack.addLast(i);
}
return res;
}!> 15. 三数之和
之前做过，👉 传送门
!> 297. 二叉树的序列化与反序列化（困难）
序列化方式有多种，可以是层序、先序、中序或后序。只要反序列化和序列化对应上就可以。
!> 1014. 最佳观光组合
由题意可知，求一对景点的最高得分就是求 A[i] + A[j] + i - j 的最大值，我们把它拆分为 A[i] + i 和 A[j] - j 两部分。首先计算出 A[i] + i，然后倒序遍历计算 A[j] - j 并维护当前最大的 A[j] - j 记为 curMaxJ。由于 A[i] + i 的值是固定的，在倒序时，我们只需计算当前的 curMaxJ 与 A[i] + i 之和，并更新这个和的最大值即可。
public static int maxScoreSightseeingPair(int[] A) {
int len = A.length;
int[] aPlusI = new int[len];
int maxScore = 0;
for (int i = 0; i < len; i++) {
aPlusI[i] = A[i] + i;
}
int curMaxJ = A[len - 1] - (len - 1);
for (int j = len - 1; j > 0; j--) {
curMaxJ = Math.max(curMaxJ, A[j] - j);
maxScore = Math.max(maxScore, aPlusI[j - 1] + curMaxJ);
}
return maxScore;
}当然可以取消计算 A[i] + i 的那个循环，直接放到第二个循环计算，不过分开循环计算思路更清晰。
!> 1028. 从先序遍历还原二叉树（困难）
占位
!> 10. 正则表达式匹配（困难）
可用 DFS 和动态规划思想。DFS 在这里，动态规划为官方题解。
!> 124. 二叉树中的最大路径和（困难）
这题和“543. 二叉树的直径”思路相同。
我们可以知道，最大路径和一定是 某一结点的值 + 此结点左子树的最长路径 + 此结点右子树的最长路径。我们计算所有结点的 结点的值 + 此结点左子树的最长路径 + 此结点右子树的最长路径 的值，并记录最大值，即为最大路径和。
对于 结点左\右子树的最长路径，我们可以通过 DFS 返回。代码思路更清晰。
private static int maxPath;
public static int maxPathSum(TreeNode root) {
maxPath = Integer.MIN_VALUE;
DFS(root);
return maxPath;
}
private static int DFS(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = Math.max(0, DFS(root.left));
int rightHeight = Math.max(0, DFS(root.right));
maxPath = Math.max(maxPath, leftHeight + rightHeight + root.val);
return root.val + Math.max(leftHeight, rightHeight);
}!> 面试题 16.18. 模式匹配
要使 pattern 匹配 value，需要 pattern 中的 a 和 b 分别代表不同的字符串，且 countA * lenA + countB * lenB = value.length()。countA，countB 和 value.length() 已知，那么我们可以通过解一元二次方程来枚举 a 和 b 的长度，再进行匹配。
但本题允许 a 或 b 为空串，因此边界条件需要仔细考虑，看题解。
!> 16. 最接近的三数之和
排序 + 双指针。和“15. 三数之和”思路相同 👉 在这里
!> 139. 单词拆分
因为字典中的单词可以被重复使用，所以这是一个完全背包问题，在动态规划分类中做过 👉 传送门
!> 41. 缺失的第一个正数（困难）
[!NOTE|label:要求] 你的算法的时间复杂度应为
$O(n)$ ，并且只能使用常数级别的额外空间
由于有空间复杂度的要求，我们不能用哈希表 + 枚举正整数（从
我们对数组进行遍历，对于遍历到的数
!> 209. 长度最小的子数组
因为给定的是正整数的数组，所以双指针完事，sum >= s 则左指针右移。
public static int minSubArrayLen(int s, int[] nums) {
if (nums.length == 0) {
return 0;
}
int l = 0, r = 0;
int sum = 0, len = Integer.MAX_VALUE;
while (r < nums.length) {
sum += nums[r];
while (sum >= s) {
len = Math.min(len, r - l + 1);
sum -= nums[l];
l++;
}
r++;
}
return len == Integer.MAX_VALUE ? 0 : len;
}此外，还有
- 暴力法：双层循环
- 前缀和 + 二分查找：sums 数组保存前缀和，通过二分查找得到大于或等于 i 的最小下标 bound，使得
sums[bound]−sums[i−1] >= s
!> 215. 数组中的第K个最大元素
三种方法：排序、快速选择、堆选择。在排序章节做过 👉 这里。