LeetCode刷题记录

关键字检索

查缺补漏：做题时比较生疏的知识点，后面复习的时候最好也check一下熟练程度。
知识点：题目所涉及到的大概知识点。
分类：根据题库现有的tag，可以大概分为 DP，贪心，数学技巧，滑动窗口，hash，二分算法，单调栈（队列），DFS/BFS，位运算，字符串，数组，二叉树，并查集，双指针
第一遍顺序过剑指Offer，第二遍根据类型和短板刷。

短板总结

短板：二叉树，矩阵，DFS，BFS

2022-04-15 17:28:42，BFS，DFS，二叉树稍微熟练了一些；目前的短板

DP，堆，矩阵

常见 BUG

1. itoa

gcc error : undefined reference to `itoa'

原因：itoa is a non-standard function which is supported by some compilers. Going by the error, it’s not supported by your compiler. Your best bet is to use snprintf() instead.

3.11

查缺补漏

二叉树建树
二叉树后序遍历

3.11

JZ.03

3钟方法，Hash 遍历，时间空间均为O(n)，用的这一种秒了；

第二种排序后，check 相邻是否重复，时间 O(nlogn)，空间O(1)

第三种原地Hash，鸽巢原理。源于一个条件 element value < nums.size()，元素值归位时如果该索引处已经存在该元素，则为重复。t.O(n), s.O(1)

知识点

vector 可以用下标索引
标签：hash，排序，数组

JZ.04 二维数组中的查找 ❌

感觉是 DP or 一些奇淫技巧；这个题感觉算法考试里面有考过:)

并非 DP，没有秒这题；主要是思路上的解法而非常规算法

从右上角开始比较，比它大就往下数一行，比它小就往左数一列
二分查找也是解法之一

知识点

二维 vector 能否用下标索引？
- 可以
标签：数组，二分查找，分治，矩阵

JZ.05 替换空格

简单的字符串替换，被 string 和 char，"" 和 ’’ 的一些知识卡了一会儿。

知识点

字符串裁剪 str.substr(pos, len)，
⚠️ 字符串比较；string 可以直接用 ==，但是注意 s[0] 是 char 型；所以 s[0] == " " 会报错，应该是 s[0] == ' '；或者 strcmp(s[0], ' ');
注意 "" 和 ''
❗ 为什么不能用 strcmp？
- 用 strcmp(string , string) 会就报错；使用 strcmp(char [], char[]) 就可以了；有什么区别？
- string 是一个 managed type，不用担心有多长；char[] 分配的长度固定

JZ.06 反转链表

从尾到头打印链表，单链表

自己的思路：用一个数组存，反向打印这个数组。都是 $O(n)$

也可以使用递归

⚠️ 注意边界条件，基本每次 case 都会有

知识点

单向链表；指针；vector
标签：栈，链表，递归，双指针

3.13

JZ.07 重建二叉树 ❌

二叉树和链表的数据结构要记住。

如何由前序和中序遍历确定一颗二叉树？确定根节点和左右子树，然后继续递归，确定左右子树的根节点和左右子树。可以用分治和递归求解

In_Hash 映射作用：pre 第一个节点为 root，根据第一个节点 val，在 In 中快速定位到 index。

❌ 看了题解第一遍没写对，注意传入参数为 pre 的起始以及 In 的起始，而非 left_start, right_start。

pre_start 作用：找到 root。In_start 作用：确定 root index，进一步确定 left_child_size 和 right_child_size

知识点

前序遍历列表：第一个元素永远是【根节点 (root)】
中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】
做题时忽略了一个关键的知识点，确定了pre root，后面的节点都是其左子树，然后才是右子树，也就是说知道了 left_child_size，就能够确定 pre_end
标签：数组，hash，分治，二叉树

JZ.09 用两个栈实现队列

自己的思路：stack_1 用来插入，需要删除时把 stack_1 全部倒入 stack_2，此时先进来的 element 在栈顶，出栈即可，再把 stack_2 中全部倒回 stack_1。操作上开销比较大。

更好的思路：其实不用再把 stack_2 中全部倒回 stack_1

知识点

栈和队列；自带的 stack 和 queue 库使用的不多；创建栈和队列的关键字？stack<int> stk; queue<int> q;
两个栈实现队列
标签：栈，队列

JZ.10 斐波那契数列 DP

自己的思路：感觉是经典的递归教学，但是肯定有比递归更好的解法。用递归会超时，可以加一个 hash 表来优化。加了 hash 优化后 AC，题解中称之为记忆递归

更好的思路：这题可以用 DP，没有想到。

现成的状态转移方程 $f(n+1) = f(n) + f(n-1)$；

转移方程：$dp[i+1] = dp[i] + dp[i-1]$

初始状态：$dp[0] = 0; dp[1] = 1$

返回值：$dp[n]$

知识点

查缺补漏：对迭代的概念不太熟悉；DP 的概念和思路
标签：DP

JZ.11 青蛙跳台阶

自己的思路：hash 递归；DP

和上一题很类似，写的是优化空间后的 DP，

✔️ 要求自己写一个常规的 DP 加深理解

知识点

JZ.11 旋转数组的最小数字 ❌

这个题目肯定有复杂度要求的，小于线性复杂度，也就是要求 $O(logn)$；看题解做出来的

确实值得一道 hard。也是二分查找的思想，只是舍弃的区间有一定的变化。

知识点

标签：二分查找，数组
查缺补漏：二分查找熟练度不够

3.14

JZ.12 矩阵中的路径 ❌

自己的思路：递归查找可以解，但是复杂度为 $O(mn)$ ；确实是用 DFS递归查找，而题解的复杂度为 $O(3^kmn)$

题解 DFS，DFS 已经非常生疏了

看了题解后手写了一个性能比较差的 DFS，通过了 case。和题解的写法差不多，性能也是一个级别。

知识点

典型的矩阵搜索问题

JZ.13 机器人运动范围

这个也是算法设计课程中出现的考试题目。

自己的思路：看起来暴力遍历可解，不过应该有复杂度要求；第一次做的时候没考虑到棋盘被截断的情况，如果有截断，那么一些满足条件的区域也是去不了的。

写错了一句 tag[i][j] == -1;，报错居然是 stackoverflow，要注意尽量一次写出 bug-free code。

题解：差不多，也上题一样，也是 DFS/BFS，回溯算法，矩阵

知识点

和上一题类似，也是矩阵，DFS还是可以用。
标签：DP，BFS，DFS；DP 体现在哪？了解 DP 的解法

JZ.14-I 剪绳子 ❌

自己的思路：m 从 2 到 n/2 进行遍历，每次均分长度，求出最大的乘积，可以AC，$O(n^2)$

更好的思路：

求长度为 n 的绳子剪掉后的乘积，从 <n 的绳子转移而来
dp数组 记录 0到n 的绳子的最大乘积，初始化 dp[2] = 1
剪掉第一段，长度为 j，j > 1
剪了第一段，剩下长度为 (i - j) 可以剪或者不剪。不剪的话 length = j * (i - j)；剪了的话 length = j * dp[i - j]；max(j * (i - j), j * dp[i - j])
遍历 j，$j \in [2, i)$，取最大值。

难道其实你已经用了 DP 思想？3.16 早上来给出答案。2022-03-15 23:27:16。

2022-03-16 10:38:06，尝试写一下 DP 解法 ✔️。DP 和自己的思路性能差不多。

贪心

均值不等式思想；n > 4 时，尽可能把绳子分为长度为 3 的小段，进行乘加。

3.16

JZ.14-II 剪绳子

在 I 的基础上加了一个答案取模，取模对于加法没有影响，~~但是会影响乘法的计算结果。~~并没有，那么这题在考察什么？

这个题目就是考察贪心的解法，如果继续用 DP，应该会超时

JZ.15 二进制中1的个数

考察位运算。

自己的思路：比较基础的 $/2%2$ 进行二进制化，时间复杂度 $O(logn)$，可以AC。bitset

更好的思路：$n&(n-1)$，$n-1:$ 二进制数字 $n$ 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1；$n&(n - 1):$ 二进制数字 $n$ 最右边的 1 变成 0 ，其余不变。时间复杂度 $O(M)$，M 为 1 的数量

知识点

标签：位运算

JZ.16 数值的整数次方 ❌

自己的思路：计算 $pow(x, n)$，naive 直接乘 $n$ 次，时间复杂度 $O(n)$，会超时，因此需要的不是 $O(n)$ 的解法。好像和复杂度没有关系，注意 $n$ 的范围，涉及越界的问题。

~~我认为这个应该就是考察 INT 型表示范围的细节，尤其是 $n = 0 - n$ 这种写法会越界~~。看来并非如此

处理了越界仍然会超时，用 $x$ 的范围去换 $n$ 的范围。这样并没有降低时间复杂度的数量级，304 case 全过但是仍然超时。因此猜测 $O(n)$ 的解法 A 不了。加了一个判断 if(x < 0.000005) return x * init_x; 后 AC 了，因为输出只保留到小数点后 5 位，有点取巧，虽然 AC 但是可能没有满足这道题的考察意图。⚠️ 这个取巧做法不能算真正的 AC。

更好的解法：确实有 $O(logn)$ 的解法，快速幂。快速幂也就是在循环中递归地使用你只用了一次的降幂操作，每次可以降幂的时候，$x *= x, n »= 1$，这样将复杂度降至 $O(logn)$

知识点

$(-3) % 2$，余数是 1 还是 -1？答案：余数是 -1
标签：递归，数学

JZ.17 打印从1到最大的n位数

自己的思路：遍历，时间复杂度 $O(10^n)$，直接 A，意义在哪？评论区有人说原题目是要考虑大数越界问题的。因此，这道题的本意应该是考察字符串和整型数字的转换。

先放一下

若不考虑大数问题，则十分简单一个从1到最大数的循环即可。若考虑大数问题，则首先需要将数字转成字符串避免溢出，然后全排列字符串的第0位到第n-1位。存储结果时需去掉字符串前几位的0(0099没有意义，应为99)再放入结果。

知识点

标签：数组（越界，大数），字符串

JZ.18 删除链表的节点

自己的思路：最简单的单链表删除，时间复杂度 $O(n)$，AC。

知识点

标签：链表

JZ.20 表示数值的字符串

这个题是有实用性的，也许在某些爬虫提取数据的时候会用到。

自己的思路：就是用条件判断筛选出不合规的情况 return false，第一次以为空格直接删除就行，提交后发现空格不能出现在有效符号的中间。

提交 23 次 AC，基本就是看着 case 补条件，完全没有周全考虑，没有使用正则表达式思想。

知识点

标签：字符串，有限状态机

JZ.21 调整数组顺序使奇数位于偶数前面

自己的思路：两次遍历，$O(n)$，AC，有没有复杂度更低的解法？

题解的思路：也是 $O(n)$ 复杂度，但只用遍历一次，双指针，类似快排的思路。分别从左右开始遍历，然后交换。稍快一点。

知识点

标签：数组，双指针，排序

JZ.22 链表中倒数第k个节点

自己的思路：打印倒数的节点，所以遍历两次，第一次确定链表长度 L，L - k 次 next 就可以找到目标结果，然后返回，AC，时间复杂度 $O(n)$

更好的解法：双指针，无需统计链表的长度。前指针先走 $k$ 步，然后共同移动，前指针到终点时返回后指针即可，时间复杂度 $O(n)$

知识点

标签：链表，双指针

JZ.24 反转链表

自己的思路：一次遍历，forward 指针在前，head 自己在后，一遍遍历一边调整，AC，时间复杂度 O(n)。

❌ 注意边界条件，注意条件判断时写了 if(head->next == NULL || head == NULL)，报错。因为当 head==NULL，是找不到 head->next，自己写代码不要忽略边界和细节。

题解：除双指针，还有递归的解法，时间空间都是 $O(n)$

知识点

标签：递归，链表
关于递归，心中要有明确的终止条件的概念。

JZ.25 合并两个递增排序的链表

自己的思路：非常基础的算法题，一次遍历，其中一个链表完成遍历后直接接过去。最初出现错误的原因：遍历的时候 l2 = l2->next，忘记保存头结点。

一开始的合并写法没有 AC，逻辑有点混乱了，后来直接换了一种写法，新建了一个链表，比较耗费空间，时间复杂度 $O(m+n)$，空间复杂度 $O(m+n)$。

知识点

标签：递归，链表
引入 伪头结点 合并链表是本题的最优解

3.17

JZ.26 树的子结构 ❌

又到了短板，二叉树相关的题目。

自己的思路：是否会有一段完全相同的中序遍历？中序遍历能否唯一确定？手写中序遍历 DFS，大概的还记得，有些地方比如 visied，还有判断条件（only care left）疏忽了，但是很快能想起来。Value 还存在负数，那么只能前序也 check 一次了。

check 了一次前序一次中序，但是还是 AC 不了，说明一开始的思路可能有点问题。写出了前序和中序，但是没法 AC，思路是错的。

更好的解法：遍历 A 树中的每个节点 $n_A$，判断以 $n_A$ 为根节点的字数是否包含 B。状态一般，没有自己手写题解，之后再熟悉一遍。

知识点

标签：树，DFS

JZ.27 二叉树的镜像

自己的思路：简单递归。AC，时间复杂度 $O(n)$，空间复杂度 $O(n)$，由递归栈的深度决定.

JZ.28 对称的二叉树 ⚠️

自己的思路：一开始直接指针指向 root，翻转二叉树，比较，忽略了只是指针指向了 root，没有保留翻转前的树。后来分别使用递归建树、翻转、比较，AC，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

更好的思路：一次递归，无需求镜像。递归地比较左右子树是否相等即可

知识点

这个题用到和复习的知识点比较多，包括建树。翻转二叉树，比较
标签：二叉树，BFS，DFS

JZ.29 顺时针打印矩阵

自己的思路：没考虑算法，用循环每次 push 边界上的几组数，然后不断地更新边界条件，直到所有数都 push 进去。注意边界条件。AC，时间复杂度 $o(mn)$，空间复杂度 $O(mn)$。

题解：和 K 神题解的思想差不多。

知识点

数组，矩阵，模拟

JZ.30 包含 min 的栈

自己的思路：用 vector 实现，push 的时候对比一下记录 min 即可，关于 vector 的指定 index 删除有点忘记了。v.erase(pos)。噢，不过突然想起 stack 是先进后出，那么直接 v.pop_back() 删掉最后一个即可。不过为了更加造轮子，还是不用 STL 了吧，用数组好了。

还有一个细节，还需要额外保存一个次小值，当 min pop 时需要用次小值顶上。次小值还不够，应该用一个数组记录不同 stack size 时的 min，空间换时间。

❗ 细节：栈空时要重置 min。

题解：很多题解都是用辅助栈，不过这题个人主要是尝试用数组求解。

知识点

关于 vector 的指定 index 删除。v.erase(pos)。

JZ.31 栈的 push, pop 顺序

也是经典的算法考题，给一个 push 顺序和 pop 顺序，判断 pop 顺序是否有可能是该 push 顺序下的一个 pop 结果。

自己的思路：插 pop，给出所有可能性然后对比，这样复杂度有点太夸张了。加一点数学思路来优化，假设 push 序列是顺序的，如果 4 pop，那么 4 之后 <4 的元素出栈时一定不可能是升序，比如 1，2，3；推理到元素 i 出栈，之后 $<i$ 的元素出栈序列一定是降序排列。

不一定是顺序输入，所以可能需要用 hash 转换一下。hash 转换得费点脑子，找找经典的理解方法。注意细节，mmax 更换时 slide_min 便作废了。AC，时间复杂度 $O(n)$，空间复杂度 $O(n)$，用了额外的 hash 空间排序。

题解：这个题其实蛮有意思，题解完全是另一种做法，自己是利用一些数学/算法上的特征解的。根据 push 序列模拟入栈操作，当栈顶元素 top() == popped[i] 时出栈元素，i++，push 操作完成观察栈是否空即可。

知识点

标签：栈，数组，模拟
自己使用到了 hash 思想；栈的基本知识；栈空时调用 s.top() 会报错

JZ.32-II 从上到下打印二叉树

自己的思路：线序遍历，根据 height 来决定 push 到哪一行。其中遇到了 vector 初始化的问题，不初始化没办法直接 v[height].push_back(root->val)，先根据上限 v.resize(1000)，遍历结束后根据深度 v.resize(height+1); 即可。时间复杂度 $O(n)$，空间复杂度 $O(n)$。

知识点

二维 vector 初始化
- v.resize(4); v[0].resize(4);
- vector<vecotr<int>> v(m, vector<int>(n, 0)); m 行 n 列全部初始化为0

JZ.32-III 从上到下打印二叉树

和上题区别在于，第一层从左到右打印，第二层从右到左打印，没法先序遍历直接解。

自己的思路：vector 是否自带 reverse？正好复习一下，reverse(v.begin(), v.end());，AC。

不过有评论说这是经典面试0分方法 😓，那认真学习下题解思路。

知识点

标签：树，BFS
reverse()

3.18

2022-03-17 22:45:21，先把两道树的题方法搞了。贪心和 DP 是薄弱点，后期要加强。

3.19

606. Construct String from Binary Tree 每日一题

这道题中文描述简直是 bullshit，还没给范围，之后直接看英文好了。这道题应该是简单吗？虽然确实不太难但是东西还蛮多，涉及先序遍历，数字转字符串等等。

自己的思路：先序遍历，数字转字符串，可以省略空子树的括号，省略右子树为空仅有左子树时的括号。时间复杂度 $O(n)$

彩蛋：2020.04.02 AC过，当时直接用的 to_string()，记一下这个函数。不知道当时是不是看的题解，那个时候写的解法更好一点~

知识点

树，DFS，字符串

3.20

JZ.33 二叉搜索树的后序遍历 ❌

一开始看题目描述蒙了，没有理解其意思。原来是忽略了二叉搜索树这个条件，太久没有接触到所以生疏了，也就是左孩子 value 小于当前节点，右孩子 value 大于当前节点。

自己的思路：后序遍历建树，后序遍历不能唯一确定，不过二叉搜索树好像是完全二叉树？这点得确认一下，先按照这个假设。然后判断建好的树是否满足搜索树的概念。

注意：循环中，it 不能回到 begin，因为 begin 位置上可能还有之前跳过的数字，留在当前位置即可。出现了意料之外的 case，所以搜索树不一定是完全二叉树？确实如此。

题解思路：遍历顺序左右根。这个思路之前有想过。后续遍历区间$[i,j]$，遍历划分左右子树区间，找到第一个大于 root 的元素 index $m$，左子树区间 $[i, m-1]$，右子树区间 $[m,j-1]$，递归判断子树的合法性即可。

知识点

vector：可以使用迭代器作为 v.erase(pos) 中的 pos 进行删除；删除后 v.size() 会发生变化.
二叉搜索树的概念，正是因为记错了所以思路出现了问题。
后续遍历的性质，左右根，左右子树的区间
标签：栈，树，二叉搜索树，递归，单调栈

3.26

JZ. 19 正则表达式匹配 ❌

自己的思路：考虑所有情况，硬配。写了一个多小时还是考虑不全所有情况，这是一种冗余分类的思路，还没有概括完所有情况。遂看题解，发现原来这也能DP。

题解的思路：拆分子问题

B 的最后一个字符为正常字符串，比较 $A_{n-1}$ 和 $B_{m-1}$，如果相等则继续比较 $A_{0..n-2}$ 和 $B_{0..m-2}$，不相等则返回 false
如果 B 的最后一个字符串为 .，则比较 $A_{0..n-2}$ 和 $B_{0..m-2}$
如果 B 的最后一个字符串为 *，则 $B_{m-2} = c$ 可以重复0次或多次
- case 1：$A_{n-1}$ 是0个c，舍弃 B 中的 c*，比较 $A_{0..n-1}$ 和 $B_{0..m-3}$
- case 2：$A_{n-1}$ 是多个c中的最后一个，比较 $A_{0..n-2}$ 和 $B_{0..m-1}$

转移方程

$f[i][j]$ 代表 A 的前 $i$ 个和 B 的前 $j$ 个能否匹配

对于前两种情况可以进行合并，$f[i][j] = f[i-1][j-1]$
- 第三种情况，$f[i][j] = f[i][j-2]$，case 2: $f[i][j] = f[i-1][j]$

初始条件

空串和空正则可以匹配，$f[0][0] = true$
空串和非空正则，需要判断
非空串和空正则，不匹配，$f[1][0]…f[n-1][0]=false$
非空串和非空正则，需要判断

看题解后自己写：没有正确理解，不是倒着来的，本质上还是正常动态规划的求解过程。用的是

for(int i = 1; i < m; i++) {
    for(int j = 1; j < n; j++) {
    }
}

不需要双指针同步推进

2022-03-27 10:22:03，有点绕，之后再来一遍，看懂了再自己写

JZ. 35 复杂链表的复制

自己的思路：先通过~~递归遍历原链表~~，修改了一下，实际无需递归，直接遍历即可。此时 random 指针还没有赋值。第二次遍历复制链表，用 traver_cpoy 指针一一为每个节点找 random 指针应该指向的节点。怎么找？双指针一同遍历 init 链表和 copy 链表，当 init 链表到达当前节点的 random 后停止，copy 指针也跟着停止，此时 copy 指针的位置就是 traver_copy 指针节点的 random 节点。AC，时间复杂度 $O(n^2)$。

更好的思路：hash map 映射，这个能够加深对于 hash 的应用上的理解。第一次遍历构造新节点时，以 hash 的形式存下 init 和 copy 对应节点的指针 map<*Node, *Node> hash_m，第二次遍历构造 copy 链表的 random，init 指向 head->random，通过 head->random 以及 hash，可以查找到 copy random hash_m[head->random]，copy->random = hash_m[head->random]。时间复杂度 $O(n)$，空间复杂度 $O(n)$。

知识点

注意复制链表需要新建节点，Node* tmp = new Node(val);，不然指针连接到之前的链表上，就违背了复制的意图。
原来这个就是深拷贝的一个例子
标签：hash，链表

JZ. 36 二叉搜索树与双向链表

自己的思路：刚学的 hash 的思想似乎可以用上。中序遍历把节点的指针存入数组 vector<Node*> ans，此时 ans 中的指针是有序的。遍历 ans 数组，重新调整节点 left 和 right 指针的指向即可。AC。

和题解思路一致

知识点

栈，DFS，二叉树，双向链表
主要是利用了二叉搜索树中序遍历后有序的性质

JZ.37 序列化二叉树

序列化函数：也就是将二叉树以 string 的形式存起来。反序列化函数：将 string 构造为二叉树

自己的思路：想到的还是 hash 的形式，把节点的指针存下来。得到了中序和前序遍历的序列，然后就是根据中序和前序遍历建树

2022-03-31 22:13:41 的思路：有什么东西不重复呢？一开始想到了随机数，但是其实还有有风险，地址应该是不重复的。注意索引越界的问题

建树：注意传入参数为 pre 的起始以及 In 的起始，而非 left_start, right_start。忘了加参数 inorder_left 和 inorder_right

知识点

整型转字符串：itoa(int num, char* str, int radix)
字符串，char str = 'a'; str += 1，可以直接加整型，此时 str = 'b';
map 如何通过 value 查找 key

3.31

728. 自除数每日一题

每日打卡，简单题，没什么亮点。

4.3

每日一题

JZ.38 字符串的排序 ❌

自己的思路：双重循环，swap，set来去重。时间复杂度 $O(n^2)$。❌这种方法覆盖不了所有情况。20分钟没有思路

题解的思路：递归回溯填空位的思想。递归回去时，使用过的字符串标记也会回溯。

知识点

❗ 本以为把 visit 数组当做参数传进去，return 的时候自动回溯，没想到也需要手动回溯。
突然想起来，要用引用传参。也不全是，只是突然想起来引用传参这个知识点。

JZ.39 数组中出现次数超过一半的数字

自己的思路：这个题之前应该是遇到过。最直接的方法就是遍历然后填充 hash 表，之后简单地判断，时间复杂度 $O(n)$，空间复杂度 $O(n)$。印象中有时间复杂度更低的解法，分治的思想之类的。想起来是排序之后找中间那个元素，~~时间复杂度 $O(logn)$~~,oh，原来排序的时间复杂度是 $O(nlogn)$

JZ.40 最小的k个数 ❌

自己的思路：排序后遍历，这样做没有意义，直接看题解。

题解：基于快排的特点。快排时每次都能把 pivot 放在他最终的位置。当结束一次快排，pivot 正好在 $index_k$ 时，返回数组的前 $k$ 个数即可。

对快排特点的应用。

❌ 忘记了快排的写法，这个题卡了1个小时的原因，在于你完全不会手写快排。如同上次蔚来面试答不出快排一样。

知识点

看了题解之后还是折腾了1个小时；完全是因为快排写错了。

4.4

307 ❌

线段树、树状数组踩坑，明天来学习

自己的思路：用一个 hash，hash[i] 存的是数组前 i+1 个元素之和，查找时复杂度为 $O(1)$，update 时复杂度为 $O(n)$，这个级别的复杂度达不到要求，需要更好的方法。遂看题解。

题解思路：分块处理，把时间复杂度优化到 $O(\sqrt{n})$；线段树，其实就是把一个完整的区间划分，左右子树分别是根节点的子区间。树节点保存的值为区间内的元素和，线段树看下图会很清晰。首先根据区间建树，用堆来存储更好。递归回退的时候计算每个节点的 val（也就是区间和），这个思路值得学习。

2022-04-05 14:17:41，做得一团 bullshit，又浪费了一个小时，坑还是剩下，不要抄代码强行提交，先去写论文了。

知识点

vector 还可以不使用 push，直接 index 吗？

4.5

762

自己的思路：判断质数函数一个，对于整数num，从 2 遍历到 num/2，没有整除就是质数，时间复杂度 $O(n)$；统计 bit 为1数量的函数，移位并计数，时间复杂度 $O（logn）$。AC

5. 最长回文子串

经典DP

自己的思路：秒不了，想不出DP，直接题解。

题解：中心扩散法，这个比较好理解，主要是来学习DP。

动态规划就是为了减少重复计算的问题。动态规划听起来很高大上。其实说白了就是空间换时间，将计算结果暂存起来，避免重复计算。

每日 310. 最小高度树

自己的思路：就是找一个节点，遍历所有节点的深度最小。建表之后dfs，写出了dfs解法，超时，需要优化。还是超时，遂先放弃。

4.15

JZ.41 数据流中的中位数

自己的思路：这道题的瓶颈在于排序，无论是插入时排序，还是找中位数时排序，如果每次 call 都进行一次排序，一定会超时。也许需要一颗平衡二叉排序树，把插入时排序的开销降低到 $O(logn)$。

以为需要建堆，看题解之后AC。但是直接用的现成的优先队列，并且是看的题解，这道题几乎没有自己想的部分。

题解：大顶堆，小顶堆。小顶堆 A 保存较大的一半数据（size = m），大顶堆 B 保存较小的一般数据（size = n）。插入时优先插入到 A，即：

m = n，把新元素加到 A：把新元素 num 插入 B，再将 B 的堆顶插入 A。查找：返回 A 和 B 的堆顶之和 / 2

m != n，把新元素加到 B：把新元素 num 插入 A，再将 A 的堆顶插入 B。返回 A 的堆顶

为什么用优先队列实现大顶堆？什么事优先队列？优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

知识点

C++中的优先队列实现。不过要注意，直接用现成的轮子，建堆的过程其实还是不会的。

priority_queue<Type, Container, Functional>
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

堆（优先队列），数据流，排序，双指针

JZ.42 连续子数组的最大和

自己的思路：经典的DP来了，练习DP的机会来了。这个似乎就是那位同学说的商汤2面的编程题。dp[i] 存放以 index i 为右边界的数组的最大和。

2022-04-15 18:03:47，果然没有想出来，和我自己想的不太一样。写 dp 方程的时候没考虑到需要连续这一特性。要接受自己的愚蠢，看答案。

思路绕进去了，一直在想 dp[i] 小于0不一定不能加；实际上自己想的是 nums[i] 小于0不一定不能加。而 dp[i] 如果小于0，说明以 i 为右边界的数组的连续子数组最大和为负数，故可以直接舍弃。

知识点

数组，分治，DP

JZ.43 1～n 整数中 1 出现的次数

自己的思路：首先尝试暴力的方法，遍历，把int转为char，统计1的数量。itoa 还是用不了，找到了替代，sprintf。暴力法必然超时，打表应该是通过的方法之一，这样需要预处理。没有使用打表的方式，以10000为步长来计算。一次AC，nice（2022-04-15 20:44:01），虽然这道题可能算不上困难。

递归，数学规律，DP

JZ.44 数字序列中某一位的数字 ❌

自己的思路：实际上就是构造这个序列化字符串。这个字符串长度大于n时跳出即可。承接上一题，还是继续使用 sprintf。atoi 格式忘记了。

2022-04-16 19:50:05，先放一放，往后做

4.16

JZ.45 把数组排成最小的数 ❌

自己的思路：排序后遍历，因为数字都是100以内，先拼接小的即可，拼接22之前先拼接2，拼接33之前先拼接3。晕，看错条件了，说的是 nums 长度小于 100。

没有A，看题解了。这道题也是有一些数学的规律，自定义字符串的排序规则。字符串排序规则，若 $x + y > y + x$，说明 y 应该放在左边。

除了 sprinft，还可以用 to_string(INT);

4.17

JZ.46 数字翻译成字符串

自己的思路：感觉是一个标准的 DP 问题。判断两数是否能组合时，要注意一些边界条件上的细节。时间复杂度 $O(n)$。实际上就是青蛙跳台阶的思路。

2022-04-17 22:10:46，成功AC。这个是刷 LeetCode DP 问题的一个里程碑。标志着你也许能够独立做出一些 DP 问题了。

初始状态：以 0 结尾的字符串，有1种翻译

状态：以 i 结尾的字符串，有多少种翻译；~$dp[i] = dp[i-1] + 1（单加一个） + if_combined$~ （i 和 i - 1 是否能够组合在一起）。应该没有这个 +1，并非叠加，$dp[i] = dp[i-1] + if_combined$

知识点

个人认为关于 DP，有个很关键的地方是，从初始态出发必须能够到达当前状态，他们是有桥梁的，因为每一步都伴随着信息的更新。

JZ.47 礼物的最大价值

自己的思路：感觉是一个和棋盘/二维数组相关的 DP 问题。边界问题补一层 padding，因为 value 非负，直接初始化为0即可。AC，比较简单的 DP 问题。

知识点

数组，DP，矩阵

JZ.48 最长不含重复字符的子字符串

自己的思路：最自然的是暴力法，遍历字符串，往后找其第一个重复的串，记录长度，时间复杂度 $O(n^2$。第一个思路有问题，这个思路不太行。明天来做，2022-04-17 23:39:50。

2022-04-18 11:51:19，AC，做了比较久，做了接近一个小时。总算绕通了其中的逻辑。自己用的应该是双指针遍历的方法，用 hash_map 存出现过的字符串，遇到重复时更新左边的指针，以及舍弃掉此重复字符串左边的字符串。

知识点

标签：滑动窗口，字符串，hash

每日一题 819. 最常见的单词

自己的思路：没什么思路，直接遍历，hash 表存出现的次数，大写转小写。我记得是有大小写转换的函数的，不过忘记了，手动转一下吧。ASCII 差值搞忘了，好像是32？可以建个表。确实是32，还算记得，不用建表了。AC，逻辑有点不清晰，花了大概30分钟。20年4月做过这道题。

4.18

每日一题 386. Lexicographical Numbers ❌

自己的思路：要求时间复杂度 $O(n)$，也就是一次遍历。n < 10 时直接返回 1-n，否则标记 1-9，后续遇到 1 开头的数就插入到 1 后面，然后标记，遇到 2 开头的数就插入到 2 后面，然后标记。不过 vector 插入的时间复杂度好像是 $O(n)$，这样的话整体就是 $O(n^2)$ 了。

15分钟没有思路，上题解。看了一部分评论之后有一个思路，应该将其转换为字符串，这样就无需考虑整数的顺序问题。

题解：迭代 DFS 的思想。对于数 number，加入数组，判断 $10*number \leq n$ 是否成立，如果成立则加入数组，并继续搜索（DFS）；如果不成立，判断 $number + 1$ 的情况，如果 number 的个位数为9（number 个位数1-9已经全部搜索过了）或者 number + 1 > n（DFS返回条件），则回退到上一层（number /= 10）

知识点

标签：DFS，前缀树

JZ.49 丑数 ❌

自己的思路：已知是一道DP。看题解

题解：核心思想是后面的丑数一定由前面的丑数乘以2，或者乘以3，或者乘以5得来。在这个基础上可以使用最小堆，每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆，然后去重。

方法二：DP 三指针。令 $\textit{dp}[i]=\min(\textit{dp}[p_2] \times 2, \textit{dp}[p_3] \times 3, \textit{dp}[p_5] \times 5)$，被使用到的对应指针++。

dp[i] = min(min(n2, n3), n5); 学到了

4.19

每日一题 821.字符的最短距离

自己的思路：第一次遍历记录字符的所有下标，第二次遍历找出当前字符 - 下标集合的最小值。时间复杂度最坏 $O(n^2)$。AC

更好的思路：两次遍历。从左往右，一边遍历一遍更新字符idx；从右往左再来一次。

知识点

int ans[] = new int(len); 写法有问题，注意是：int *ans = new int[len]{0};，一定是指针形式
vector 初始化：vector<int> ans(len); 以及 vector<int> ans; ans.resize(len);

JZ.50 第一个只出现一次的字符

自己的思路：hash，两次遍历。

知识点

这道题有一个比较好奇的地方，map 中元素顺序是否是按加入的顺序；噢，map 似乎是自动排序的，根据 first 排序

JZ.51 数组中的逆序对 ❌

自己的思路：这是一个 hard 题，最自然的想法是暴力法，$o(n^2)$，很自然地，超时。换一种思路，DP，dp[i] 代表位置 i 之前有 dp[i] 个大于 nums[i] 的数。看题解

题解：归并排序和逆序对息息相关，归并排序体现了分治的思想。归并的同时顺便统计信息。

PS：着题解代码写得

知识点

二分查找，归并排序，分治，树状数组，线段树

JZ.50 两个链表的第一个公共节点

自己的思路：题目要求尽量用时间复杂度 $O(n)$，空间复杂度 $O(1)$，

Table of Contents

关键字检索

短板总结

常见 BUG

1. itoa

3.11

查缺补漏

3.11

JZ.03

JZ.04 二维数组中的查找 ❌

JZ.05 替换空格

JZ.06 反转链表

3.13

JZ.07 重建二叉树 ❌

JZ.09 用两个栈实现队列

JZ.10 斐波那契数列 DP

JZ.11 青蛙跳台阶

JZ.11 旋转数组的最小数字 ❌

3.14

JZ.12 矩阵中的路径 ❌

JZ.13 机器人运动范围

JZ.14-I 剪绳子 ❌

3.16

JZ.14-II 剪绳子

JZ.15 二进制中1的个数

JZ.16 数值的整数次方 ❌

JZ.17 打印从1到最大的n位数

JZ.18 删除链表的节点

JZ.20 表示数值的字符串

JZ.21 调整数组顺序使奇数位于偶数前面

JZ.22 链表中倒数第k个节点

JZ.24 反转链表

JZ.25 合并两个递增排序的链表

3.17

JZ.26 树的子结构 ❌

JZ.27 二叉树的镜像

JZ.28 对称的二叉树 ⚠️

JZ.29 顺时针打印矩阵

JZ.30 包含 min 的栈

JZ.31 栈的 push, pop 顺序

JZ.32-II 从上到下打印二叉树

JZ.32-III 从上到下打印二叉树

3.18

3.19

606. Construct String from Binary Tree 每日一题

3.20

JZ.33 二叉搜索树的后序遍历 ❌

3.26

JZ. 19 正则表达式匹配 ❌

JZ. 35 复杂链表的复制

JZ. 36 二叉搜索树与双向链表

JZ.37 序列化二叉树

3.31

728. 自除数 每日一题

4.3

每日一题

JZ.38 字符串的排序 ❌

JZ.39 数组中出现次数超过一半的数字

JZ.40 最小的k个数 ❌

4.4

307 ❌

4.5

762

5. 最长回文子串

每日 310. 最小高度树

4.15

JZ.41 数据流中的中位数

JZ.42 连续子数组的最大和

JZ.43 1～n 整数中 1 出现的次数

JZ.44 数字序列中某一位的数字 ❌

4.16

JZ.45 把数组排成最小的数 ❌

4.17

JZ.46 数字翻译成字符串

JZ.47 礼物的最大价值

JZ.48 最长不含重复字符的子字符串

每日一题 819. 最常见的单词

4.18

每日一题 386. Lexicographical Numbers ❌

JZ.49 丑数 ❌

728. 自除数每日一题