数组

二分查找

二分查找的精髓在于寻找循环不变量，可以理解为有固定的含义，在处理的过程中绝对不会改变的量

二分查找服务的对象必须是有序的

二分查找的解题步骤

确定循环不变量，一般是数组的左边界和右边界
确定循环结束的条件，根据循环不变量的不同会有所改变
确定处理的逻辑
- 什么时候边界会改变？
- 要查找的是什么？

双指针法

双指针法的精髓在于思考指针所表示的含义

通常有以下几种

一个指针用于遍历，另外一个指针用于收集遍历得到的数据，充当结果数组的边界
- 可以理解为，我们要从原来的数组中，剔除不符合要求的元素，保留符合要求的元素
- 不同的题目，对于双指针的操作并不相同，要根据不同的题目设计不同的逻辑
两个指针分别用于两种不同性质数组的划分
- 当划分为两个数组的时候，通常是解决合并的问题
- 要注意利用数组本身是有序的性质
- 不一定要从小到大，也可从大到小。

滑动窗口

滑动窗口的精髓在于窗口的性质和窗口边界的变化

滑动窗口的解题步骤

确定窗口内装载的是什么东西，有什么性质
思考一种恰当的数据结构去记录这种窗口内数据的性质
确定什么时候窗口要移动
确定我们需要得到什么

模拟

模拟的精髓在于模拟的过程

解题步骤：

思考模拟过程中需要用到的变量，模拟中的变量通常会不断的变化，把大模拟分为小模拟，思考模拟过程中的需要用到那些量，这些量之间有什么关系，尽可能的减少变量(用变量去确定其他变量)
思考模拟结束的条件

链表

链表的操作

增加节点
- 从头部增加
  - 引入一个新的节点，该节点的next指向当前头节点，替换当前数据结构的头节点，
- 从尾部增加
  - 遍历到当前链表的尾节点，引入一个新的节点，让尾节点指向这个新的节点
- 在中间插入
  - 遍历到要插入位置的前一个节点pre，记录下一个节点next，引入一个新的节点cur，让pre指向cur，cur指向next
删除节点
- 删除头节点
  - 让当前头节点变为头节点的下一个节点
- 删除其他节点
  - 遍历到待删除节点的前一个节点，记录下待删除节点的下一个节点，让前一个节点指向下一个节点
获取节点
- 依次遍历，知道获得当前节点、、

虚拟头节点

在做链表题目的时候，通常虚构出一个头节点指向真实的头节点，这样就可以我们方便去处理那些需要设计到头节点边界的问题了

反转链表

首先要思考链表反转的过程，链表反转实际上需要改变节点间的指向关系

假设有三个节点，pre cur next

本来是 pre -> cur -> next

我们需要变成 pre <- cur <- next

思考操作的顺序和细节

我们需要记录下每一个节点的前一个节点和后一个节点，注意对null的判断

操作的时候，要让cur先指向前一个节点，pre变成cur

cur变成next,next变成next的next

依次往复，就能完成链表的反转

双指针

比如遇到删除倒数第n个节点这种题目，可以用双指针，让双指针之间的距离保持不变，快指针遍历到链表尾巴，就可以找到倒数第n个节点，注意指针之间的距离通常要比n大1，我们要找到倒数n + 1个节点来删除倒数第n个节点

比如遇到寻找链表相交节点这道题，链表一旦相交，后面的节点都是一样的，要判断谁是长一些的，让长一些的链表和短一些的链表在相同的起点同时移动，如果相遇，就是相交节点

比如寻找环形链表的入环节点

首先快慢指针，快指针每次移动两次，慢指针每次移动一个，当两者相遇
快指针回到起点，两者每次都移动依次，再次相遇的节点就是入环节点

哈希表

当我们需要快速判断一个元素是否出现在集合里，就要使用哈希表

注意key value的选取

三数之和/四数之和

使用双指针配合哈希表来解决此类问题

先对数组排序

当为三数之和的时候

注意去重的逻辑是

i > 0 && nums[i] == nums[i - 1] countinue

while(left < right && nums[left] == nums[left + 1]) left++;

while(left < right && nums[right] == nums[right - 1]) right–;

当为四数之和的时候

注意去重的逻辑是

i > 0 && nums[i] == nums[i - 1] countinue

j > i + 1 && nums[j] == nums[j - 1] countinue

while(left < right && nums[left] == nums[left + 1]) left++;

while(left < right && nums[right] == nums[right - 1]) right–;

优化的部分

三数 : nums[i] > target && nums[i] > 0

四数: nums[i] + nums[j] > target && nums[i] + nums[j] > 0

之后的n数逻辑相同

二叉树

二叉树节点的深度：从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
二叉树节点的高度：从该节点到叶子节点的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始)
根节点的高度就是二叉树的最大深度