代码随想录通关小节
代码随想录通关小节
数组
数组是存放在连续内存空间上的相同类型数据的集合。
数组核心概念就是下标。
连续内存 + 相同类型，意味着我们可以根据 元素地址 = 数组首地址 + 类型单位长度 * 元素下标
查找数组的元素是通过元素下标来的，而我们就可以在下标上做文章，通过对于下标的计算来执行算法的逻辑。
二分法，指定两个下标 left 和 right ，并通过不断取二者中间下标的方式。
双指针法，数组中一种常见的方法，上文的二分法也可以说是一种双指针法，还有比如滑动窗口，双指针分别代表滑动窗口的开始和结束
前缀和，统计从一开始到当前元素之和作为新元素，可以通过相减方便地得出任意两个下标之间集合之和，说白了就是集散的积分。
链表
链表是由带数据和指针的节点通过指针串联而成的、内存非连续的线性数据结构。
链表核心概念有节点、指针，还有虚拟头节点（可选）。
链表有几种类型：单链表、双链表、循环链表（字面意思，就不解释了）
基本操作，增删节点，这对于链表来说是比较轻松的事，只需要修改指针即可
双指针法，也是链表中一种常见的方法，太好用了。
哈希表
哈希表是通过哈希函数将键映射到数组位置、以空间换时间实现高效存取的散列数据结构。
哈希表核心概念有键、值、映射。键 Key 是唯一的。这里有个极易混淆的点，这里所说的映射指的是 键（Key） 到 数组位置（下标）的映射，这个映射就是哈希函数，是通过计算实现的，而作为哈希表典型的 map 的 key-value 也有映射的说法，但是 map 的存储的是 key-value 键值对！不是单纯的 value！map 存储键值对的原理是拿到键值对之后将其中的键拿出来用哈希函数进行计算得到下标，从而找到其应该存放的位置，然后将键值对整个存放进去，当我们要用到这个键值对的时候，只需要知道它的键，就可以找到这个键值对，而我们取出了键值对之后只取用了其中的值，所以所谓键值的映射其实只是借助哈希函数的映射而已，并没有在键值之间真的建立了映射，真正的映射是键映射到下标。
哈希表可以快速判断一个元素是否在集合里。从这个延伸出去还可以解决是否循环的问题，因为如果循环的话表示有限个状态依次出现，一旦发现状态集合中某个状态再次出现，那么就完成闭环，开始循环。
哈希表从数据结构上来说就是一个数组，只是我们通过下标的计算赋予了逻辑，简单来说，我们通过一个函数（称为哈希函数）将一个键 Key 映射成哈希表的下标，然后将这个 Key 存入这个位置，而判断一个 Key 是否在哈希表中只需要用哈希函数计算得到一个下标，然后看看哈希表中这个下标对应的位置中有没有这个 Key 就可以了，这中方法不用枚举对比，效率极高。
哈希碰撞，在映射过程中，哈希函数可能将不同的值映射成同一个下标，这两个不同的值就“碰撞”了，这显然是一个问题，解决哈希碰撞一般有两种方法：拉链法和线性探测法
拉链法是将碰撞的数据组成一个链表，在一个下标的位置引申出去
线性探测法则是将碰撞的数据就近分散开存放，按照一定的规则放到附近的空位中
常见的哈希结构：数组、set（集合）、map（映射）
哈希表的底层存储结构是数组， HashMap 和 HashSet 都是 数组 + 链表/红黑树
map 无序且数据以键值对存储，set 无序且数据单独存储（实际上只是存了空值而已）
字符串
字符串是一串字符序列，或者说字符数组。
如果是用字符数组来承载字符串那么很多解法都和数组的各种解法有重合
而特定语言中会用特定的形式来表示字符串，会有一些额外的规则需要注意。
如果是 String 的话，需要考虑到其不可变的特性，并且封装了一些常见操作的方法，比如拼接、截取、反转（反转这里的话有个小技巧，整体反转+局部反转可以实现字符位置的回环拖动），不过要大概知道库函数的实现原理及其时间复杂度。
如果遇到需要可变的情况，那么就需要考虑用到 StringBuilder 和 StringBuffer
对于找字串的问题，有个 KMP 算法，利用前缀表进行回溯，提高查找效率，前缀表记录了最长公共前后缀
双指针法
双指针法是指用两个指针遍历数组 / 链表，协同移动实现高效运算。
双指针法作为一种常见技巧穿插在前文中。
栈与队列
栈是后进先出（LIFO）的线性数据结构，队列是先进先出（FIFO）的线性数据结构。
栈可以用来检查格式问题，比如括号闭合、逆波兰表达式
逆波兰表达式展开说说好了，逆波兰表达式中运算符在后，正常的算式是中缀表达式，而逆波兰表达式是后缀表达式。利用栈计算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。
二叉树
二叉树是每个节点最多有两个子树（左子树和右子树）的树结构。
二叉树的种类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树（AVL）
二叉树的存储方式：可以链式存储（指针），也可以顺序存储（数组）。二叉树用数组存储时可以方便地通过计算下标得出节点之间的父子关系——左子节点下标 = 当前节点下标 * 2 + 1、右子节点下标 = 当前节点下标 * 2 + 2
堆在逻辑上是一个父子节点大小关系单调的完全二叉树，通常用数组实现，插入时存入数组尾部，删除时一般删除数组首部，通过上升下沉维持堆结构。
二叉树的遍历方式：前/中/后/层序遍历。对于前/中/后序遍历来说，有递归和迭代两种方式，两种方式都有各自统一的写法，只需要稍加修改就可以转换前/中/后。对于层序遍历来说，也有递归和迭代两种方式，递归需要利用一个变量来表示当前深度，迭代则借助队列。
二叉树的题目大多数就是考察二叉树的遍历及题目特定的边界条件和计算。
回溯算法
回溯算法是一种通过递归尝试所有可能路径，在发现当前选择无法得到有效解时撤销上一步（回溯）并尝试其他选择的搜索算法。
从代码上来说是通过递归和栈来实现的。
贪心算法
贪心算法是一种在每一步选择中都采取当前状态下最优的选择（局部最优），以期最终得到全局最优解的算法。
贪心算法重要的是找到局部最优的策略，不过这种策略需要按照具体问题分析，一般依靠经验和直觉，做贪心就不要追求精密的数学推导了。
动态规划
动态规划是一种通过将复杂问题分解为重叠子问题、并存储子问题解以避免重复计算，从而高效求解最优化的算法思想。
此类题目关键是构造 dp table 和找到
单调栈
单调栈是一种维护栈内元素单调递增或递减的栈结构，通过及时弹出不符合单调性的元素，用于高效求解数组中每个元素左边/右边第一个更大/更小元素的位置或值。
用栈记录遍历过但是悬而未决的元素
可判断时即可出栈
图论
图论是研究图（由顶点和边组成的数据结构）及其算法（如遍历、最短路径、最小生成树、网络流等）的数学分支，用于建模和解决多对多关系中的优化与连通性问题。
深搜（栈实现，常用递归或显式栈），广搜（队列实现）