常见算法题
常见算法题
  查找
    二分查找
      只适合在数组
        因为要跳跃式查找
      小数据量下，线性查找性能更佳
        在线性查找中，每轮只需 1 次判断操作
        在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作
      查找插入点
        在二分查找插入点的算法中，循环结束时必有：j<target<i（更准确说：nums[j] < target ≤ nums[i]）
    重拾查找
      偏暴力
        通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
          无须对数据做预处理和借助额外的数据结构
          此类算法的时间复杂度为 O( n)
          小数据，频繁更新
      不暴力
        利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。
          使用这些算法往往需要对数据进行预处理
          时间复杂度可达到 O(logn) 甚至 O(1)
          大数据，不频繁更新
    优化
      如果能干引入 O(n) 的数据结构，则可以尝试引入哈希表来处理这个问题
  排序
    运行效率
      我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。
        对于大数据量的情况，运行效率显得尤为重要。
    就地性
      顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。
        通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
    稳定性
      稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。
    自适应性
      自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。
        TimSort：Python和Java的默认排序，对部分有序数据很高效
        冒泡排序：可以提前结束优化
          因为数据是否局部/全局有序可以通过一趟扫描是否发生交换来确定
        对于已排序和数据偏斜适应得很好
    是否基于比较
      基于比较的排序依赖比较运算符（<、>、=）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 O(nlogn)。
      而非比较排序不使用比较运算符，时间复杂度可达O(n)，但其通用性相对较差。
        计数排序：O(n + k)
        基数排序：O(d × n)
        桶排序：平均 O(n)
    具体算法
      比较排序
        选择排序
          时间复杂度为 O(n^2)
          非自适应排序
          空间复杂度为O(1)
          原地排序
          非稳定排序
        冒泡排序
          冒泡排序的最差时间复杂度和平均时间复杂度仍为 O(n^2)
          但当输入数组完全有序时，可达到最佳时间复杂度 O(n)
          自适应排序
            对于已排序和数据偏斜适应得很好
          空间复杂度为 O(1)
          原地排序
          稳定排序
            由于在“冒泡”中遇到相等元素不交换。
        插入排序
          时间复杂度为 O(n^2)
          自适应排序
            对于已排序和数据偏斜适应得很好
          空间复杂度为 O(1)
          原地排序
          稳定排序
            在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。
        快速排序
          时间复杂度为 O(nlogn)
            在平均情况下，哨兵划分的递归层数为 logn ，每层中的总循环数为 n ，总体使用 O(nlogn) 时间。
            性能优势
              现最差情况的概率很低
                虽然快速排序的最差时间复杂度为 O(n^2) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O(nlogn) 的时间复杂度下运行。
              缓存使用效率高
                在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。
              复杂度的常数系数小
                在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少
            基准数优化
              随机化劣势
                随机化也有自己的劣化案例
              中位数优化
                我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。
          非自适应排序
          空间复杂度为 O(n)
            最差的空间复杂度是O(n)
              仅对较短的子数组递归，则最差复杂度变成 O(logn)
          原地排序
          非稳定排序
        归并排序
          时间复杂度为 O(nlogn)
            划分产生高度为 logn 的递归树，每层合并的总操作数量为 n
          非自适应排序
          空间复杂度为 O(n)
          非原地排序
            稳定排序
          链表排序
            归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 O(1)
            划分阶段
            合并阶段
        堆排序
          传统排序法
            准备一个堆和 result 列表，弹出最大/最小的数到结果列表里
          优化排法
            每次把堆的最大值交换到尾部，让堆缩小
          时间复杂度为 O(nlogn)
          非自适应排序
          空间复杂度为 O(1)
          原地排序
          非稳定排序
      非比较排序
        它适用于数据量 n
较大但数据范围 m
较小的情况。
        桶排序
          桶排序适用于处理体量很大的数据。要先分桶分别排序，后面再合并。
          时间复杂度为 O(n+k)
            当桶数量 k 比较大时，时间复杂度则趋向于 O(n)
            桶排序的时间复杂度理论上可以达到 O(n)，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。
              为实现平均分配，我们可以先设定一条大致的分界线，将数据粗略地分到 3 个桶中。
分配完毕后，再将商品较多的桶继续划分为 3 个桶，直至所有桶中的元素数量大致相等。
              如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。
          空间复杂度为 O(n+k)
          非原地排序
        计数排序
          时间复杂度为 O(n+m)
          非自适应排序
          空间复杂度为 O(n+m)
          非原地排序
          稳定排序
        基数排序
          基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。
            浮点数不适合使用基数排序
          时间复杂度为 O(nk)
          非自适应排序
          空间复杂度为 O(n+d)
          非原地排序
          稳定排序
  位运算
    (cols & mask1) 位运算完结果一定要用小括号括起来，才能当整数用，或者赋给其他变量
    任意非0的数必定至少包含1个1
    n &(n-1) 至少会消费1个1-这不需要任何掩码就能做到
      时间复杂度 O(logn)
    所有的操作里一般都包含
      位移-左右移
      用掩码取位
        这一步很容易被忘记
      把取出的位用 | 赋值，或者用 & ~ ^ 进行其他操作
    右边的位是低位
      ASCII 码是最早出现的字符集，其全称为 American Standard Code for Information Interchange（美国标准信息交换代码）。它使用 7 位二进制数（一个字节的低 7 位）表示一个字符，最多能够表示 128 个不同的字符。
    java 有个 bitset 可以当 bitmap
  bfs
    通常要考虑引入辅助队列，而且出入队的顺序有技巧
  dfs
    通常要先思考是不是前中后遍历问题
      是不是搜索二叉树
      是不是可以用回溯
        是不是可以用hashmap
        是不是用 lastVisited 和 current 解决子读不到父的问题
  回溯
    从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。
    前序、中序和后序遍历都属于深度优先搜索
    复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。
    搜索/回溯通常是在离散、组合的状态空间里寻找可行或最优解，需要枚举并剪枝；
    典型例题
      可以解，但是最好不要用回溯解
      搜索问题
        全排列问题
          球盒模型 n 是球的数量，k 是盒子数量
            盒子视角
              P(n, k) = nP(n-1, k-1)
                n!/(n-k)!
                  分步计数乘法原理
                    n(n-1)...(n-m+1) 化简得到基础公式
                每个盒子每次必取一个球
            球的视角
              P(n, k) = P(n-1, k) + kP(n-1, k-1)
                每个球不放，就彻底放弃，对应前半部分；放有k种选择，对应后半部分
        组合问题
          n!/((n-k)!*k!)
            第一步，就是从
n
个球中抽
m
个出来，先不排序，此即组合数问题
C
m
n
；
            第二步，则是把这
m
个被抽出来的球排序，即全排列
A
m
m
。
            根据乘法原理，
Amn=Cmn *Amm
        子集和问题
          易错的点
            本元素可以被重复选择吗
              要注意是否可以重复选择本元素，或者用相邻元素排除法
            乱序的情况下产生乱序的重复组合需要去重吗
              需要
                先排序，然后每轮更新 start
                引入 hashSet
              不需要
                允许每轮迭代 start 都从本元素i开始
            无限递归
              完全反方向的case
              越界的 case
        汉诺塔问题
      约束满足问题
        皇后
          剪枝的做法
            逐行放皇后
            对角线
              主对角线
                row - col 是恒等值
                  对n*n的矩阵，row/col的最大值都是 n-1，最小值都是0，所以如果 row-col 的范围是 [1-n, n-1]
              次对角线
                row + col 是恒等值
                  同上，row+col的最大范围是[0,2n-2]
            所以数组上界-下界+1会得到 2n-1，对角线的长度就是 2n-1
        数独
        图着色问题
      组合优化问题
        0-1 背包问题
        旅行商问题
        最大团问题
  动态规划
    基石
      Bellman 最优性原理（Bellman’s Principle of Optimality）
        最优子结构 Optimal Substructure
          一个问题的最优解可以通过其子问题的最优解来构造
            第 n 阶最大方案数量等于第 n -1 阶和第 n-2 阶最大方案数量之和。
        无后效性 Without Aftereffect
          给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。
            反例
              给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶，但不能连续两轮跳 1 阶，请问有多少种方案可以爬到楼顶？
                ≈ ​​概率中的“不放回抽样”​
            ≈ ​​概率中的“放回抽样”​
        重叠子问题 Overlapping Subproblems
    判断
      适合
        可以用决策和决策树来表达问题的探索过程
        问题包含最大（小）或最多（少）等最优化描述
        问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
      不适合
        问题的目标是找出所有可能的解决方案，而不是找出最优解。
        问题描述中有明显的排列组合的特征，需要返回具体的多个方案。
    步骤
      描述决策
        暴力搜索
        记忆化搜索
        动态规划
      定义状态
      建立dp表
      推导状态转移方程
      确定边界条件
        对于很多dp方程来讲，是初始条件
          一维dp是初始的点
          二维dp是初始的边
    爬楼梯
      加法原理
        ​​dp[i] = dp[i - 1] + dp[i - 2]​​
          如此一来，dp[i]会被它上层的所有父问题（dp[i+1], dp[i+2], ..., dp[n]）多次调用。
​​结论是：dp[i]被重复计算的次数等于计算 dp[n]时的斐波那契数 F(n-i+1)。​
          这是一个一维dp的例子，即只有一个参数
            这种 dp 是可以被压缩成0维 dp 的
      暴力搜索
        类似二叉树子树高度问题
      动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。
  记忆化搜索 Memoization/Memoized Search
  分治法
    最大子数组问题
      股票问题
        股票并不是简单低买高卖就能收获足够多的利润，而需要转化成一个最大子数组问题-leetcode
        把这个股票问题的“最优性条件”（这其实是一个最大极值问题）想成一条单向过山车轨道：
• 你只能从左往右走（时间不能倒流）。
• 轨道上有高高低低的山峰和谷底。
• 游戏规则：任选一处先“蹲下”（买入），再往前走，任选一处“站起”（卖出）。
• 你的收益＝站起的高度 − 蹲下时的高度。
“最优性条件”就是：
当你站起的那一瞬间，之前所有蹲过的点里，最低的那个点一定就是真正的最佳买入点；任何更早或更晚的买入点都不会比它更优。
换句话说，在你走到当前最高点之前，只要记住“迄今为止见过的最低谷”就够了；不需要回头看整条轨道的全局最低——因为它可能在你身后还没出现，或者根本无法回头去蹲。
这就是数学里的“最优性条件”：
最优解只依赖于“合法前缀”内的极值，而不是整个序列的极值。
          如果股票价格是升序数组，那么满足最优性条件。最优性条件带有时序限制。
          时间约束：我们只能从过去走向未来，无法回到过去
            如果决策有严格的时间顺序约束 → 考虑贪心
            如果可以"回头"做决策 → 需要DP
          决策约束：必须先买入，后卖出
          信息约束：在任何时刻t，我们只知道时刻0到t的信息
          目标：最大化 sell_price - buy_price
          最优子结构检验
            在时刻t的最优解只依赖于[0,t]的信息 → 贪心可行
              max_profit = max(max_profit, prices[t] - min_price_so_far)
              min_price_so_far = min(min_price_so_far, prices[t])
            需要未来信息或多个时间点的组合 → 需要DP
          传统思维假设："最优解需要考虑全局信息" 质疑：在有时间约束的情况下，这个假设是否成立？
      可能存在多个最大子数组
      只有子数组包含负数时，最大子数组才不是数组本身
        这是转化成差额数组的奇妙之处
      难以想到的点：我们可以用转化的方法，把价格变动问题，转化成带负数的子数组问题
        任意两点的差值，等于差分数组的两点之间所有变化值的和
      把问题均匀二分是比较容易想到的分治逻辑
      时间复杂度
        假设输入规模为2的幂，可以大致上简化问题的分析，而不产生太大的偏差
        O(nlgn)
      适配条件
        ① 目标是某段连续区间的聚合值（和、积、最大字段、最长上升段等）；
        ② 聚合函数可分解：跨区间值能由左右区间的少量可合并信息（前缀、后缀、区间和、最值）在 O(len) 时间内推出；
          前缀与序列
            合法前缀 = 你站在现在能看到的过去
              合法前缀：[7, 1, 5, 3, 6] - 你在第5天能看到的所有信息
                关键洞察：当你在第5天决定是否卖出时，你：
                  ✅ 可以选择前5天任意一天作为买入点
                    合法选择：买入点只能在第0-4天之间
                    最优买入点：第1天（价格=1），因为它是前缀[7,1,5,3,6]中的最小值
                  ❌ 不能选择第6、7、8天作为买入点（还没发生）
                    为什么不考虑第6天（价格=4）：因为你不能在未来买入，然后在过去卖出
              只需要"过去的极值" → 贪心
                单次买卖股票（贪心）
            整个序列 = 上帝视角，包含未来
              需要"未来的信息"或"复杂的历史组合" → DP
                票with冷却期（DP）
                背包问题（DP）
          整个序列：[7, 1, 5, 3, 6, 4, 9, 2] - 包含未来信息
          profit(t) = price[t] - min(price[0:t+1])
            这里的min(price[0:t+1])就是"合法前缀的极值"。
        ③ 子区间信息互不干扰（独立）；
        ④ 合并阶段只需常数或线性时间。
    依据
      问题可以分解
        原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
      子问题是独立的
        子问题之间没有重叠，互不依赖，可以独立解决
      子问题的解可以合并
        原问题的解通过合并子问题的解得来
    分治不仅可以有效地解决算法问题，往往还可以提升算法效率
      操作数量优化
      并行计算优化
        适合
          归并排序
          快速排序
          基数排序
        不适合
          堆排序
          冒泡排序
          插入排序
          选择排序
    常见问题
      寻找最近点对
      大整数乘法
      矩阵乘法
      汉诺塔问题
      重建二叉树
      求解逆序对
      二分查找
      归并排序
      快速排序
      桶排序
      树
      堆
      哈希表
      时间复杂度为 O(logn) 的搜索算法通常是基于分治策略实现的
  字符串
    匹配问题
      暴力匹配
      Knuth-Morris-Pratt 算法
        字符串
          Text
          Pattern
            前缀
              字符串里不包含尾字母，包含首字母的全部子串
            后缀
              字符串里不包含首字母，包含尾字母的全部子串
        部分匹配表（Partial Match Table） = 前缀函数 = 失败函数
          “相同的前后缀”是指一个字符串的前缀（字符串开始的部分）和后缀（字符串末尾的部分）相同（而不是公共）的最长子串的长度。在KMP算法中，这个概念用于构建部分匹配表（也称为前缀函数或失败函数），它帮助算法在发生不匹配时知道模式字符串应该回退到哪个位置。
            对于模式字符串的每个位置，计算其最长相同前后缀的长度。
            这个长度表示在发生不匹配时，模式可以向右滑动多少位。
          举例
            a
              0
            aa
              1
            aab
              0
            aaba
              1
            aabaa
              2
            aabaaf
              0
        步骤
          从文本的第一个字符开始，逐个与模式的字符进行比较。
          如果字符匹配，继续比较下一个字符。
          如果字符不匹配，查看部分匹配表，确定模式应该向右滑动多少位。
          重复这个过程，直到模式完全匹配（构建next数组的完全匹配条件和text的完全匹配是不太一样的）或无法继续匹配。
      Boyer-Moore 算法
      Sunday 算法
  基本数据结构
    链表
      currentCursor.next = currentNode;
currentCursor = currentNode;
        要把第一反应要做的节点操作，留到最后操作
    二叉树
      遍历结构问题，最终会变成这四种遍历的一种，特别是遍历根节点的顺序
      类型
        进入查找二叉树的状态后，大部分递归操作都要返回一个 node，而且如果有必要 node 还要重新赋值-特别是删除操作
        连续性
        度为2
        完美二叉树（perfect binary tree）所有层的节点都被完全填满。
          若树的高度为 h，则节点总数为 2^(h+1) -1
          在中文社区中，完美二叉树常被称为满二叉树。
        完全二叉树（complete binary tree）仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充
        完满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点。
        平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过 1
        查找二叉树
          性质
            每个值只有一个node
          插入
            迭代法
              遍历到某个none，记录prev，用prev再比较一次插入
            递归法
              从某个节点（通常是根节点插入），然后再返回这个节点重新赋值，如果这个节点本来是null，此时就返回了一个值。也就是说递归的返回值起到了对 null 值的替换作用
          删除
            当待删除节点的度为 1时，将待删除节点替换为其子节点即可。
            当待删除节点的度为1时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树<根节点<右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点-实践中对于度为2的节点，只要右子树的最小节点就行了。
            删除的技巧
              用右子树的val代替当前 node 的 val
              在右子树里（换当前 node）里删除这个 val
                要记得重新给右子树赋值
                如果只是单纯删除，要搞清楚怎么给之前的父的左右赋值
                  要保留父
                  而且要根据父确定要替换的是左右孩子的哪一个
                  要用被删除的右子树来做这件事
              如果使用迭代法而不是简单递归，则需要引入一个 pre
      基本属性
        根节点（root node）：位于二叉树顶层的节点，没有父节点。
        叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
        边（edge）：连接两个节点的线段，即节点引用（指针）。
        节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
        节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
        二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
        节点的深度（depth）：从根节点到该节点所经过的边的数量。
          长边算法
            1 + Math.max(getDepth(node.left), getDepth(node.right))
          短边算法
            1 + Math.min(getDepth(node.left), getDepth(node.right))
        节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。
        请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下，高度和深度都需要加 1 -点比边多一，如果加一，depth 会变 level。
      遍历方法
        一圈一圈向外扩展
        计算高度经常需要使用的方案，所有“计算递归累积”、“递归包含某种性质”的行为都是这样计算的
        下降类的比较经常用的算法，dfs和递归都像
        查找类比较经常实用
        层序
          时间复杂度
            O(n)
              所有节点只被访问一次
          空间复杂度
            O(n)
              最多在队列里存在(n+1)/2个节点
        前序 中左右
          时间复杂度
          空间复杂度
        中序 左中右
          时间复杂度
          空间复杂度
        后序 左右中
          时间复杂度
          空间复杂度
        breadth first traversal。如果要转成递归的做法要引入层数的概念
        depth first search
          深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。
    堆
      属性
        结构连续
        最大最小属性
      用途
        优先级队列
        topK 问题
      实例
        PriorityQueue
          java 的优先级队列天然是最小堆，建最大堆要在构造器里选用一个反方向的比较函数
      节点指针通过索引映射公式来实现
        左子结点
          2i + 1
        右子结点
          2i + 2
        父节点
          (i - 1) / 2
      操作
        元素入堆
          我们首先将其添加到堆底
          因此需要修复从插入节点到根节点的路径上的各个节点
            自底向上 heapify
        堆顶出堆
          交换堆顶和堆底
          删除堆底
          修复堆顶
            自顶向下 heapify
        时间复杂度
          插入（Insert）
            O(logn)
          删除最大/最小元素（Extract-Max/Extract-Min）
            O(logn)
          增加/减少键值（Increase-Key/Decrease-Key）
            O(logn)
          查找最大/最小元素（Find-Max/Find-Min）
            O(1)
          构建堆（Build-Heap）
            O(n)
          堆排序（HeapSort）
            O(nlogn)
          合并两个堆（Merge）
            O(n+m)，其中 n 和 m 分别是两个堆的大小
          删除任意元素（Delete）
            O(logn)
    图 graph
      对比
        链表是线性关系
        二叉树是分治关系
        图是网络关系
          自由度最高，也最复杂
      分类
        方向
          无向图（undirected graph）
          有向图（directed graph）
            方向独立，一条边可以变两条边
        联通
          连通图（connected graph）
          非连通图（disconnected graph）
            在非连通图中，从某个顶点出发，至少有一个顶点无法到达。遍历非连通图需要设置多个起点，以遍历到图的所有连通分量。
        有没有权重
          有权图（weighted graph）
      概念定义
        邻接（adjacency）
          当两顶点之间存在边相连时，称这两顶点“邻接”
            顶点会产生其他邻接顶点
        路径（path）
          从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”
            路径可以有很多条
          路径被视为一个边序列，而不是一个顶点序列
        度（degree）
          一个顶点拥有的边数
            入度（in-degree）表示有多少条边指向该顶点
            出度（out-degree）表示有多少条边从该顶点指出。
      表达方式
        邻接矩阵 adjacency matrix
          以空间换时间
          设邻接矩阵为 M、顶点列表为 V，那么矩阵元素 M[i,j]=1表示顶点 V[i]到顶点 V[j]之间存在边；反之 M[i,j]=0表示两顶点之间无边。
          特性
            在简单图中，顶点不能与自身相连，此时邻接矩阵主对角线元素没有意义。
            对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
            将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。
          时间
            使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1)
            矩阵的空间复杂度为 O(n^2)
          操作
            初始化
              初始化 vertices
                O(n)
              初始化邻接矩阵
                O(n * n)
            添加顶点
              增加一行一列
                O(n)
            添加或删除边
              改格子
                O(1)
            删除顶点
              删除一行一列
                最差 O(n^2)
        邻接表 adjacency list
          以时间换空间
          特性
            邻接表仅存储实际存在的边，而边的总数通常远小于 n^2
            在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。
              比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 O(n) 优化至 O(lgn)
              还可以把链表转换为哈希表，从而将时间复杂度降至 O(1)
              “与该顶点相连的所有顶点”的顶点顺序是否有要求？
                可以是任意顺序。但在实际应用中，可能需要按照指定规则来排序，比如按照顶点添加的次序，或者按照顶点值大小的顺序等，这样有助于快速查找“带有某种极值”的顶点。
          操作
            遍历
              BFS
                由近及远、层层扩张
              DFS
                优先走到底、无路可走时再回溯
        顶点列表
      用例
        社交网络
          顶点
            用户
          边
            好友关系
          图计算问题
            潜在好友推荐
        地铁线路
          顶点
            站点
          边
            站点间的连通性
          图计算问题
            最短路线推荐
        太阳系
          顶点
            星体
          边
            星体间的万有引力作用
          图计算问题
            行星轨道计算
    数组
      通常基于数组实现的数据结构需要注意 capacity和 size 的比对问题，扩缩容完要切换底层数组；基于链表的不需要
    链表
      链表在某些场景下会造成内存碎片：频繁增删节点可能​​间接​​引发内存分配不均
    队列
      如果使用循环数组来实现入队和出队，则要注意 head 和 tail 不一定指向数组的头和尾，实现循环需要取模（可能还需要加上 capacity）
    Map
      哈希表
        真实的 index = hash(key) % capacity
          如果key是负数怎么办？
            取反？
              h = h & 0x7fffffff;
                这种反向取模非常重要
            增加大数？
          这个函数的复杂度是O(1)，哈希表的时间复杂度才是O(1)
        loadFactor = cnt/bucketCnt
          java hashmap 的 capacity 是桶的数量而不是元素的数量
          cnt 仍然是 kv的数量
          loadFactor 越高，时间复杂度越接近 O(n)，否则接近 O(1)
        哈希冲突处理方法
          separate chaining 链式地址法
            不容易产生哈希聚集
          open addressing 开放地址法
            线性探测
            平方探测
            多次哈希
            产生哈希聚集
        好的hashKey算法
          抗碰撞性
          雪崩效应
          确定性
          高效率
          均匀分布
            哈希算法通常采用大质数作为模数，以最大化地保证哈希值均匀分布，减少哈希冲突
              "大质数模数可减少因数据周期性分布导致的哈希冲突（如 key % 8在 key 为偶数时冲突率50%以上）"
        key
          一般能作 key 的对象是不可变的
          key 是无序的，不要依赖于特定顺序
            仅修改 value 不会影响遍历顺序
          不要在迭代中变更 key
      TreeMap
        时间复杂度经常是 O(logN)的
    所有的变化都至少要注意 size的变化，而且数组越界要注意抛异常和扩缩容 resize
  主方法
    大规模递归式的刻画方法，分治法的根本思想
      T(n) = aT(n/b) + f(n)
        a是子问题个数，b是子问题的规模系数，ab不一定相等，f(n)是合并结果的代价
        不含有n非常小的时候的精确刻画，但是误差不大
        有了主方法可以直接计算时间复杂度
          1. 情况1 (f(n) 增长较慢，是低阶项):
            如果存在常数ε > 0，使得f(n) = O(nlogba - ε)，则T(n) = Θ(nlogba)。
            例子
              Θ(log n)
                二分查找
          2. 情况2 (f(n) 与nlogba 具有相同增长速度):
            如果存在常数k ≥ 0，使得f(n) = Θ(nlogba * (log n)k)，则T(n) = Θ(nlogba * (log n)k+1)。
            为什么a T(n/b) 的时间复杂度是 Θ(n^{log_b a})
            例子
              Θ(n log n)
                归并排序
                快速排序（平均）
                堆排序 / 建堆
                最大子数组（分治）
          3. 情况3 (f(n) 增长较快):
            如果存在常数ε > 0，使得f(n) = Ω(nlogba + ε)，并且对于足够大的n，存在常数c < 1，使得a\*f(n/b) <= c\*f(n)，则T(n) = Θ(f(n))。
          例外
            0/1 背包 DFS（无记忆化）
              Θ(2^n)
              超出主方法范围
            回溯：n 皇后
              Θ(n!)
              阶乘级
            贪心：活动选择、Huffman
              直接 Θ(n log n)
              不适用主方法
            动态规划：LCS、LIS
              通常是 Θ(n²) 或 Θ(nk)
              不适用主方法
  语言操作
    初始化空数据结构的方法
      带长度
        int[] emptyArray = new int[5];
        emptySlice := make([]int, 5)
      不带长度
        int[] emptyIntArray = {};
        emptySlice := []int{}
        m := make(map[string]int) // 创建一个空的 map，键为 string 类型，值为 int 类型
        m := map[string]int{} // 创建一个空的 map
    从字符串里取字符的方法
      java
        String str = "Hello";
char ch = str.charAt(0); // 获取第1个字符 'H'
char lastChar = str.charAt(str.length() - 1); // 获取最后一个字符 'o'
        String str = "Hello";
char[] chars = str.toCharArray();
char firstChar = chars[0]; // 'H'
      go
        str := "Hello"
b := str[0] // 获取第1个字节，注意这是 byte 类型，不是 rune
        str := "Hello"
runes := []rune(str)
ch := runes[0] // 获取第1个字符作为 rune 类型
        str := "Hello"
for i, ch := range str {
if i == 0 {
fmt.Printf("第一个字符: %c\n", ch) // 'H'
break
}
}
  数组问题
    数组求和的基础是 twosum 的散列解法
      把差值作为 key 存储是逆用数据结构的设计
    要区分题设要求的索引和值之间的相等和不等关系
    Arrays.sort(nums);// leetcode允许直接先对数组排序，这一点容易被忘记
      确保数据是排序的，这样可以用相邻的比较跳过重复数据
        极易出错：新的元素要用新的起点
        数组排序可以说是不用hash表去重且要指针移动的时候必须要的方案
          往右移动时，相等元素都是相邻的。这意味着在某轮选择中，若当前元素与其左边元素相等，则说明它已经被选择过。
        如果涉及数学计算的结果组合而不是排序问题，都可以考虑排序
          子集和问题去重
    环形数组
      i = (i + 1) % arr.length; // 如果可能每个下标移动操作都要带上 mod 操作
      左闭右开
        [start, end)
          for (int i = 0; i < count; i++) {
newArr[i] = arr[(start + i) % size];
}
            arr = newArr;
// 重置 start 和 end 指针
start = 0;
end = count;
          // 因为 start 是闭区间，所以先左移，再赋值
start = (start - 1 + size) % size;
arr[start] = val;
          start = (start + 1) % size;
count--;
          start = end = 0 时，区间 [0, 0) 中没有元素，但只要让 end 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。
          加元素开头要记得扩容，删结尾要记得缩容
加法直接 mod，减法要加上size再 mod size，类似数字补码操作
    双指针法的复杂度本质
      想象你和朋友分别站在一条长度为 M 的绳子的两端。你们的目标是相遇或者找到绳子上的某些特殊点。
暴力法（类似三重循环）：你站在起点不动，让你朋友从终点走到起点，检查每个点。然后你移动到下一个点，你朋友再从终点走到起点检查每个点... 总共需要 M * M = M^2 次检查。
双指针法：你从起点开始向终点走，你朋友从终点开始向起点走。你们根据某种规则（比如比较你们所在位置数字的和与目标）决定谁下一步往哪边移动。你们每移动一步，搜索空间就缩小一部分。直到你们相遇或者找到目标。在这个过程中，你们两人总的移动步数最多就是 M 步（从两端走到中间）。这就是 O(M) 的由来。
双指针法通过利用数组有序的特性和问题本身的单调性（如果 b 增大，c 就得减小；反之亦然），使得两个指针以一种协调的方式朝着中间移动。两个指针的总移动步数被限制在整个子数组的长度范围内，而不是像嵌套循环那样是长度的平方。因此，对于每一次固定的外层元素，内层寻找另外两个数的操作时间复杂度是 O(N)（更准确地说是 O(M)，M 是子数组长度，但所有 M 加起来是 N 的量级），远优于朴素的 O(N^2) 嵌套循环。
      为了保持有序性，双指针的2/3层指针必须保持左右大小不相等，找到等值的时候就放弃
        while (i < j) {
while (i < j && nums[j] >= nums[left])
          这个 i < j 必须写两层，双层 while 必须如此
      每一层都必须去除重复元素
      双指针本身并不是只简单从反向存储那么简单而已，而是对于同一个i，j和k找到一对，另一对一定在更窄的区间内找到，所以双指针要并行，而不是嵌套移动
        找到一对指针以后，必须移动一次指针，然后再引入测试的指针移动，否则极易进入死循环!
          // 优化4：根据 sum 与 target 的关系移动指针
if (sum < target) {
left++; // 如果主动移动了这个指针，下面的移动就不需要有个 left != i +1
// 可选：跳过 left 的重复值 (对性能提升有限)
// while (left < right && nums[left] == nums[left - 1]) left++; // 如果打开这个注释，则一定要在这里加上 left < right，否则在这个循环里可能指针移动越界
} else { // sum > target
right--;
// 可选：跳过 right 的重复值 (对性能提升有限)
// while (left < right && nums[right] == nums[right + 1]) right--;
}
            对于每一个while循环，都要检查哪些是必须有的条件，比如这里的内部 while 仍然是需要 l < r 的条件的，因为移动了 l。
        如果指针移动条件过于复杂，也可能触发不移动左右指针的死循环
        这种缩窄是双指针法的单调性原理
      如果双指针是完全对位执行的，也可以用一个i，另一个是 n - 1 - i 的方式执行。如果指针的运行速度不一致，则需要引入双指针
    大数
      加
        用倒置字符串模拟数字
        用 char[] 来提高性能，而不是 String
          str.charAt(i) - '0'
          (char)(num + '0')
        要懂得进位，也懂得清除进位
          if (sum > 2) {
carry = 1;
sum %= 2;
}
        加起来以后要懂得再逆序
          允许使用 StringBuilder，可以直接 reverse() 和 toString()
          List<Integer> result = new ArrayList<>();
            // list 的优势，不需要处理超长的那一位，也就不需要计算数组长度，缺点是不能处理前导0问题
            Collections.reverse(result)
        在极端场景下要注意去掉前导0
        消耗掉全部指针
          int carry = 0;
while (i >= 0 || j >=0 || carry > 0) {
int result = carry;
if (i >= 0) {
result += num[i--];
}
if (j >= 0) {
result += kNum[j--];
}
carry = result/10;
int current = result % 10;
temp.add(current);
}
      减
        减法不同于加法的地方在于，如果要使用竖式减法，要求被减数要大于减数，这样常见的借位逻辑才能生效。
所以第一步是判断哪个数大，如果被减数小于减数，则交换减数，增加一个是否为 负数的 flag。
        最大的数组长度是被减数的 i，所以与加法不同，temp 数组不需要多准备一位。但是如果要解决前导0问题，仍然需要准备一个 temp 数组，逆序积攒减法的结果。
      步骤
        把大数放在前面，确定正负号
        准备前导0数组和i、j、k指针
        逆序用大数 - 借位 - 小数，赋给当前值 temp[k--]
          i、j、k要记得移动
          记得赋值完消耗掉借位
          如果本计算发生小数问题，要专门生成新的借位
        继续循环，直到 i、j 和借位都处理完为止
        在temp数组里寻找除了最后一位以外的前导0界线
        使用前导0界线按照顺序appen数据到sb里
        加上“-”
      乘
      除
  数论
  贪心
    sop
      画时间轴：明确哪些信息在哪个时刻可获得
      检查约束：是否存在不可逆的时间约束
      验证局部最优：在每个决策点，局部最优是否足够
      写出状态转移：如果状态简单且只依赖前缀，选贪心；否则选DP
    贪心选择性质
      “一步就能做出全局最优决策，而不必比较所有子问题的最优解