1.冒泡排序
从头开始，不断的比较相邻的两个数，小的放前边，大的放后边，一次比较之后，最大的数字会出现在数组的尾端；不断重复这个过程，直到排序完成
细节问题：外层循环表示完成排序需要进行的次数，数组长度为n,就需要n-1次，因为每次都会得到一个最大的，那么假如数列长度为10，那么9次排序之后，有9个最大的数字已经被筛选出来，那么最后一次不需要再做比较，一定是最小的；内层循环控制每次排序需要比较的次数，数组长度为n,则需要比较n-1次，这是-1的原因;每次比较完成之后，最大的数字已经排在尾端，所以下一次比较会新增一个不需要参与比较的数字，这就是-i的原因
特点：稳定；平均时间复杂度O(n2)，最坏时间复杂度O(n2)，最佳时间复杂度O(n),空间复杂度O(1)
冒泡排序.gif
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2.选择排序
冒泡排序第一次排序完成之后，会得到最大的数字，而选择排序是第一次排序之后，得到最小的数字。顾名思义，选择排序就是从未排序的序列中选择出最小（或最大，这里以从小到大排序为例说明）的数字放在数组的首位，不断的重复这个过程，直到排序完成,既然是选择最小的数字，那么一定有一个记录本次比较最小值的操作
细节问题：外层循环同样是控制需要进行的次数，长度为n,需要进行n-1次；内层循环控制每次需要比较的次数，选择排序每进行一层比较，就会得到一个最小的数字，放在最左边，那么这个得到的最小的数字就不需要再参与比较，所以j=i+1,内层循环每循环一次，就能得到这个数列中最小的元素的index，如果它比本次比较的起始位置（当前i位置）的值小，则交换即可。
特点：不稳定（数列中有相同元素的情况下，如a = b,a本来在b的前边，但是排序之后，二者的位置可能被交换）；平均时间复杂度O(n2)，最坏时间复杂度O(n2)，最佳时间复杂度O(n2),空间复杂度O(1)
选择排序.gif
public static void selectSort(int[] arr) {
int minIndex,temp;
for (int i = 0; i < arr.length - 1; i++) {
minIndex = I;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
3.简单插入排序
工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。
插入排序.gif
public static void insertSort(int[] arr) {
int current,preIndex;
for (int i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[I];
while (preIndex >= 0 && arr[preIndex] > current){
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
}
3.堆排序
参考：https://www.jianshu.com/p/938789fde325
堆排序的堆并不是java内存的堆的概念，它依托于一个完全二叉树的结构来实现排序，首先将数列调整成一个大顶堆（还有称为大根堆的）或者小顶堆（小根堆），以大顶堆为例(父节点中的元素不小于任意子节点的元素这种情形。所以，在一个大顶堆中，一个节点的元素在其子树所有元素组成的集合中必定是最大值)，调整完成之后，最大的数字是这个完全二叉树的根节点，接下来把这个最大的值和完全二叉树的最后一个节点交换，交换之后可能会破坏大顶堆的结构(父节点中的元素不小于（不大于）任意子节点的元素)，所以交换之后需要同时再次调整大顶堆，重复这个操作直到排序完成
什么是完全二叉树？ 如 [2,4,1,3,8,6,9]形成一个完全二叉树
截屏2021-08-22 上午10.24.05.png
关键点：
1.当我们知道某一数字在数组中的索引后，就可以计算出二叉树中该数字的左右子节点的索引，或者父节点在数组中的索引。以数字4为例，它的数组表示为A[1],根据二叉树特点，其父节点为2，即A[0];同时其左节点为3，右节点为8，分别对应A[3],A[4]，可得出一个结论，A[i]的左节点为A[2i+1],右节点为A[2i+2]，父节点为A[i/2]。
2.开始位置(从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1（完全二叉树），从左至右，从下至上进行调整。)
堆排序过程.gif
public static void heap(int[] arr, int size, int index) {
//左子节点的index（完全二叉树）
//A[i]的左节点为A[2i+1],右节点为A[2i+2]，父节点为A[i/2]
int leftNode = 2 * index + 1;
//右子节点的index
int rightNode = 2 * index + 2;
//设置最大值
int max = index;
//进行和左子节点比较
if (leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
//和右子节点比较
if (rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
//找到最大的节点之后就替换
if (max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
//然后如果还有的话就继续替换
heap(arr, size, max);
}
}
public static int [] heapSort(int [] arr){
//开始位置(从最后一个非叶子结点开始（叶结点自然不用调整，第一个非
//叶子结点 arr.length/2-1（完全二叉树），从左至右，从下至上进行调整。)
int start = (arr.length) / 2 - 1;
//1.得到一个大顶堆
for (int i = start; i >= 0; i--) {
heap(arr, arr.length, i);
}
//2.根结点和尾节点交换，并再次调整维持大顶堆
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//每交换一次之后，最大的值已经到了堆的最后一个节点，所以这个
//最大值不需要再参与排序，所以heap第二个参数size = i
heap(arr, i, 0);
}
return arr;
}
总体复杂度为O(n*log n)
3.top-k排序
1.整体排序
将n个数排序之后，取出最大的k个
2.局部排序
只对最大的k个排序，冒泡排序冒泡k次，就会得到前k个最大元素
3.堆
a.只找到TopK，省去了排序过程，先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。
b.接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。
c.直到扫描完所有n-k个元素，最终堆中的k个元素，就是TopK
快速排序
快速排序是由冒泡排序改进而得到的，是一种分区交换排序方法。思想如下：
一趟快速排序采用从两头向中间扫描的方法，同时交换与基准记录逆序的记录。
1.在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准，称为基准记录；
2.定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
3.首先，尾索引向前扫描，直到找到比基准值小的记录(left != righ)，并替换首索引对应的值；
4.然后，首索引向后扫描，直到找到比基准值大于的记录(left != righ)，并替换尾索引对应的值；
5.若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束；将基准值(key)替换首索引所对应的值；
6.再进行下一趟排序时，待排序列被分成两个区:[0,left-1],[righ+1,end]
7.对每一个分区重复步骤2~6，直到所有分区中的记录都有序，排序成功。
快速排序最好时间复杂度为nlogn,最坏时间复杂度为n的平方,平均时间复杂度为nlogn
快速排序1.jpg
快速排序2.jpg
快速排序3.jpg
快速排序4.jpg
快速排序5.jpg
快速排序6.jpg
快速排序7.jpg
快速排序8.jpg
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
}
int left = leftIndex;
int right = rightIndex;
//待排序的第一个元素作为基准值
int key = arr[leftIndex];
//从左右两边交替扫描，直到left = right
while (left < right) {
while (left < right && arr[right] >= key) {
//从右往左扫描，找到第一个比基准值小的元素
right--;
}
while (left < right && arr[left] <= key) {
//从左往右扫描，找到第一个比基准值大的元素
left++;
}
if (left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//基准值归位
arr[leftIndex] = arr[left];
arr[left] = key;
//对基准值左边的元素进行递归排序
quickSort(arr, leftIndex, left - 1);
//对基准值右边的元素进行递归排序。
quickSort(arr, right + 1, rightIndex);
}
4,二分查找
一般二分查找
public static int binarySearch(int arr[], int num) {
int left = 0;
int right = arr.length - 1;
//等号必须加，不然部分情况无法搜索到结果
while (left <= right) {
// 等同于(left+ right) /2 只是可以避免溢出
int center = left + (right - left) / 2;
if (arr[center] > num) {
right = center - 1;
} else if (arr[center] < num) {
left = center + 1;
} else {
return center;
}
}
return -1;
}
左边界二分查找
static int leftBoundBinarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length-1; // 注意
//while的条件不能是<= ,比如当前left = 3， right = 4，那么mid = 3，
// 更新right = 3，然后满足while，并且mid = 3，更新right = 3，就会死循环
while (left < right) { // 注意
int center = left + (right - left) / 2;
if (nums[center] == target) {
//如果找到相等的，继续向左查找，这里right必须设置为等于，
// 以防止如果没有左边界，还能返回当前找到的值
right = center;
} else if (nums[center] < target) {
//已经不想等了，就没有必要下次参与查找了
left = center + 1;
} else if (nums[center] > target) {
//已经不想等了，就没有必要下次参与查找了
right = center-1;
}
}
return left;
}
右边界二分查找
static int rightBoundBinarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// +1 其实是上取整，避免最后left 和right对应值相等且等于target，这样center还是等于left，然后判断赋值left = center ，这样就死循环了
int center = left + (right - left + 1) / 2;
if (arr[center] > target) {
right = center - 1;
} else if (arr[center] < target) {
left = center + 1;
} else {
left = center;
}
}
return left;
}
二分查找变形
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
public static int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left+(right-left)/2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
由于x 平方根的整数部分ans 是满足k的平方≤x 的最大值，因此我们可以对k 进行二分查找，从而得到答案。
找到最后一个满足a的平方小于等于x的情况下，a的值，和上边的二分查找变形，找插入位置刚好相反
int left = 0;
int right = x;
while(left <= right){
int middle = (right - left) / 2 + left;
if((long)middle*middle < x){
left = middle+1;
}else if((long)middle * middle > x){
right = middle - 1;
}else{
return middle;
}
}
return right;
5.数组类
1.删除有序数组中的重复项（小米）
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。注意关键词有序，因为有序，所以重复的元素一定是紧挨着的
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
例如：输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
思路：定义两个指针fast 和slow，分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标1，假设数组nums 的长度为n。将快指针fast 依次遍历从1到n−1 的每个位置，对于每个位置，如果nums[fast]≠nums[fast−1]，说明nums[fast] 和之前的元素都不同，因此将nums[fast] 的值复制到nums[slow]，然后将slow的值加1，即指向下一个位置，遍历结束之后，从 nums[0] 到 nums[slow−1]的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为slow，返回slow 即可。
删除元素.png
public static int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int fast=1,slow = 1;
while(fast < nums.length){
if (nums[fast] != nums[fast - 1]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
2.找出数组中任意一个重复的数字（小米）
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
这道题看起来很简单，直接用个集合存一下，有重复的就反回，但是假如不准使用其他数据结构，对空间复杂度要求为O(1)的时候就不行了
参考选择排序的方式来解(快慢指针解法)：
public static int findRepeatNumber2(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[I];
}
}
}
return -1;
}
变形一下：
public static int findRepeatNumber3(int[] nums) {
int i = 0;
while (i < nums.length) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[j];
}
}
I++;
}
return 0;
}
3. 0～n-1中缺失的数字（Google，Tencent）
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
注意是有序的
如果没有任何一个缺失的数字，那么这个数组应该是这样的：
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
......
arr[n-1] = n-1;
也就是说，数组下标和数组值相同，但是缺了一个，那么一定从某一个index开始，index != value。这种题的解法看起来很简单，直接遍历，找到这个index和value不想等的数字返回，不过还有更好的解法-二分查找（有序数组，又是要找某个数，就要想到二分查找）
public static int findLostNum(int[] nums) {
int start = 0;
int end = nums.length - 1;
while(start < end){
int middle = (end - start) / 2 + start;
if(nums[middle] > middle){
end = middle;
}else{
start = middle + 1;
}
}
// 当左边界与右边界相等时，可能已经指向该缺失的数字，但是还有一种可能是缺失的数字就在最后一个数组的后边
// 即[0,1,2]，缺少3，长度为3，即n=4，数的范围0~3
return start == nums[start]?start+1:start;
4.给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。 要求：空间复杂度O(1)，时间复杂度为O（n）
注意：空间复杂度要求为O(1)，那么就不能使用额外的数据结构，只能直接来操作这个数组，这里还是用双指针法来处理。既然奇数在左，偶数在右，那么定义两个指针，一个从左往右，一个从右往左（可以看作二分查找的变形）,从左往右找到第一个偶数，从右往左找到第一个奇数，交换两个数字的位置，然后重复上边的步骤
public static int[] reSortArray(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 != 0) {
left++;
}
while (left < right && nums[right] % 2 == 0) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
6.链表类
1.反转单链表(小米/美团/快手)
a.非递归方法：
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路：在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
反转单链表-1.png
反转单链表-2.png
反转单链表-3.png
反转单链表-4.png
反转单链表-5.png
public class Node {
int value;
Node next;
Node(int x) {
value = x;
}
}
public static Node reverseList(Node head) {
Node cur = head, pre = null;
while (cur != null) {
Node tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
b.递归方法：
public static Node reverseList2(Node head) {
return recur(head, null); // 调用递归并返回
}
private static Node recur(Node cur, Node pre) {
if (cur == null) return pre; // 终止条件
Node res = recur(cur.next, cur); // 递归后继节点
cur.next = pre; // 修改节点引用指向
return res; // 返回反转链表的头节点
}
2.链表的中间结点(中国平安)
给定一个头结点为 head 的非空单链表，返回链表的中间结点,如果有两个中间结点，则返回第二个中间结点。
快慢指针.png
public static Node getMiddleNode(Node head) {
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
3.如何检测一个链表是否有环（优酷腾讯滴滴）
A -> B -> C -> D -> E -> A这样的链表表示有环，链表的头节点和链表的尾节点相连；或者另一种情况，链表并非首尾相连，而是尾节点指向了中间某节点A -> B -> C -> D -> E -> C, 这样也表示这个链表有环
思路：设置一个快指针fast，一个慢指针slow，二者初始都指向链表头，fast一次走两步，slow一次走一步，两个指针同时向前移动，每移动一次，两个指针都要进行比较，如果快指针等于慢指针，则证明这是个有环的单链表。
如果是有环的链表，那么这个链表就没有尾部， while (fast != null && fast.next != null) 会一直成立，直到找到两个值相同的节点；如果没有环，那么当fast节点到达尾端的时候就会跳出循环，恰恰证明了这个链表没有环
public static boolean isLoop(Node head) {
boolean flag = false;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast.value == slow.value) {
flag = true;
break;
}
}
return flag;
}
4.相交链表（华为）
给你两个单链表的头节点 headA和headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null 。
公共节点.png
思路：
设第一个公共节点为 node ，链表 headA的节点数量为
a ，链表 headB的节点数量为b ，两链表的公共尾部的节点数量为c ，则有
头节点 headA 到 node 前，共有a−c 个节点
头节点 headB 到 node 前，共有b−c 个节点
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA ,headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为b+(a−c)
此时指针 A , B 重合，并有两种情况
a+(b−c)=b+(a−c)
若两链表有公共尾部 (即 c>0 ) ：指针A , B同时指向第一个公共节点node
若两链表无公共尾部 (即c=0 ) ：指针 A , B 同时指向null
public static Node getIntersectionNode(Node headA, Node headB) {
if (headA == null || headB == null) {
return null;
}
Node first = headA;
Node second = headB;
while (first != second) {
first = first == null ? headB : first.next;
second = second == null ? headA : second.next;
}
return first;
}
5.链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.
倒数节点.gif
public Node getNodeEnd(Node head, int k) {
Node former = head, latter = head;
for (int i = 0; i < k; I++)
former = former.next;
while (former != null) {
former = former.next;
latter = latter.next;
}
return latter;
}
时间复杂度O(N) ：N 为链表长度；总体看， former 走了N 步， latter 走了(N−k) 步。
空间复杂度O(1) ： 双指针 former , latter 使用常数大小的额外空间。
6.两数相加（今日头条，美团）
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头
如：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
两链表相加.png
public Node addTwoNumbers(Node l1, Node l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.value);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.value);
l2 = l2.next;
}
int carry = 0;
Node head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty() ? 0 : stack1.pop();
sum += stack2.isEmpty() ? 0 : stack2.pop();
//构建一个节点
Node node = new Node(sum % 10);
//头插法中，第一个构建的节点作为最终的尾节点，尾节点
//的next指向null，head指向null，新建的节点也指向null
node.next = head;
//移动head节点指向当前创建的节点，作为头节点，下一次循环
//新建的节点仍会被作为新节点的next节点，就这样不停的移动head指针
head = node;
carry = sum / 10;
}
return head;
}
时间复杂度：O(max(m,n))，其中m 和n 分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要
O(1) 的时间。
空间复杂度：O(m+n)，其中m 和n 分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间。
变形
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
7.队列，堆栈
1.用两个栈实现队列
根据栈先进后出的特性，我们每次往第一个栈里插入元素后，第一个栈的底部元素是最后插入的元素，第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性，我们引入第二个栈，用第二个栈维护待删除的元素，在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。
两个栈实现队列.gif
public class TwoStackQueue {
private final Stack<Integer> stackPush;
private final Stack<Integer> stackPop;
public TwoStackQueue() {
stackPush = new Stack();
stackPop = new Stack();
}
public void addTail(int num) {
stackPush.push(num);
}
public int removeHead() {
if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
8.二叉树
1.前序遍历
递归
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
迭代
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
List<Integer> list = new ArrayList();
while(root != null || !stack.isEmpty()){
while(root != null){
list.add(root.val);
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
root = node.right;
}
return list;
}
2.中序遍历
递归
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.value + " ");
preOrderRecur(head.right);
}
迭代
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
List<Integer> list = new ArrayList();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
list.add(node.val);
root = node.right;
}
return list;
}
3.后序遍历
递归
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
迭代
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList();
LinkedList<TreeNode> stack = new LinkedList();
TreeNode pre = null;
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
if(node.right == null || node.right == pre){
list.add(node.val);
pre = node;
root = null;
}else{
stack.push(node);
root = node.right;
}
}
return list;
}
4.检查子树(爱奇艺)
检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
示例1:
输入：t1 = [1, 2, 3], t2 = [2]
输出：true
示例2:
输入：t1 = [1, null, 2, 4], t2 = [3, 2]
输出：false
public boolean checkSubTree(TreeNode n1, TreeNode n2) {
if (n2 == null) {
return true;
}
if (n1 == null) {
return false;
}
return isEquals(n1, n2) || checkSubTree(n1.left, n2) || checkSubTree(n1.right, n2);
}
private boolean isEquals(TreeNode n1, TreeNode n2) {
if (n1 == n2) {
return true;
}
if (n1 == null || n2 == null) {
return false;
}
return n1.value == n2.value && isEquals(n1.left, n2.left) && isEquals(n1.right, n2.right);
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
时间复杂度分析：最差情况下,t1在小于t2子树高度以上节点都要比对M次，M是t2节点的大小，所以时间复杂度为O（N*M）
变形：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
如果同时满足下面的条件，两个树互为镜像：
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称
我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和q 指针一开始都指向这棵树的根，随后p 右移时,q 左移，p 左移时,q 右移。每次检查当前p 和q 节点的值是否相等，如果相等再判断左右子树是否对称。
public boolean isSymmetric(TreeNode root) {
TreeNode left = root;
TreeNode right = root;
return check(left,right);
}
public boolean check(TreeNode left,TreeNode right){
if(left == null && right == null){
return true;
}
if(left == null || right == null){
return false;
}
return left.val == right.val && check(left.left,right.right) && check(left.right, right.left);
}
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
如果我们知道了左子树和右子树的最大深度l 和r，那么该二叉树的最大深度即max(l,r)+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}else{
int leftMaxLength = maxDepth(root.left);
int rightMaxLength = maxDepth(root.right);
return Math.max(leftMaxLength,rightMaxLength)+1;
}
}
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
选择中间位置左边的数字作为根节点
public TreeNode sortedArrayToBST(int[] nums) {
return transferArrayToTree(nums,0,nums.length - 1);
}
public TreeNode transferArrayToTree(int[] nums,int left,int right){
if(left > right){
return null;
}
int mid = (left + right)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = transferArrayToTree(nums,left,mid - 1);
node.right = transferArrayToTree(nums,mid+1,right);
return node;
}
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
将给定的有序链表转换为二叉搜索树的第一步是确定根节点,如何找出这样的一个根节点呢？我们可以找出链表元素的中位数作为根节点的值.找出链表中位数节点的方法多种多样，其中较为简单的一种是快慢指针法
class Solution {
public TreeNode sortedListToBST(ListNode head) {
ListNode h = head;
ListNode t = null;
return linkListToTree(h,t);
}
public TreeNode linkListToTree(ListNode left,ListNode right){
if(left == right){
return null;
}
ListNode mid = getMidleNode(left,right);
TreeNode node = new TreeNode(mid.val);
node.left = linkListToTree(left,mid);
node.right = linkListToTree(mid.next,right);
return node;
}
public ListNode getMidleNode(ListNode left,ListNode right){
ListNode fast = left;
ListNode slow = left;
//注意这里比较关键，不能通过fast != null && fast.next != null 判断
while(fast != right && fast.next != right){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
给你二叉树的根结点 root ，将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
1
/ \
2 5
/ \ \
3 4 6
//将 1 的左子树插入到右子树的地方
1
\
2 5
/ \ \
3 4 6
//将原来的右子树接到左子树的最右边节点
1
\
2
/ \
3 4
\
5
\
6
//将 2 的左子树插入到右子树的地方
1
\
2
\
3 4
\
5
\
6
//将原来的右子树接到左子树的最右边节点
1
\
2
\
3
\
4
\
5
\
6
......
public void flatten(TreeNode root) {
while(root != null){
if(root.left == null){
root = root.right;
}else{
TreeNode temp = root.left;
while(temp.right != null){
temp = temp.right;
}
temp.right = root.right;
root.right = root.left;
root.left = null;
root = root.right;
}
}
}
5.二叉树的序列化和反序列化
可以先序遍历这颗二叉树，遇到空子树的时候序列化成 NULL，否则继续递归序列化。那么我们如何反序列化呢？首先我们需要把原先的序列分割开来得到先序遍历的元素列表，然后从左向右遍历这个序列：
如果当前的元素为 NULL，则当前为空树
否则先解析这棵树的左子树，再解析它的右子树
public static String serialize(TreeNode node) {
return serialize2(node, "");
}
public static String serialize2(TreeNode node, String str) {
if (node == null) {
str += "NULL,";
} else {
str += node.value + ",";
str = serialize2(node.left, str);
str = serialize2(node.right, str);
}
return str;
}
public static TreeNode deserialize(String str) {
String[] split = str.split(",");
List<String> list = new LinkedList<>(Arrays.asList(split));
return deserialize2(list);
}
public static TreeNode deserialize2(List<String> list) {
if ("NULL".equals(list.get(0))) {
list.remove(0);
return null;
}
String s = list.get(0);
TreeNode node = new TreeNode(Integer.parseInt(s));
list.remove(0);
node.left = deserialize2(list);
node.right = deserialize2(list);
return node;
}
时间复杂度：在序列化和反序列化函数中，我们只访问每个节点一次，因此时间复杂度为O(n)，其中n 是节点数，即树的大小。
空间复杂度：在序列化和反序列化函数中，我们递归会使用栈空间，故渐进空间复杂度为O(n)。
给定一个字符串，请你找出其中不含有重复字符的最长字串的长度（字节跳动）
我们不妨以abcabcbb为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
以(a)bcabcbb 开始的最长字符串为(abc)abcbb；
以a(b)cabcbb 开始的最长字符串为a(bca)bcbb
以ab(c)abcbb 开始的最长字符串为ab(cab)cbb
以abc(a)bcbb 开始的最长字符串为abc(abc)bb；
以abca(b)cbb 开始的最长字符串为abca(bc)bb
以abcab(c)bb开始的最长字符串为abcab(cb)b；
以abcabc(b)b开始的最长字符串为abcabc(b)b
以abcabcb(b) 开始的最长字符串为abcabcb(b)。
发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1 个字符作为起始位置时，首先从k+1到rk
的字符显然是不重复的，并且由于少了原本的第k 个字符，我们可以尝试继续增大人rk，直到右侧出现了重复字符为止。
这样一来，我们就可以使用「滑动窗口」来解决这个问题了：
我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中枚举子串的起始位置，而右指针即为上文中的rk;在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
在循环结束后，我们找到的最长的子串的长度即为答案。
public static int lengthOfLongestSubstring(String s) {
int left = 0;
HashSet<Character> set = new HashSet();
int max = 0;
for(int i = 0; i < s.length();i++){
if(i != 0){
set.remove(s.charAt(i - 1));
}
while(left < s.length() && !set.contains(s.charAt(left))){
set.add(s.charAt(left));
left++;
}
max = Math.max(max,left-i);
}
return max;
}
7.反转字符串中的单词
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
public static String reverseWords(String s) {
int start = 0;
int length = s.length();
StringBuilder builder = new StringBuilder();
while(start < length){
int lastStart = start;
while(start < length && s.charAt(start) != ' '){
start++;
}
for(int i = start -1 ; i >=lastStart;i--){
builder.append(s.charAt(i));
}
while(start < length && s.charAt(start) == ' '){
builder.append(' ');
start++;
}
}
return builder.toString();
}
时间复杂度,O(N)，其中N 为字符串的长度。原字符串中的每个字符都会在O(1) 的时间内放入新字符串中。
空间复杂度,O(N)。我们开辟了与原字符串等大的空间。
8.动态规划
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 temp
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 temp的大小，将最大值置为temp，遍历结束返回结果
时间复杂度:O(n)
public int maxSubArray(int[] nums) {
//优化空间前
// int arr[] = new int[nums.length];
// arr[0] = nums[0];
// int max = nums[0];
// for(int i = 1; i < nums.length; i++){
// if(arr[i - 1] > 0){
// arr[i] = arr[i - 1] + nums[i];
// }else{
// arr[i] = nums[i];
// }
// max = Math.max(max,arr[i]);
// }
// return max;
//优化空间后
int pre = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
pre = Math.max(pre + nums[i],nums[i]);
max = Math.max(pre,max);
}
return max;
9.汉诺塔问题
1.只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。
2.当A塔上有两个盘子是，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。
3.当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。
4.当A塔上有n个盘子是，先将A塔上编号1至n-1的盘子（共n-1个）移动到B塔上（借助C塔），然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。
5.综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况均一样（只是事件的复杂程度不一样）。
发现：
中间的一步是把最大的一个盘子由A移到C上去；
中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；
public static void hannoi(int n, char A, char B, char C) {
if (n == 1) {
move(n, A, C);
} else {
hannoi(n - 1, A, C, B);
move(n, A, C);
hannoi(n - 1, B, A, C);
}
}
private static void move(int n, char a, char c) {
System.out.println("把" + n + "从" + a + "移动到" + c);
}
网友评论