本文共 13120 字，大约阅读时间需要 43 分钟。

写在前面，许多问题并不只有一种解答思路

一. 数据结构

1. 栈

1.1 栈

• 简单

• 中等

• 困难

1.2 单调栈

单调栈问题有2大特点：（1）涉及到元素的比较（从小到大？字典序小？）（2）保持原有的相对顺序

保持栈中元素从大到小排列：

for () {   	int cur = //当前元素    while(!stack.isEmpty() && cur > stack.peek()) {    // 当前元素大于栈顶元素        stack.pop(); // 出栈            }    stack.push(i); //入栈}

• 简单
• 中等
• 困难

2. 链表

基本结构：

public class ListNode {   	public int val;    public ListNode next;    public ListNode() {   	}    public ListNode(int x) {        	val = x;     }}

基本操作：

• 插入

temp = 待插入位置的前驱节点.next待插入位置的前驱节点.next = 待插入指针待插入指针.next = temp

• 删除

待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next

基本技巧：

• 增加虚拟头节点

ListNode dummy = new ListNode(-1);dummy.next = head;//...return dummy.next;

例题：

• 简单
• 中等
• 困难

3. 二叉树

二叉树路径 / 深度：

• 简单
• 中等
• 困难

遍历二叉树：

• 中等
• 困难

构造二叉树：

• 简单
• 中等

利用二叉树的性质：

• 简单
• 中等

4. 队列

4.1 优先队列/堆

• 简单
• 中等
• 困难

4.2 双端队列/单调队列

两个特征：单调性（从队列头部到队列尾部保持递减的顺序）、双端操作

思路：

1. 给定初始【队列】
2. 从【队列】尾部插入元素时，提前取出【单调队列】中所有比该元素小的元素，等价于维护单调队列的单调性
3. 从【队列】头部删除元素时，需要判断待删除元素和【单调队列】头部元素是否相同，如果相同，则一同删除；如果不同，则表明待删除元素不是当前队列最大值

例题：

• 中等
  • ——已做
• 困难
  • ——已做

5. HashSet/HashMap

• 简单
• 中等
• 困难
  • —— 原地哈希

6. 并查集

• 中等
• 困难

二. 算法

1. 双指针

1.1 双指针

• 简单
• 中等

1.2 滑动窗口

大字符串包含小字符串

• 模板思路

// 1. 构造数组、set、map存放滑动窗口中出现的元素int[] letter = new int[26];Set
   
     set = new HashSet<>();Map
    
      map = new HashMap<>();// 2. 定义窗口左右边界：[left, right)int left = 0;int right = 0;int need_len = 0; // 统计小串中的元素在大串中出现的个数// 比如小串为"aabc" ，窗口中出现"abc"，need_len = 3，窗口中出现"aabc"，need_len = 4// 3. 右移窗口while (right < len) {   	char r = right处的字符	if (r在小串出现了) {   		窗口中r的个数 + 1		if (窗口中r的个数 <= 小串中r的个数) need_len ++;	}	right ++; // 右移窗口		// 出错debug位置	System.out.println("left = " + left +", right = " + right);	// 判断窗口是否需要收缩    while (窗口满足要求，即need_len = 小串的长度) {       	//可能在这里输出结果    	//...    	char l = left处的字符    	if (l在小串出现了) {       		if (窗口中l的个数 <= 小串中l的个数) need_len --;			窗口中l的个数 - 1		}               left ++;    }   }
    
   

• 简单
• 中等
• 困难

1.3 快慢指针

• 简单
• 中等

2. 二分查找

技巧：

• 划分区间：左闭右闭区间
• int mid = left + (right - left) / 2; 防止越界

模板1：在循环体内部【查找】元素

• while (left <= right )
• 退出循环的时候 left 和 right 不重合

public int search(int[] nums, int target) {       int left = 0;    int right = nums.length - 1;    while (left <= right ) {           int mid = left + (right - left) / 2;        if (nums[mid] == target) {               return mid;        }        else if (nums[mid] > target) {               right = mid - 1;        }        else {               left= mid + 1;        }	    }    return -1;}

模板2：在循环体内部【排除】元素，可以解决绝大部分问题，重点掌握！

• while (left < right )
• 退出循环的时候 left 和 right 重合

public int search(int[] nums, int target) {       int left = 0;    int right = nums.length - 1;    while (left < right ) {           int mid = left + (right - left) / 2;        if (nums[mid] == target) {               return mid;        }        else if (nums[mid] > target) {               right = mid;        }        else {               left= mid + 1;        }	    }    return nums[left] == target ? left : -1;}

题型1：在数组中查找符合条件的元素的下标

• —— 基本模板
• —— 山脉数组
• —— 山脉数组
• —— 旋转数组
• —— 旋转数组
• —— 旋转数组
• —— 旋转数组
• —— 区间搜索
• —— 涨见识

题型2：在一个有范围的区间里搜索一个整数

题型3：复杂的二分查找问题（判别条件需要遍历数组）

• 中等
  • —— 非常规二分
• 困难

参考链接：

3. BFS

• 中等

4. DFS + 回溯

DFS + 回溯的核心思路是画图！依据回溯图写代码！

4.1 洪水问题

洪水问题的标准解法是设置 visited 数组，设置方向数组，抽取私有方法

private static final int[][] Dir = {   {   -1, 0}, {   0, -1}, {   1, 0}, {   0, 1}};private boolean[][] visited;

• 洪水问题（从一点出发，将所有与该点相连的点改变状态）：
  • —— 洪水问题
  • —— 洪水问题
  • —— 洪水问题
  • —— 洪水问题

排列、组合、子集相关问题解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法

4.2 排列、组合、子集相关问题

• 排列、组合、子集相关问题：
  • —— 组合问题
  • —— 组合问题
  • —— 组合问题
  • —— 排列问题
  • —— 排列问题
  • —— 排列问题
  • —— 排列问题
  • —— 子集问题
  • —— 子集问题

4.3 数字问题

• 数字问题（需要注意数字过大的问题，另外一种形式的回溯问题）
  • —— 数字问题
  • —— 数字问题

4.4 游戏问题

• 游戏问题

4.5 一般类型问题

• 简单

• 中等

• 困难

5. DP

5.1 背包问题

• 中等
  • —— 完全背包
  • —— 01背包
  • —— 01背包
  • —— 01背包
  • —— 01背包
• 困难
  • —— 完全背包
  • —— 01背包
  • —— 01背包

5.2 网格二维DP

• 中等

  • ：从网格的左上角到右下角有多少条不同的路径
  • ：网格中有障碍物，从网格的左上角到右下角有多少条不同的路径
  • ：从网格的左上角到右下角的路径的和最小
  • ：从三角形顶端到三角形底端的路径的和最小
  • ：从网格的左上角到右下角的路径的积最大

• 困难

  • ：从网格的起点到终点拿起宝藏的路径
  • ：从网格的起点到终点不能重复通过网格

5.3 子序列问题

• 简单
  • —— 子序列问题
• 中等
  • —— 子序列问题
  • —— LIS
  • —— 子序列问题
• 困难
  • —— 二维LIS
  • —— 三维LIS
  • —— 二维LIS
  • —— 子序列问题
  • —— 转化为最长上升子序列问题

5.4 一般类型问题

• 简单

• 中等

  • —— 数字DP
  • —— 树形DP
  • —— 数字DP

• 困难

  • —— 区间DP

6. 分治

• 简单

7. 排序

7.1 排序

• 中等

7.2 归并排序

典型的分治思想

代码：

public static void main(String[] args) {   	int nums[] = {    8, 4, 55, 7, 1, 3, 6, 2 }; 	int[] temp = new int[nums.length];//提前定义临时数组，避免递归中反复开辟内存空间		mergeSort(nums, 0, nums.length - 1, temp);}	//分+合方法public static void mergeSort(int[] nums, int left, int right,int[] temp) {   	if(left < right) {   		int mid = (left + right) / 2; //中间索引		//向左递归进行分解		mergeSort(nums, left, mid, temp);		//向右递归进行分解		mergeSort(nums, mid + 1, right, temp);		//合并		merge(nums, left, mid, right, temp);	}}//合并两个有序数组：nums[left, mid] nums[mid + 1, right]public static void merge(int[] nums, int left, int mid, int right, int[] temp) {   		int l = left; // 初始化i, 左边有序序列的初始索引	int r = mid + 1; //初始化j, 右边有序序列的初始索引		//左边序列：[left-mid]，右边序列：[mid+1，right]	for(int k = left; k <= right; k ++) {       	//左边数添加完        if(l > mid) {               temp[k] = nums[r ++];        }        //右边数添加完        else if(r > right) {               temp[k] = nums[l ++];        }        //左边数小，先添加左边数        else if(nums[l] <= nums[r]) {               temp[k] = nums[l ++];        }        //右边数小，先添加右边数        else {               temp[k] = nums[r ++];            /			//这里是计算逆序对的关键			//应该先添加左边小的数，再添加右边大的数。			//但右边数比左边数小，即右边数比左边[l,mid]范围内的数都小			/        }    }		//将temp[]拷贝到arr[]，合并的数从left--right，right右边的位置不考虑	for(int tempi = left; tempi <= right; tempi ++) {   		nums[tempi] = temp[tempi];	}}

• 中等
• 困难

这类问题还有其他思路：从后往前插入排序、构造二叉排序树、树状数组、线段树等。

详细题解思路参考：

7.3 快速排序

• 简单
• 中等

7.4 拓扑排序

• 中等

7.5 桶排序/计数排序

• 困难

8. 贪心

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

• 简单
• 中等
  • ：尽可能跳远
  • ：让最先出现的对面阵营的人禁止投票
  • ：出现尽可能多的9

9. 前缀和

前缀和算法是一种重要的预处理算法，能大大降低查询的时间复杂度。最简单的题目就是：给定n个数和m次询问，每次询问一段区间的和。

比如求和为k的连续子数组的个数：

• 使用前缀和快速计算区间和（需要O(n)计算前缀和，再O(n*n)遍历区间和）

public int subarraySum(int[] nums, int k) {       int len = nums.length;    // 计算前缀和数组    int[] preSum = new int[len + 1];    preSum[0] = 0;    for (int i = 0; i < len; i++) {           preSum[i + 1] = preSum[i] + nums[i];    }    int count = 0;    for (int left = 0; left < len; left++) {           for (int right = left; right < len; right++) {               // 区间和 [left..right]，注意下标偏移            if (preSum[right + 1] - preSum[left] == k) {                   count++;            }        }    }    return count;}

• 前缀和优化：哈希表（边遍历，边存储前缀和，O(n)）
• 前缀和优化：数组（明确哈希表的键有哪些时，可以使用数组代替哈希表）

public int subarraySum(int[] nums, int k) {      // key：前缀和，value：key 对应的前缀和的个数    Map
   
     preSumFreq = new HashMap<>();    // 对于下标为 0 的元素，前缀和为 0，个数为 1    preSumFreq.put(0, 1);    int preSum = 0;    int count = 0;    for (int num : nums) {           preSum += num;        // 先获得前缀和为 preSum - k 的个数，加到计数变量里        if (preSumFreq.containsKey(preSum - k)) {               count += preSumFreq.get(preSum - k);        }        // 然后维护 preSumFreq 的定义        preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);    }    return count;}
   

比如求包含的元音均为偶数个的连续子数组的最大长度：连续子数组的含有元音的个数只能是偶数或者奇数，可以使用二进制表示，0 代表出现了偶数次，1 代表出现了奇数次

• 前缀和进一步优化2：哈希表 + 状态压缩
• 前缀和进一步优化2：数组 + 状态压缩

public int findTheLongestSubstring(String s) {       int n = s.length();    int[] pos = new int[1 << 5];    Arrays.fill(pos, -1);    int ans = 0, status = 0;    pos[0] = 0;    for (int i = 0; i < n; i++) {           char ch = s.charAt(i);        if (ch == 'a') {               status ^= (1 << 0);        } else if (ch == 'e') {               status ^= (1 << 1);        } else if (ch == 'i') {               status ^= (1 << 2);        } else if (ch == 'o') {               status ^= (1 << 3);        } else if (ch == 'u') {               status ^= (1 << 4);        }        if (pos[status] >= 0) {               ans = Math.max(ans, i + 1 - pos[status]);        } else {               pos[status] = i + 1;        }    }    return ans;}

• 简单
• 中等
• 困难

10. 状态压缩

利用二进制表示状态

• 简单
• 中等
  • DP + 状压
  • —— 前缀和 + 状压
• 困难
  • —— 回溯 + 状压
  • —— DP + 状压
  • —— 前缀和 + 状压

11. 摩尔投票法

解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。

1. 候选人(cand_num)初始化为nums[0]，票数count初始化为1。
2. 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
3. 当票数count为0时，更换候选人，并将票数count重置为1。
4. 遍历完数组后，cand_num即为最终答案。

• 简单
• 中等

三. 常见类型题

1. 区间问题

• 简单
• 中等
• 困难

2. 最大子序和问题

• 简单
• 困难

3. 岛屿问题（网格DFS+BFS）

• 简单
• 中等
• 困难

4. 位运算

求只出现一次的元素：使用异或 ^。规律：A ^ A = 0，A ^ 0 = A。

1. 出现偶数次，异或结果为0。
2. 两个数异或，二进制位相同的位置置0，不同的置1。

• 简单
• 中等

每个元素只出现一次，用二进制表示：0未出现、1出现

• 中等

统计二进制中1的个数：判断最后一位是否为1（n & 1）、右移（n >>> 1）

• 中等

5. 设计类问题

• 简单
• 中等
• 困难

6. 回文数/串

• 简单
• 中等
• 困难

7. 数字操作

• 简单
• 中等
• 困难

8. 股票问题（增加dp维数消除后效性）

状态1：第i天不持股状态转移：第i - 1天不持股 or 第i - 1天持股 + 第i天卖出股票状态2：第i天持股状态转移：第i - 1天持股 or 第i - 1天持股 + 第i天买入股票=====所以第i天的状态与第i - 1天状态有关，违反了后效性，所以需要增加dp维数dp[i][0] 不持股dp[i][1] 持股

详细题解：

• 简单
• 中等
• 困难

9. 打家劫舍问题（增加dp维数消除后效性）

• 简单
• 中等
  • —— 树形DP

10. 数学推理

• 中等

11. 操作矩阵

• 中等

12. n数之和

• 简单
• 中等

13. 最大矩形

• 困难

14. TOPK问题

快速排序：直接通过快排切分，找到第 K 小的数（即下标为 k - 1） 【O(N)】

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小

class Solution {       public int[] getLeastNumbers(int[] arr, int k) {           if (k == 0 || arr.length == 0) {               return new int[0];        }        // 最后一个参数表示我们要找的是下标为k-1的数        return quickSearch(arr, 0, arr.length - 1, k - 1);    }    private int[] quickSearch(int[] nums, int left, int right, int k) {           // 每快排切分1次，找到排序后下标为index的元素，如果index恰好等于k就返回index以及index左边所有的数；        int index = partition(nums, left, right);        if (index  == k) {               return Arrays.copyOf(nums, index + 1);        }        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。        return index > k? quickSearch(nums, left, index - 1, k): quickSearch(nums, index + 1, right, k);    }    // 快排切分，返回下标index，使得比nums[index]小的数都在index的左边，比nums[index]大的数都在index的右边。    private int partition(int[] nums, int left, int right) {       	int temp = 0;    	//基准数据        int pivot = nums[left];        //划分区间：基准左面的数小，基准右面的数大		while (left < right) {   			//如果队尾的元素大于基准，左移			while (nums[right] >= pivot && left < right) {   				right--;			}			//如果队尾元素小于pivot了，交换			if (nums[right] < pivot) {   				temp = nums[left];				nums[left] = nums[right];				nums[right] = temp;			}							//如果队首的元素小于基准，右移			while (nums[left] <= pivot && left < right) {   				left++;			}			//如果队首元素大于pivot时，交换			if(nums[left] > pivot) {   				temp = nums[left];				nums[left] = nums[right];				nums[right] = temp;						}		}			//跳出循环时left和right相等,此时的left或right就是pivot的正确索引位置		return left;     }}

大根堆：自带PriorityQueue 【O(NlogK)】

// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：// 1. 若目前堆的大小小于K，将当前数字放入堆中。// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。class Solution {       public int[] getLeastNumbers(int[] arr, int k) {           if (k == 0 || arr.length == 0) {               return new int[0];        }        // 默认是小根堆，实现大根堆需要重写一下比较器。        Queue
   
     pq = new PriorityQueue<>((v1, v2) -> v2 - v1);        for (int num: arr) {               if (pq.size() < k) {                   pq.offer(num);            } else if (num < pq.peek()) {                   pq.poll();                pq.offer(num);            }        }                // 返回堆中的元素        int[] res = new int[pq.size()];        int idx = 0;        for(int num: pq) {               res[idx++] = num;        }        return res;    }}
   

二叉搜索树TreeMap，求得的前K大的数字是有序的 【O(NlogK)】

class Solution {       public int[] getLeastNumbers(int[] arr, int k) {           if (k == 0 || arr.length == 0) {               return new int[0];        }        // TreeMap的key是数字, value是该数字的个数。        // cnt表示当前map总共存了多少个数字。        TreeMap
   
     map = new TreeMap<>();        int cnt = 0;        for (int num: arr) {               // 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1            if (cnt < k) {                   map.put(num, map.getOrDefault(num, 0) + 1);                cnt++;                continue;            }             // 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：            //    若当前数字比map中最大的数字还大，就直接忽略；            //    若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。            Map.Entry
    
      entry = map.lastEntry();            if (entry.getKey() > num) {                   map.put(num, map.getOrDefault(num, 0) + 1);                if (entry.getValue() == 1) {                       map.pollLastEntry();                } else {                       map.put(entry.getKey(), entry.getValue() - 1);                }            }                    }        // 最后返回map中的元素        int[] res = new int[k];        int idx = 0;        for (Map.Entry
     
       entry: map.entrySet()) {               int freq = entry.getValue();            while (freq-- > 0) {                   res[idx++] = entry.getKey();            }        }        return res;    }}
     
    
   

数据范围有限，直接计数排序 【O(N)】

基本思想：开辟一个额外空间（数组），统计元素个数，然后遍历这个数组，依此添加个数大于0的元素

详情参考：

class Solution {       public int[] getLeastNumbers(int[] arr, int k) {           if (k == 0 || arr.length == 0) {               return new int[0];        }        // 统计每个数字出现的次数        int[] counter = new int[10001];        for (int num: arr) {               counter[num]++;        }        // 根据counter数组从头找出k个数作为返回结果        int[] res = new int[k];        int idx = 0;        for (int num = 0; num < counter.length; num++) {               while (counter[num]-- > 0 && idx < k) {                   res[idx++] = num;            }            if (idx == k) {                   break;            }        }        return res;    }}

• 简单