基础篇
1.基础知识（时间复杂度、空间复杂度等）
2.线性表（顺序表、单链表）
3.双链表、循环链表
4.队列
5.栈
6.递归算法
7.树、二叉树（递归、非递归遍历）
8.二叉搜索树（BST）
9.二分查找
10.二叉平衡树（AVL）
提高篇
1.散列表（哈希表）
2.堆
3.哈夫曼树、哈夫曼编码
4.并查集
5.串（KMP算法）
6.分治算法
7.贪心算法
8.回溯算法
9.动态规划（常见LCS、LIS等）
图论必会算法
1.DFS深度优先搜索
2.BFS广度优先搜索
3.Dijkstra（单源）最短路径算法
4.Floyd（多源）最短路径算法
5.Prim、Kruskal最小生成树算法
6.拓扑排序、关键路径
排序必知算法
1.交换类：冒泡排序
2.交换类：快速排序
3.插入类：直接插入排序
4.插入类：希尔排序
5.选择类：简单选择排序
6.选择类：堆排序
7.归并排序
8.桶排序
9.计数排序
10.基数排序
高级数据结构
1.红黑树
2.B树
3.跳跃表
4.字典树（Trie）
5.树状数组
6.后缀数组和后缀树
7.线段树
笔试面试常遇
1.快速幂
2.大数加减乘除
3.位运算
4.欧几里得（GCD）最大公约数、最小公倍数
5.滑动窗口、双指针
6.约瑟夫环问题
7.求素数（素数筛）
8.回文串（马拉车算法）
1、大字符串str1以及一个独立的小字符串str2，从这个大字符串str1里找到包含独立小字符串str2中所有字符的最小子字符串str3。例如，大字符串"meituan2019"和一个子字符串"i2t”，答案就应该是"ituan2”
滑动窗口代码模板
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static String findMinimumSubstring(String str1, String str2) {
if (str2 == null || str2.isEmpty()) {
return str1;
}//处理特殊情况
Map<Character, Integer> targetMap = new HashMap<>();
for (char ch : str2.toCharArray()) {
targetMap.put(ch, targetMap.getOrDefault(ch, 0) + 1);
}
//构建目标映射，对于每个字符ch，如果该字符还没有在 targetMap 中出现过，返回默认值 0；
//如果该字符已经在 targetMap 中存在，则返回其出现的次数，然后将这个次数加1
int left = 0, right = 0;//窗口的左右边界
int minLen = Integer.MAX_VALUE;
int count = str2.length();//窗口中满足条件的字符个数
int startIndex = 0;//最小子字符串的起始位置
Map<Character, Integer> windowMap = new HashMap<>();
while (right < str1.length()) {
char ch = str1.charAt(right);
if (targetMap.containsKey(ch)) {//windowMap指窗口内字符的出现次数
windowMap.put(ch, windowMap.getOrDefault(ch, 0) + 1);
if (windowMap.get(ch).intValue() <= targetMap.get(ch).intValue()) {
count--;
}
}
while (count == 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
startIndex = left;
}
char leftChar = str1.charAt(left);
if (targetMap.containsKey(leftChar)) {
windowMap.put(leftChar, windowMap.get(leftChar) - 1);
if (windowMap.get(leftChar).intValue() < targetMap.get(leftChar).intValue()) {
count++;
}
}
left++;
}
right++;
}
//在每一步中，窗口右移一格，将字符加入窗口，并更新 windowMap 和 count。
//当 count 减为0时，表示当前窗口包含了 str2 中的所有字符，开始尝试缩小窗口。
//每次左移窗口时，更新最小子字符串的长度和起始位置。
return minLen == Integer.MAX_VALUE ? "" : str1.substring(startIndex, startIndex + minLen);
//如果找到了最小子字符串，则返回该子字符串；否则返回空字符串
}
public static void main(String[] args) {
// String str1 = "meituan2019";
// String str2 = "i2t";
Scanner in = new Scanner(System.in);
String str1 = in.nextLine();
String str2 = in.nextLine();
System.out.println(findMinimumSubstring(str1, str2));
}
}
