各种常用API 及概念
二叉树种类
完全二叉树
除了最后一层，每层节点都达到最大数量，同时缺少的节点只在右边
满二叉树
满了
二叉搜索树（二叉排序树，二叉查找树）（BST）
二叉排序树：可以为空树，或者是具备如下性质：
若它的左子树不空，则左子树上的所有结点的值均小于根节点的值；
若它的右子树不空，则右子树上的所有结点的值均大于根节点的值，
左右子树分别为二叉排序树。
平衡二叉树
它是一个空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。
字符串
String s = "abcdefg";
System.out.println(s.substring(1,3)); // 注意，substring 所有字母都是小写的
// 输出"bc"
长度：s.length()
StringBuilder sBuilder = new StringBuilder();
sBuilder.append("i");
sBuilder.length();
sBuilder.charAt(2);
sBuilder.setCharAt(1, 'Q');
char[] charArray = s.toCharArray();
String s = new String(charArray);
数字
Integer.MAX_VALUE;
Integer.MIN_VALUE;
队列
Queue
是一个先进先出的队列。如果使用队列的数据结构，那么在new 的时候就new 一个LinkedList 就好了。
PriorityQueue
是一个优先队列，使用它的时候，可以传入一个Comparator 对象来判断两个元素的顺序，如：
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
add 和offer 方法都是向queue 中添加一个元素，在容量已满的情况下，
add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false 。
Queue 中的poll() 方法的作用是 获取并移除队列的头部元素，如果队列为空，返回null
Stack.peek() 返回栈顶元素的值；Stack.pop() 返回栈顶元素的值，并删除栈顶元素的值
Deque
是双端队列（double ended queue）双端队列，继承了Queue，既可以当队列使用，也可以当栈使用
有两个类实现了Deque：LinkedList 和ArrayDeque，这两个类可以实现栈和队列的功能。推荐使用ArrayDeque。
堆
使用PriorityQueue，因为其本身为”优先队列“，所以可以实现”堆“的功能。其本身底层实现也是二叉堆。
数组
Arrays.sort(nums);
方法返回值为void，将传入的数组直接排好序
Arrays.sort(nums, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
Arrays.fill(nums, value);
给nums 数组填入数字value
List
对list 的排序：
Collections.sort(list, new Comparator<…>() {@Override int compare(..o1, … o2) {} });
删除list 中的某个元素，使用remove，参数是整型
可以传入下标，也可以传入对象。
对于一个List，其中存整型数字的，如果要按照元素删除，那么使用list.remove(Integer.valueOf(1));
list.set(下标，元素）
栈
Stack 是一个类。对比队列，Queue 是一个接口。
empty() 是否为空
peek() 查看栈顶部对象，但是不移除
pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象
push(ele) 入栈
search(ele) 返回对象在堆栈中的位置，1 是基数。后入的是1，先入的是最后的那个。找不到返回-1
字符串
字符串的长度：s.length();
组数的长度：nums.length;
变为字符数组：char[] charArray = s.toCharArray();
字符截断：String result = s.substring(begin, begin + length); 注意substring 第二个字母小写，然后取长度为3 的子串，length 就是3
集合
set.add()
set.addAll()
set.size()
Map
使用HashMap 的时候，其内部key 是无序的
还有一种map，会对内部key 进行排序，这种map 就是SortedMap，它是个接口，它的实现是TreeMap
算法题具体思路
二分查找
在二分查找模板模块中：
分成 [left..mid] 和 [mid + 1..right]，对于这种情况，其实就是像下面这种代码
if (nums[mid] > target) {
条件1 判断进入语句;
} else {
条件2 判断进入语句;
}
只有两个判断条件，没有num[mid] == target 的这种
针对这种情况，执行条件1 语句的时候，如果执行了right = mid 或者left = mid + 1
这样就直接mid = （left + right) / 2 就好了。这种while 循环条件是不需要+1 的，原因是
- 如果选择了右边那部分元素，其实left = mid + 1， left 是有变化的
- 如果选择了左边那部分元素，right = mid，选择范围也是有变化的，所以不会造成死循环
对于在计算mid = (left + right + 1)/2 的这种情况，其实是在剩最后两个元素的时候，是选择右边的还是左边的。
所以这种情况的情景是数组被分为：
[left, mid – 1] 和 [mid, right]，这样在剩最后两个的时候，就不会发生每次除以完事之后left 赋值为mid 之后没变化的情况了。
34 题
对于寻找数组中相同元素的第一个、最后一个元素下标的时候
找第一个，我们将数组分为两部分，小于targe 的那些，和大于等于target 的那些
小于的那些那就说明不符合条件要求，就剩下大于等于的那些了
public static int findFirst(int[] nums, int target) {
int left = 0, right = nums.length – 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[left] == target) {
return left;
} else {
return -1;
}
}
这里面的判断逻辑可以分为
- 当num[mid] < target，说明左边的都是小于target 的，那么我们就需要把left 换成mid + 1
- 然后剩下的left 就不用再操心了
找最后一个重复元素数组下标的时候，在nums[mid] == target 的时候，因为我们要找寻最后一个，所以还是需要摒弃左边的部分的，所以我们把数组分为两部分：大于的，和小于等于的。
对于大于的那些数字，都是不符合条件的，代码如下：
public static int findLast(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] > target) {
right = mid -1;
} else {
left = mid;
}
}
if (nums[left] == target) {
return left;
} else {
return -1;
}
}
为什么分成了那两组，举例来说，寻找重复数最末尾的那个，是分了两组：肯定不是的那组，和包含的那组。
比如说if (nums[mid] > target)，对于这个，它肯定不是符合条件的那组，所以果断抛弃。在符合条件那组去找。
当有重复的时候，就一直往右去缩小范围，仔细品，发现就是这样的。
分组就分为两组：包含target 的和不包含target 的
中心偏左的意思，就是如果有奇数个元素，那么(left + right) / 2 就是中心偏左
比如说7/2 等于3，就在3.5 左边
287 题
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间
这道题是利用数组的规则，数字是从1 到n，那么首先我们假设前几个数字中没有重复的，那么小于1 的数字有0 个；小于2 的数字有1 个。
所以我们针对数字进行二分。也就是对于1 到n，去中间mid，判断小于mid 的有几个，如果超过了mid 本身，那就证明重复数字在left 到mid 之间
public static int findDuplicate(int[] nums) {
// 对1 – n 这些数字做二分
// 所以第一个是1
**int left = 1;
// 所以最后一个是n（数组长度为n + 1，减去1 就是n）
**int right = nums.length – 1;
while (left < right) {
// count 用来统计和mid 对比的统计
**int count = 0;
int mid = (left + right) / 2;
// 每次找到一个mid 的时候，需要遍历一遍数组
**for (int i = 0; i < nums.length; i ++) {
if (nums[i] <= mid) {
count ++;
} else {
continue;
}
}
// 如果count 大于mid 数字字面量，说明重复数字在1 ~ mid 之间，所以rihgt = mid
**if (count > mid) {
right = mid;
} else {
// 否则就处理剩下的那部分
**left = mid + 1;
}
}
return left;
}
33 搜索旋转排序数组
二分法处理问题的时候，在处理left、right 重新赋值的操作的时候，要学会”舍弃一边“，把确定条件的那边处理完成之后，剩下的一遍直接转换left 与right 的值即可。
比如说对于这道题，首先就瞄准有序那端
378 有序矩阵中第k 小的元素
二分法的时候，有时候是针对下标索引进行二分，有时候是针对元素值进行二分。
对于这道题，就是针对元素值进行二分
利用了矩阵的性质，左上角元素值最小，右下角元素值最大
这道题就是对数组中的数据做二分，对数据进行二分，找到符合条件的值，得到即可确认。
public static int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int left = matrix[0][0];
int right = matrix[n – 1][n – 1];
while (left < right) {
// 在最小和最大的数字之间找寻某个数字，使其满足 “ 第k 小 “ 的要求
**int mid = (left + right) >> 1;
if (check(matrix, mid, k)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 这个函数的作用就是到matrix 中
public static boolean check(int[][] matrix, int mid, int k) {
int n = matrix.length;
int i = n – 1;
int j = 0;
// 统计小于等于mid 的数量
**int count = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= mid) {
count += i + 1;
j ++;
} else {
i –;
}
}
// 这里得判断小于等于mid 的数量和k 的关系，用来在二分的时候做边界转换
**return count >= k;
}
链表
前后连接关系可断开的判断标准：
在做链表，执行循环迭代的时候，可能不知道什么时候可以把前后关联的关系切断，我们只要确认，当下一个节点有变量名命名的时候就可以。
举例来说：
1 -> 2 -> 3 -> 4 -> 5
比如说设置 cur = 2，2和3 之间有个next 的关系，2.next = 3
当我们设置 nextNode = cur.next 的时候，这个时候就可以放心大胆地切断2 和3 之间的联系了
比如说我们可以2.next = 3.next，让2 的下一个指到4，即使2 和3 之间断开了关系，但是3 有名称，就可以立刻找到它
92 链表节点交换
在做92 题的时候，是需要在给定的范围内进行翻转。
在设计翻转的时候，比如说开始链表1 2 3 4 5 6
我们要在2 到4 之间翻转，那么每次循环的中间结果为：
1 3 2 4 5 6
1 4 3 2 5 6
在完成1 3 2 4 5 6 的过程中，需要1 指向3，3 指向2，2 指向4.
我们在写代码的时候，从倒着的顺序开始
代码如下：
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode pre = new ListNode(-1);
pre.next = head;
// 因为在从第一个元素就开始转换的时候，head 这个指针会被带到后面去，所以应该有个预先的dummy 值用来存储指针
ListNode returnPre = pre;
for (int i = 0; i < left – 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode pos;
for (int i = 0; i < right – left; i++) {
pos = cur.next;
cur.next = pos.next;
pos.next = pre.next;
pre.next = pos;
}
return returnPre.next;
}
25 k 个一组翻转链表
发现针对一个链表，存在三个结构的指标数据
第一个是对于指针本身的，比如说head、tail 这种；
第二个是对于head 和tail 之外的用来做指引的，比如说一个pre，pre.next = head
第三层东西就是最终返回的头结点，finalReturnedHead，在最开始就要设置上
滑动窗口
可以使用left right 双指针作为“窗口”， 也可以使用map 作为窗口。
树
如果是递归，那么在最开始要确定“终结条件”。
什么情况下能用迭代；什么情况下只能用递归
迭代模板
chen-tao.github.io/2017/01/27/…
递归、回溯、dfs、bfs 模板
递归
先递进，再回归——这就是「递归」
递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。
规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
使用递归的时候，必须满足的三个条件：
- 解决问题的时候，可以把一个问题转换成一个新问题。这个新问题的解决方法仍与原问题一样。
只不过是处理的对象从原对象变成了子对象。
这些被处理的对象是有规律的“增”或者“减”的。 - 可以通过转化过程，使问题得到解决。
- 必定要有一个明确的结束递归的条件，否则递归就会无止境地进行下去。
对于递归来说，一个很形象的例子就是计算阶乘。
f(3) =
3 * f(2)
3 * 2 * f(1)
3 * 2 * 1
3 * 2
6
整个处理流程就是先递进，再归一。
非常典型的一个例子就是104 题，求二叉树的最大深度。
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
我们就可以直接在纸上画一画，或者想这个过程。
求当前树的深度，就是求其深度最大的子树的告诉然后再加1
递归的模板：
void f()
{
if(符合边界条件)
{
///////
return;
}
//某种形式的调用
f();
}
dfs
DFS的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底。
DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。
广度优先搜索缺点，消耗大量内存，但是可以判断是否有最优解
深度优先搜索难以找到最优解，但是消耗内存小
Dfs & 回溯的区别
深度优先搜索适用于所有图。而回溯算法只适用于树结构。
任何解空间可以映射成树结构的问题，都可以使用回溯法。任何解空间不能映射成树结构的问题，都不可以使用回溯法。
————————————————————————————————————————————
回溯的关键不在于递归，而在于“状态”。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回退，此时需要把之前设置的状态撤销掉。
dfs 只是找某个或某些满足条件的东西而已，找到就返回，找不到拉倒，没状态啥事儿。
————————————————————————————————————————————
回溯
解决一个回溯问题，实际上就是一个决策树的遍历过程。需要考虑三个问题：
- 路径（已经做出的选择）
- 选择列表（当前可以做的选择）
- 结束条件（到达决策树底层，无法再做选择的条件）就是结束条件
result = []
Def backtrack(路径，选择列表):
if 满足条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径，选择列表)
撤销选择
——————
Union-find （并查集 -> 合并union 查find）
——————
并查集算法是解决动态连通性(dynamic conectivity)的一种算法。
动态连通性是计算机图论中的一种数据结构。
简单来说就是：
- 图中各个节点是否相连
- 如何将两个节点相连
- 连接后有多少个连通分量
二叉树
为什么要撤销
private int height = 0; private int maxHeight = 0; void traverse(TreeNode root) { if(root == null) { maxHeight = Math.max(maxHeight, height); return; //结束遍历 }
height++; // 选择 traverse(root.left); traverse(root.right); height–; // 撤销选择 }
撤销是在后续遍历的位置
后序遍历的位置是啥意思呢
void traverse(TreeNode root) { if(root == null) { return; }
// 前序位置 traverse(root.left); // 中序位置 traverse(root.right); // 后续位置 }
对于递归 你就想这个这个递归方法的作用是什么 比如求高度
int depth(TreeNode node)
{
if(node == null) {
return 0;
}
return Math.max(depth(node.left),depth(node.right)) + 1;
}
回溯其实是有规律的穷举 回溯的过程其实就是在遍历一个多叉树
前序遍历的位置的代码 执行的时机是在刚进入这个节点 中序遍历的位置的代码 执行的时机是这个节点左边都处理完了 即将去处理这个节点右边的时候执行 后续遍历的位置的代码 是左右都处理完了 即将离开这个节点的时候执行
那么进入一个节点的时候 说明高度需要加一 后续从这个节点出去的时候（ 二叉树从一个节点出去的时候只能是往上走）高度肯定要减1
回溯其实是在遍历n叉数 在前序位置做选择 在后续位置撤销
