[TOC]
-
- 条件
- 【数组】数据存储结构为纯数组，可以任意顺序读取或随机读取。尾部插入删除操作开销低，其他位置插入删除操作开销大
- 【偶数次重复】重复元素都重复两次
- 【不重复元素唯一】不重复元素只有一个
- 分析：TODO
- 解法
- 【数学：异或位运算】Time=O(n), Space=O(1)
-
异或位运算有如下性质：
- $ a \oplus 0 = a $
- $ a \oplus a = 0 $
- $ a \oplus b = b \oplus a $
- $ a \oplus b \oplus c = a \oplus (b \oplus c) $
-
将整个数组所有元素一起进行异或运算，据异或位运算的性质，可以过滤掉数组内所有偶数次重复的元素，留下唯一不重复的元素：
$ a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b $
-
- 【数学：异或位运算】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【数组】数据存储结构为纯数组，可以任意顺序读取或随机读取。尾部插入删除操作开销低，其他位置插入删除操作开销大
- 分析：TODO
- 解法
- 【逆序遍历】Time=O(n), Space=O(1)
- 从数组尾部向前进行逆序遍历：
- 当前元素=9，则置0
- 当前元素<9，则+1，并返回
- 遍历结束意味着该数字每一位都是9，则分配一个size+1的数组，并将数组首位置1，其余元素置0，然后返回该新数组
- 从数组尾部向前进行逆序遍历：
- 【逆序遍历】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【32位】算法运行环境是32位环境，每次计算不准有多于32位的数据
- 分析：TODO
- 解法
- 【数学：溢出判断】Time=O(n), Space=O(1)
- 要保证翻转后的数字不会溢出，只要如下不等式成立即可： $ -2^{31} \leq reverse \times 10 + digit \leq 2^{31}-1 $ 该不等式可以简化为: $ \lceil \frac{-2^{31}}{10} \rceil \leq reverse \leq \lfloor \frac{2^{31}-1}{10} \rfloor $
- 使用求模再除10的方法，从最低位逐位取出该位数值
- 再使用乘10后相加的方法，把该数值添加到反转数当前的最低位上
- 使用上面的简化后的不等式判定反转数的当前值，不符合判定则返回错误
- 【逆运算还原检查】Time=O(n), Space=O(1)
- 使用求模再除10的方法，从最低位逐位取出该位数值
- 再使用乘10后相加的方法，把该数值添加到反转数当前的最低位上
- 对当前反转数做上一步的逆运算，检查逆运算结果是否与反转数的上一数值等同。若不等同意味着有溢出，返回错误
- 【数学：溢出判断】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【ASCII字符串】
- 分析：TODO
- 解法
- 【确定有限状态机 + 数学：溢出判断】Time=O(n), Space=O(1)
- 初始状态：
- 遍历到空格不做处理
- 遍历到数字转移到“数字状态”
- 遍历到正负号转移到“符号状态”
- 遍历到其他字符转移到“结束状态”
- 数字状态：
- 遍历到非数字转移到“结束状态”
- 遍历到数字则推入最终结果，并做溢出判断
- 符号状态：
- 遍历到数字则转移到“数字状态”
- 遍历到非数字则转移到“结束状态”
- 结束状态：返回最终结果与符号
- 初始状态：
- 【确定有限状态机 + 数学：溢出判断】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【ASCII字符串】
- 分析：TODO
- 解法
- 【子串匹配：KMP算法】
- 条件
-
- 条件
- 分析：TODO
- 解法
- 【字符串遍历】
-
- 条件
- 【字符串数组】
- 分析：TODO
- 解法
- 【矩阵横向查找】
- 步骤
- 以矩阵第一行作为前缀模式初值
- 以行遍历的方式从第二行开始逐字符匹配：
- 相等：比对下一字符
- 不等：比对下一行
- 遍历结束后，返回前缀模式
- 复杂度
- 时间：
- O(m*n)，n是字符串数量，m是字符串平均长度
- 在内存以行存储矩阵且共同前缀较长时，性能优于其他方法
- 空间：O(1)
- 时间：
- 步骤
- 【矩阵纵向查找】
- 步骤
- 以列遍历的方式检查字符矩阵每一列是否相等：
- 相等：检查下一列
- 不等：返回任一行的0列到前一列的内容为最终结果
- 以列遍历的方式检查字符矩阵每一列是否相等：
- 复杂度
- 时间：
- O(m*n)，n是字符串数量，m是字符串平均长度
- 在内存以列存储或者共同前缀非常短时，性能优于其他方法
- 空间：O(1)
- 时间：
- 步骤
- 【矩阵横向查找】
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 【从中间开始】只给出指定要删除节点且保证不是尾节点，不给出链表头节点
- 分析：TODO
- 解法
- 【TODO】Time=O(1), Space=O(1)
- 将指定节点的下一节点的值赋给指定节点
- 将指定节点的下一节点的next赋给指定节点
- 将指定节点的下一节点作为要删除的节点，删除释放掉
- 【TODO】Time=O(1), Space=O(1)
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 分析：TODO
- 解法
- 【快慢指针】Time=O(n), Space=O(1)
- 快指针前进n步后，慢指针再开始前进，保持快指针领先慢指针n个节点
- 快指针遍历完链表成为空指针时，慢指针就指向了倒数第n个节点，删除慢指针指向的节点即可
- 【快慢指针】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 分析：TODO
- 解法
- 【TODO】Time=O(n), Space=O(1)
- 设置3个指针，cur指向当前要翻转的节点，next指向cur的下一节点，pre指向cur的前一节点
- 设置cur指针的next指向pre
- 更新pre指向cur
- 更新cur指向next
- 更新next指向cur.next
- 回到(2)，重复直到cur为空
- 【TODO】Time=O(n), Space=O(1)
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 【有序】两个单链表的节点值是升序的
- 分析
- 【TODO】
- 解法
- 【TODO】
- 算法
- 创建一个新的链表头节点
- 两个链表中的较小的头节点取出来加入到新链表
- 回到(2)，重复直到其中一个链表为空
- 将另一个不空的链表整个添加到新链表
- 返回新链表
- 复杂度
- 时间：O(m + n)，“m”和“n”是两个链表的长度
- 空间：O(1)
- 算法
- 【TODO】
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 分析
- 【TODO】
- 解法
- 【快慢指针】
- 分析
- 【快慢指针步长倍数是遍历元素数量的倍数】快慢指针步长的倍数为n，则当快指针遍历全部元素时，慢指针恰好遍历完1/n的元素
- 步骤
- 设置快慢指针同时从头节点出发向尾节点前进
- 遍历链表并更新快慢指针：
- 快指针每次前进两步，同时累加链表节点计数
- 慢指针每次前进一步，每次离开一个节点前，先反转该节点的next指向原来的前序节点
- 重复(2)，直到快指针到尾节点，此时，慢指针正好在链表中间，而链表前半部分则被翻转：
- 快指针重置为慢指针的next
- 根据链表节点数量的奇偶性分别处理
- 链表节点数为偶数：不做处理
- 链表节点数为奇数：
- 慢指针重置为前一个节点
- 快指针向尾节点前进，慢指针向头节点前进，两指针每次前进一步：
- 修复该节点被慢指针修改的next
- 检查节点值：
- 节点值相等：继续前进
- 节点值不等：修复剩余被慢指针修改的链表顺序，然后返回无效回文判定
- 复杂度
- 时间：O(n)
- 空间：O(1)
- 分析
- 【全局变量递归】
- 分析
- 【TODO】
- 步骤
- 设置一个指向头节点的全局变量后，开始递归
- 从头节点开始递归处理：
- 检查当前节点是否为空节点：
- 空节点：返回有效回文判定
- 非空节点：递归处理该节点的next节点，并检查其返回的判定是不是有效回文：
- 无效回文：直接返回无效回文的判定
- 有效回文：
- 检查当前节点与全局节点的值是否相等：
- 相等：更新全局节点指向其next节点，然后返回有效回文判定
- 不等：直接返回无效回文判定
- 检查当前节点与全局节点的值是否相等：
- 检查当前节点是否为空节点：
- 复杂度
- 时间：O(n)
- 空间：O(1)
- 分析
- 【快慢指针】
- 条件
-
- 条件
- 【单链表】单链表数据结构，可以顺序访问，不能随机访问，不能逆序访问。任何位置的插入删除操作开销都很低
- 分析
- 【TODO】
- 解法
- 【快慢指针】
- 分析
- 【TODO】
- 步骤
- 设置快慢指针同时从头节点出发向尾节点前进
- 使用快慢指针遍历链表：
- 快指针每次前进两步，并检查遍历过的两个节点是否被慢指针指向：
- 是慢指针指向：返回有环的判定
- 不是慢指针指向：继续遍历
- 慢指针每次前进一步
- 快指针每次前进两步，并检查遍历过的两个节点是否被慢指针指向：
- 重复(2)，直到快指针遍历到链表尾节点时返回无环的判定
- 复杂度
- 时间：O(n)
- 空间：O(1)
- 分析
- 【快慢指针】
- 条件
-
- 条件
- 【二叉树】TODO
- 分析
- 【TODO】
- 解法
- 【TODO】
- 步骤
- 检查当前递归节点是否为空：
- 空：返回深度=0
- 非空：
- 递归计算左子树深度
- 递归计算右子树深度
- 取左右子树最大深度值，加一后返回
- 检查当前递归节点是否为空：
- 复杂度
- 时间：O(n)
- 空间：O(
$log_2n$ )
- 步骤
- 【广度优先遍历】
- 步骤
- 广度优先遍历时，每次都先把队列内所有节点全部出队再遍历。这样能保证任意时刻队列内的节点都处于统一深度
- 复杂度
- 时间：O(n)
- 空间：O(
$log_2n$ )
- 步骤
- 【深度优先遍历】
- 步骤
- 使用双栈，并在深度优先遍历时，每次节点入栈都把该节点深度同步入另一个栈
- 复杂度
- 时间：O(n)
- 空间：O(
$log_2n$ )
- 步骤
- 【TODO】
- 条件
-
- 条件
- 【二叉树】TODO
- 【有序】TODO
- 分析
- 【TODO】
- 解法
- 【TODO】
- 分析
- 【TODO】
- 步骤
- 使用值域区间来递归处理每个节点：
- 检查当前节点是否处于区间内：
- 否：返回无效搜索树判定
- 是：
- 递归处理左子树，并将值域区间的下限保留，上限改为自身值
- 递归处理右子树，并将值域区间的上限保留，下限改为自身值
- 检查当前节点是否处于区间内：
- 复杂度
- 时间：O(n)
- 空间：O(
$nlog_2n$ )
- 分析
- 【中序遍历】
- 分析
- 【TODO】
- 步骤
- 中序遍历过程中：
- 出栈前先记录当前节点为pre
- 出栈后检查出栈节点是否大于pre：
- 否：返回无效搜索树判定
- 是：检查出站节点是否小于其右子节点：
- 否：返回无效搜索判定
- 是：继续中序遍历
- 中序遍历过程中：
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
- 分析
- 【TODO】
- 步骤
- 从根节点的左右子节点开始递归
- 每次递归同时处理两个节点：
- 两个节点是否有空结点：
- 两个都是空：返回有效对称判定
- 仅有一个空：返回无效对称判定
- 两个都非空：检查两个节点值是否相等：
- 不等：返回无效对称判定
- 相等：
- 递归处理左节点的左子树和右节点的右子树
- 递归处理左节点的右子树和右节点的左子树
- 两个节点是否有空结点：
- 复杂度
- 时间：O(
$log_2n$ ) - 空间：O(TODO)
- 时间：O(
- 分析
- 【TODO】
- 条件
-
- 条件
- 【二叉树】TODO
- 分析
- 【TODO】
- 解法
- 【广度优先遍历】
- 步骤
- 广度优先遍历时，每次都先把队列内所有节点全部出队再遍历。这样能保证任意时刻队列内的节点都处于统一深度
- 复杂度
- 时间：O(n)
- 空间：O(
$log_2n$ )
- 步骤
- 【广度优先遍历】
- 条件
-
- 条件
- 【二叉树】
- 【有序】
- 分析
- 【TODO】
- 解法
- 【分治】
- 分析
- 【TODO】
- 步骤
- 递归处理整个数组
- 每次递归：
- 取数组最中间元素作树根
- 递归处理数组左半部分得到左子树根并更新到根上
- 递归处理数组右半部分得到右子树根并更新到根上
- 向上一层返回树根
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【分治】
- 条件
-
- 条件
- 【数组】
- 【有序】
- 分析
- 【TODO】
- 解法
- 【尾部归并排序】
- 分析
- 【TODO】
- 步骤
- 从两数组尾部元素开始比较，较大的元素填入第一个数组的尾部空间
- 其中一个数组被全部比较完后，另一数组余下元素直接填充结果
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【尾部归并排序】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 质数的定义是因子只有1和自身，那么如果某数不是质数，则它必然可以因式分解为某几个质数，即它必然是某几个质数的倍数
- 因此，只有知道某个数x是质数，则必然知道2x，3x等不是质数
- 而对于某个数是否为质数，我们只能通过其有没有自身以外的质因子判断，而这些质因子若存在，则必然比他小
- 这意味着我们可以从最小的已知质数开始计算每个质数的倍数并做标记，当遍历到某个更大的数时，该数若有标记就是合数，因为之前遍历发现了它的质因子；若无标记则是质数，因为它没有比它更小的质因子
- 【TODO】
- 解法
- 【埃氏筛】
- 分析
- 【TODO】
- 对于遍历到的某个质数x，虽然他的倍数如2x，3x等必然是合数，但其中有部分倍数即${n \cdot x | n \in [0, x) }$是已经被小于x的质数标记过的，不需要由质数x来冗余标记
- 所以对任意质数x，他的倍数的计算可以直接从它的平方开始，即$x \cdot x$、$x(x+1)$
- 【TODO】
- 步骤
- 构建长度为n的状态数组，小于n的所有数的状态都初始化为true，即先认为所有数都是质数
- 从2这个已知质数开始遍历小于n的所有数，令i为迭代变量：
- 检查状态数组中以i为下标的状态：
- false：继续遍历
- true：
- 累加质数数量
- 检查$i^2$是否小于n：
- 否：继续遍历
- 是：
- 从$i^2$开始遍历，令j为迭代变量，每次迭代步长为i：
- 将状态数组以j为下标的状态置为false
- 从$i^2$开始遍历，令j为迭代变量，每次迭代步长为i：
- 检查状态数组中以i为下标的状态：
- 返回质数数量累加值
- 复杂度
- 时间：O(
$n\log_2\log_2n$ ) - 空间：O(n)
- 时间：O(
- 分析
- 【线性筛】
- 分析
- 【TODO】
- 埃氏筛是有冗余标记的。任意合数有几个质因子就会被埃氏筛冗余标记几次，导致时间复杂度无法达到O(n)
- TODO
- 【TODO】
- 步骤
- TODO
- 复杂度
- 时间：O(n)
- 空间：O(n)
- 分析
- 【埃氏筛】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
- 分析
- 【TODO】
- 步骤
- 循环检查n是否大于0：
- 是：检查n是否能整除3：
- 是：计算n除以3地商，并将商结果覆盖n
- 否：跳出循环
- 否：跳出循环
- 是：检查n是否能整除3：
- 返回n是否等于1的判定结果
- 循环检查n是否大于0：
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【TODO】
- 分析
- 【TODO】
- 32位整数中最大的3的幂为$3^19$，只要n是$3^19$的约数，那么n就必定是3的幂，否则就必定不是3的幂
- 【TODO】
- 步骤
- TODO
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
- 分析
- 【TODO】
- 对于一个比较短的位串，我们是可以直接看出有几个1的。即一个比较小的k，k-位串中1的数量可以直接看出来。则一个较大的位串可以分成好几个小段，直接累加每段中1的数量
- 那么我们可以构建一个k-位串表，以k-位串所有可能值作为下标或者说映射的键，则表上有$2^k$个元素，每个元素值都是其下标的二进制表示中1的数量
- n每次都与全是1的k-位串做位与运算，可以得到最低k位的二进制表示，该位串作为下标直接查表即可得到n最低k位中有几个1，统计后将n向右位移即可继续做同样的运算
- 【TODO】
- 步骤
- TODO
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【Brian Kernighan】
- 分析
- 【TODO】
- 只要不断右移并统计最低位的1的个数，或者用$2^i$来匹配并统计即可
- 但是注意$n & (n-1)$的运算结果恰好就是把n最低为的1置0，可以利用该性质加速检查过程
- 不断将$n & (n-1)$的运算结果覆盖n，直到n=0，期间计算了多少次，n中就有多少个1
- 【TODO】
- 步骤
- TODO
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【平行法】
-
分析
- 【TODO】
- 将位串每相邻的两位分成一组，每组的两位相加并将运算结果的二进制表示覆盖本组，此时每组的两个位合起来表示的是本组的1的数量
- 将整个位串每相邻的四位分成一组，每组的四位相加并将运算结果的二进制表示覆盖本组，此时每组的四个位合起来表示的是本组的1的数量
- 不断扩大每组的位数并重复上述步骤，直到所有位分作一组并计算出相加结果即可得到整个位串的1的数量
- 【TODO】
-
算法
fn hamming_weight(mut n: u32) -> usize { n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555); n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333); n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f); n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff); n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff); n as usize } -
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 异或运算识别出两个位串有哪些位不同，这些位都会被置为1
- 计算异或结果中1的个数即可得到汉明距离
- 【TODO】
- 解法
- 【TODO】
- 分析
- 【TODO】
- 步骤
- TODO
- 复杂度
- 时间：O(TODO)
- 空间：O(TODO)
- 分析
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
-
【二分旋转】
-
分析
- 【TODO】
- 将32位串分成两半进行旋转，即前16位和后16位整体交换
- 再分别对两串16位串分成两半8位串继续旋转
- 以此类推直到分割成两个1位串并旋转完
- 【TODO】
-
算法
fn reverse_bits(mut x: u32) -> usize { x = (x >> 16) | (x << 16); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); x as usize } -
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
-
【分治】
-
分析
- 【TODO】
- 将位串每相邻的两位分成一组，每组的两位交换
- 再将整个位串每相邻的四位分成一组，每组的高两位和低两位整体交换
- 如上不断扩大每组的位数并重复上述步骤，直到所有位分作一组并把高16位和低16位整体交换
- 【TODO】
-
算法
fn reverse_bits(mut x: u32) -> usize { x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); x as usize } -
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
-
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 杨辉三角在计算机的按行存储的模型下，会被左对齐，三角左边的1在一列上
- 在计算机存储模型视角下，杨辉三角每个元素(i,j)都是上一行的同列元素(i-1, j)和前列元素(i-1, j-1)之和
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 一个有效的括号表达式，最底层的嵌套的括号对，其开括号一定比上层开括号出现的最晚，但其闭括号却比上层闭括号出现的最早，这很适合栈的出入原则——后进先出
- 遇到开括号入栈，遇到闭括号，就出栈检查开括号是否与该闭括号匹配
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 数组有n个数，每个数都不同，而值域是[0, n]的n+1个数，意味着数组只缺失了一个数字
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【数学：数列求和】
- 这是一个缺失了一个数字的等差数列，可以计算该等差数列和，然后再计算数组和，两个和相减的差就是缺失的数字
- 【数学：数列求和】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
-
分析
- 【数学：异或位运算】
- 数组的每个数字都是唯一的，而且只缺失了值域中的一个数字，意味着如果在数组后面把值域所有数字都添加上去，则缺失的数字唯一，而其他数字全都重复两次
- 对于一个数组只有一个数字唯一，其他数字都重复两次，可以使用异或位运算的性质求解
- 【数学：异或位运算】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 蛮力法通过枚举所有可能的三元组来解题，每一次枚举都首先遍历地确定第一个元素和第二个元素，然后遍历寻找第三个元素。遍历完后枚举一个新的第二元素，再进行一次第三元素的枚举。第二元素也遍历完了就开始枚举新的第一元素，直到所有元素曾作为第一元素被枚举过
- 分析$a_i + a_j + a_k = 0$，可以发现：
- 要么三个元素全是0，否则必有一个元素是小于0的，且还元素肯定是元组最小值，我们让最小值总是排在三元组第一位。这意味着如果我们可以在遍历第一元素时确定之后元素都是正数的话，就可以提前结束枚举。如果将数组排序，即可很快确定正负元素分界，从而实现优化
- 当第一元$a_i$确定后，我们就是要寻找一个$(j, k)$组合使得$a_j + a_k = -a_i$。我们可以假设不等式$a_j \leq a_k$成立，这意味着当我们遍历时有以下三种情况：
-
$a_j + a_k < -a_i$ ：如果我们令第三元总是当前剩余元素里最大的那个元素，则这种情况意味着第二元素$a_j$太小了，我们需要稍微大一点的第三元。如果将数组排序，即可很快找到更大的元素 -
$a_j + a_k > -a_i$ ：如果我们令第二元总是当前剩余元素里最小的那个元素，则这种情况意味着第三元素$a_k$太大了，我们需要稍微小一点的第三元。如果将数组排序，即可很快找到更小的元素 -
$a_j + a_k = -a_i$ ：找到一个符合要求的元组，将$a_j$和$a_k$都从备选元素里排除，因为他们任何一个都不可能再和当前的第一元$a_i$组成一个不重复的三元组了
-
- 从以上分析可见，将数组排序可以得到较大的优化，且排序后去重也变得简单，只要遍历时简单跳过重复元素即可，对于排序后的数组：
- 三元组所有元遍历时都跳过和上一次遍历元素重复的元素
- 第一元遍历到非0正数就停止遍历返回结果
- 第二元从第一元的下一元素开始遍历，第三元则从数组末尾开始遍历。重复迭代到二者交叉后迭代第一元：
- 二者和太小：第二元向前迭代一步
- 二者和太大：第三元向前迭代一步
- 找到符合条件三元组：第二元和第三元同时向前迭代一步
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(
$n^2$ ) - 空间：O(
$log_2n$ )
- 时间：O(
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 在矩阵中遇到一个0元素时，不能直接将所在行列元素清0，否则接下来的遍历中遇到的0很难确认是原本为0还是被清理成0，从而无法确定是否要执行行列的清0操作。因此遇到0元素，没有辅助空间标记要被清0的行列，将会非常困难
- 但如果限制不使用额外空间，就必然要从数据本身自带的空间“原地”标记，需要两块空间分别标记行列，而矩阵首行标记列和首列标记行是个容易想到的选择
- 首行和首列的内容会在遍历矩阵过程中被修改，但是这样的修改是不影响输出正确性的，因为首行和首列无论本身就是0还是被清0，其最终结果也都是0
- 首行和首列记录了矩阵其余行列是否应该被清0，但无法记录矩阵的首行首列是否应该被清0，所以需要两个额外的变量标记
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 遍历字符串时，如何判断当前字符是不是重复字符，如何判断遇到重复字符时如何操作最省时间，这些问题可以借鉴KMP回溯的**：
- 可以通过哈希的方法判断遍历到的字符是不是重复字符
- 遇到重复字符时就要滑动子串的开头，让它去掉子串头到重复字符在内的所有字符
- 综上可以通过以字符值为键，字符下标为值的哈希表，每当遍历到在哈希表有记录的字符就是遇到重复字符，把子串头设置为哈希表记录的下标的下一位，并将当前遍历到的字符下标更新到哈希表
- 遍历字符串时，如何判断当前字符是不是重复字符，如何判断遇到重复字符时如何操作最省时间，这些问题可以借鉴KMP回溯的**：
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 一个递增的三元序列，其前两元组成的序列必然是递增二元序列，也就是说递增三元子序列存在的必要条件是存在递增二元子序列
- 递增二元子序列的寻找和确定是简单的，而且总能找到出现的第一个递增二元子序列。当找到第一个递增二元子序列$\left<s_i, s_j\right>$后，接下来寻找第三元$s_k$时，遍历到的元素$A$会有以下三种情况：
-
$s_i < s_j < A$ ：A就是我们要找的第三元，直接返回结果 -
$s_i < A < s_j$ ：A到现在的第二元之间没有我们要找的第三元，而A比当前的第二元小，又是位于第一元之后的比第一元大的元素，将第二元更新为A，显然放宽了第三元的条件，能在之后更容易找到符合要求的第三元 -
$A < s_i < s_j$ ：- 因为只要A的值比第二元大，就可以确定A是第三元，而第一元的值是用不上的，换言之，在这个递增的场景下，第二元的值是包含了第一元的值的信息的（即“前面有更小的元素”这一信息），这一隐含的约束确保递增三元序列的成立
- 既然第一元的值用不上，那么更新第一元为更小的元素值，显然是放宽了第二元的条件，能在之后寻找到更小的第二元，从而放宽第三元的条件
- 但是不能滚动地把第一元的旧值更新给第二元，尽管这看起来非常自然。因为第一元的值并不必然包含“前面有更小的元素”这一条件，破坏了我们找到的第一次出现的递增二元子序列里第二元包含的逻辑约束，使得之后再找到比使用第一元值的第二元更大的元素时，无法确保是有一个递增三元子序列存在
-
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
- 因为两个链不一定长度相同，使得遍历时不能保证同时迭代到相交节点，导致无法通过比对指针来确定是否共链
- 可以先确定两个链表长度，计算长度差，让较长的链表先行迭代到长度差被抹平，再两个链表同时迭代，就能保证相交节点可以被同时遍历到
- 【TODO】
-
算法
-
复杂度
- 时间：O(n)
- 空间：O(1)
-
- 【TODO】
-
分析
- 【TODO】
- 两个指针分别对两个链表同时遍历，一旦指针所在链表遍历完后就立刻从另一个链表头开始继续遍历，直到两个指针相遇，此时相遇节点就是相交点
- 这个算法我不知道是怎么想出来发明出来的，但是其正确性是可以简单证明的：
- 两个链表分别是：
$a_1 \rightarrow a_2 \rightarrow c_1 \rightarrow c_2 \rightarrow c_3$ $b_1 \rightarrow b_2 \rightarrow b_3 \rightarrow c_1 \rightarrow c_2 \rightarrow c_3$
- 该算法下两个指针的遍历路径如下：
$a_1, a_2, c_1, c_2, c_3, b_1, b_2, b_3, c_1$ $b_1, b_2, b_3, c_1, c_2, c_3, a_1, a_2, c_1$
- 显然无论链表如何变化，都会如同以上遍历路径，最终只需要$2n+2m+k+1$步即可相遇，其中n和m是链表各自不相交的节点数，k是相交共享的节点数
- 两个链表分别是：
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 因为输出结果要求按层序组织，所以层序遍历时稍微修改一下，每次出队都把整队列所有节点出队即可实现按层序处理该层所有节点，从而实现结果按层序组织
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
- 前序遍历和中序遍历的输出结果分别如下：
- 前序：{ 根, {左子树}, {右子树} }
- 中序：{ {左子树}, 根, {右子树} }
- 可根据前序的第一个元素确定中序哪个元素是根
- 中序确定根后，可知左子树和右子树分别有多少个节点，从而在前序中划分出左右子树
- 递归运用以上两点性质即可通过前序和中序来反序列化二叉树
- 前序遍历和中序遍历的输出结果分别如下：
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
-
分析
- 【TODO】
- 从任意子树根到该子树的最左叶子的节点，把这些节点从前序遍历或者中序遍历中保持出现顺序地摘选出来，一个称为前序摘选，一个称为中序摘选，而该子树则称为摘选子树，则有如下性质：
-
前序摘选性质：
- 前序摘选的首个元素总会是被摘选子树的根
- 前序摘选在前序遍历中总是一个紧邻相连的部分，即被摘选的节点之间没有其他节点穿插其中
- 前序摘选最后一个被摘选节点，在前序遍历中该节点后面紧邻的节点必定是被摘选节点中某一节点的右子树根
- 前序摘选的左边界即首元素，是摘选迭代中确定的，一开始是前序遍历结果的首元素作为左边界，之后是上一摘选子树右边界节点在前序遍历中紧随其后的节点
-
中序摘选性质：
- 中序摘选的首个元素总会是被摘选子树的最左叶子
- 中序摘选在中序遍历中是否是紧邻相连的部分，取决于这些节点有无右子树：
- 所有节点没有右子树：中序摘选也是中序遍历中一块紧邻相连的部分
- 至少一个节点有右子树：中序遍历中这些被摘选的节点不是紧邻相连的，其中必有某两个被摘选节点之间穿插了前一个节点的右子树
- 中序摘选的左边界即首元素，是摘选迭代中确定的，一开始是中序遍历结果的首元素作为左边界，之后是上一摘选子树中第一个在中序遍历被穿插分隔的摘选节点的紧随其后的节点
-
前序摘选性质：
- 前序摘选和中序摘选之间有如下关系：
- 前序摘选总是会与中序摘选相反，即互为逆序
- 根据中序摘选的性质2，可以确定前序摘选的右边界节点
- 根据前序摘选的性质2，可以确定中序摘选的右边界节点
- 根据中序摘选的性质3.2，可以确定前序摘选中哪一个节点拥有性质3提到的右子树
- 实现方法大致如下：
-
设置一个变量作为当前摘选子树最左叶子的锚，也就是中序摘选左边界。初值是指向中序遍历首元素，即整棵树的最左叶子
-
遍历前序结果并逐个按序压栈，直到栈顶节点等于最左锚。此时栈中就是当前摘选子树的前序摘选，而当前遍历到但尚未压栈的前序结果节点就是新摘选子树根
-
接下来我们要做的就是为新摘选子树找到其父节点是当前哪一个摘选节点，根据关系4：
注意，最左锚指向中序遍历中被摘选子树所在的区间内，要么指向摘选节点，要么指向某个摘选节点的右子树
- 检查栈顶节点是否等于最左锚：
- 等于：出栈，同时向右推动最左锚
- 二者相等意味着目前前序摘选的逆序（入栈会反序化）和中序摘选的逆序是这一部分是相等，这表明现在遍历到的摘选节点都是无右子树节点，新摘选子树的父节点还没有找到
- 出栈并向右推动最左锚相当于同时遍历前序摘选的逆序和中序摘选
- 不等：跳出寻找新摘选子树的父节点的循环，以新摘选子树继续之前的循环，此时最左锚就是新摘选子树的最左锚
- 等于：出栈，同时向右推动最左锚
- 检查栈顶节点是否等于最左锚：
-
上述不断摘选的过程就是还原了正确的前序遍历过程，只要在过程中适当地方建立二叉树关系即可
-
- 从任意子树根到该子树的最左叶子的节点，把这些节点从前序遍历或者中序遍历中保持出现顺序地摘选出来，一个称为前序摘选，一个称为中序摘选，而该子树则称为摘选子树，则有如下性质：
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
- 如果可以按顺序的分层遍历每层的节点，就可以简单的设置next指针，而层序遍历就能做到
- 需要注意的是，因为每层的最后一个节点的next指针是空而不是指向下一层，所以结果是按层组织的，层序遍历时要一次把整层都倒出来遍历，不能一边遍历一边插队
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
-
分析
- 【TODO】
- 树的遍历总是要用到额外空间的，但如果限制为O(1)空间的话，就必然要利用甚至占用输入数据内的空间
- 对于任一节点来说，如果它是父节点的：
- 左子节点：则该节点的next指向兄弟节点即父节点的右子节点
- 右子节点：则该节点的next指向父节点的next节点的左子节点
- 也就是说对于任一层节点来说，只要上一层节点的next被正确设置，就能简单遍历上一层节点来设置其下一层节点的next
- 而整棵树的第一层是根节点，也恰好是next被正确设置的一层，从第一层开始可以递推地设置完所有层
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【二叉搜索树】
- 分析
- 【TODO】
- 二叉搜索树的中序遍历是一个有序的序列
- 只需要中序遍历该树，返回遍历到的第k个节点即可
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【TODO】数组两侧视为无穷小：$a_{-1} = a_n = -\infty$
- 【TODO】数组任意一对相邻的两个数不相等：$a_{i-1} \ne a_i \ne a_{i+1}$
- 分析
- 【TODO】
- 有三种情况下的数组不存在峰值，但这三种情况都因题目条件限制而不可能成立：
- 单调递增：数组尾元素满足峰值条件：
- 大于前一元素：因为严格单调递增，尾元素是最大值，必然大于前一元素
- 大于后一元素（数组尾）：因为数组尾是负无穷，意味着尾元素大于数组尾
- 单调递减：数组首元素满足峰值条件：
- 大于前一元素（数组头）：因为数组头是负无穷，意味着首元素大于数组头
- 大于后一元素：因为严格单调递减，首元素是最大值，必然大于后一元素
- 不增不减：因为限制了相邻两个元素不等，所以数组所有元素相等是不可能成立的
- 单调递增：数组尾元素满足峰值条件：
- 综上，数组峰值必定存在，且按单调性分割数组，可以不遗漏任何元素地分成多个单调数列
- 将数组按单调性划分为多个单调数列后，峰值只存在于以下两种情况：
- 递增数列尾：
- 数列尾是数组尾元素：如上分析，此时数列尾是峰值
- 数列尾不是数组尾元素：
- 大于前一元素：因为严格单调递增，尾元素是最大值，必然大于前一元素
- 大于后一元素：后一元素必然小于数列尾，否则递增数列应扩展数列尾到后一元素
- 递减数列头：
- 数列头是数组首元素：如上分析，此时数列头是峰值
- 数列头不是数组首元素：
- 大于前一元素：前一元素必然小于数列头，否则递减数列应扩展数列头到前一元素
- 大于后一元素：因为严格单调递减，首元素是最大值，必然大于后一元素
- 递增数列尾：
- 单调数列划分后，任一元素必然属于其中一个单调数列，有以下三种情况：
- 递增数列尾+递减数列头：此时元素站在相邻的递增数列和递减数列之间，恰好就是峰值
- 递增数列元素：此时元素属于递增数列，峰值在它的右侧沿着数字增大的方向
- 递减数列元素：此时元素属于递减数列，峰值在它的左侧沿着数字增大的方向
- 综上，对于任意元素而言，要么是峰值，要么沿着左右两侧数字增大的方向遍历可以找到峰值
- 有三种情况下的数组不存在峰值，但这三种情况都因题目条件限制而不可能成立：
- 【TODO】
- 解法
- 【二分查找】
-
分析
- 【TODO】
- 因为非峰值元素只要沿着左右两侧数字增大的方向就可以找到峰值，我们可以依据这个定义二分搜索规则：对于每次二分出来的中间元素：
- 中间元素大于两侧：找到峰值，返回结果
- 中间元素小于两侧：此时向任一侧继续二分都可以，我们规定向右侧
- 中间元素仅小于左侧：向左侧继续二分查找
- 中间元素仅小于右侧：向右侧继续二分查找
- 使用以上二分规则就可以实现二分查找来找到峰值
- 因为非峰值元素只要沿着左右两侧数字增大的方向就可以找到峰值，我们可以依据这个定义二分搜索规则：对于每次二分出来的中间元素：
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【二分查找】
- 条件
-
- 条件
- 【TODO】
- 分析
- 【TODO】
- 虽然我们不知道旋转后两个子数组的交界在哪儿，但被旋转的数组是升序排列的，意味着两个子数组较大的那个一定在数组前半部分，较小的一定在数组后半部分
- 这意味着数组首元素就是左子数组的首元素，即数组首元素$a_0$一定是大于右子数组的所有元素的，因此可通过判断任一元素与数组首元素的大小关系来确定该元素应该会在左右哪一数组中出现
- 具体来说，对任意的目标元素$t$，有如下情况：
-
$t = a_0$ ：数组首元就是目标元素，直接返回结果 -
$t > a_0$ ：目标元素必然在左子数组。因为目标大于首元，所以一定大于整个右子数组，不可能等于其中某元素 -
$t < a_0$ ：目标元素必然在右子数组。因为目标小于首元，所以一定小于整个左子数组，不可能等于其中某元素
-
- 对于除$t$以外的另一个元素$a_m$，该元素要么大于它、要么小于它，综合$t$和$a_m$分别在左右哪个数组来考虑有：
-
$t > a_0$ （$t$在左数组）：-
$a_m > a_0$ （$a_m$在左数组）：-
$a_m < t$ ：$a_m$的右侧是$t$ -
$a_m > t$ ：$a_m$的左侧是$t$
-
-
$a_m < a_0$ （$a_m$在右数组）：$a_m$的左侧是$t$
-
-
$t < a_0$ （$t$在右数组）：-
$a_m > a_0$ （$a_m$在左数组）：$a_m$的右侧是$t$ -
$a_m < a_0$ （$a_m$在右数组）：-
$a_m < t$ ：$a_m$的右侧是$t$ -
$a_m > t$ ：$a_m$的左侧是$t$
-
-
-
- 以上关系性质定义了任意元素如何确定向哪个方向迭代能接近目标元素的规则，可以直接用于定义二分搜索规则，从而实现二分搜索查找目标元素
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
-
- 条件
- 【矩阵】
- 【有序】每行按升序排列，每列也按升序排列
- 分析
- 【TODO】
- 矩阵中的行列都是升序排列，这意味着对任一元素$a_{xy}$，比对其与目标$t$大小关系时，有如下性质：
-
$t = a_{xy}$ ：该元素就是目标，返回结果 -
$t < a_{xy}$ ：因为列是升序排列，所以第y列从第x个元素以下都大于目标，因此不可能有目标值 -
$t > a_{xy}$ ：因为行是升序排列，所以第x行从第y个元素以前都小于目标，因此不可能有目标值
-
- 综上，每次比对，我们要么找到目标、要么排除一列的部分元素，要么排除一行的部分元素。为了能排除更多的元素：
- 从列头$a_{0y}$开始比对，因为发现目标小于元素时，该元素越靠近列头，就可以排除更多该列元素
- 从行尾$a_{xn}$开始比对，因为发现目标大于元素时，该元素越靠近行尾，就可以排除更多该行元素
- 因此我们可以从右上角的$a_{0n}$开始，向左下角的$a_{m0}$以Z形遍历比对，即从第一行开始每次遍历一行，每行从行尾开始遍历，令$i$位遍历行，$j$为遍历列：
-
$t = a_{ij}$ ：该元素就是目标，返回结果 -
$t < a_{ij}$ ：$j$向左前进一步整列排除，因为该列前i个元素已经在之前的遍历中被比对过，都不是目标，而剩下的$m-i$个元素都比目标大，不可能是目标
-
$t > a_{ij}$ ：$i$向下前进一步整列排除，因为该行后$n-j$个元素已经在之前的遍历中被比对过，都不是目标，而剩下的$j$个元素都比目标大，不可能是目标
-
- 矩阵中的行列都是升序排列，这意味着对任一元素$a_{xy}$，比对其与目标$t$大小关系时，有如下性质：
- 【TODO】
- 解法
- 【TODO】
-
分析
- 【TODO】
-
算法
-
复杂度
- 时间：O(TODO)
- 空间：O(TODO)
-
- 【TODO】
- 条件
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent