1 介绍
1.1 概念
01.算法
操作数据、解决程序问题的一组方法
02.衡量
a.时间复杂度
程序所消耗的时间，一个算法中的语句执行次数称为语句频度或时间频度
b.空间复杂度
程序所占用的内存空间，在规模为n的情况下额外消耗的储存空间
c.平均时间复杂度
略
1.2 线性结构
01.一维数组
内存中连续分配、数组元素通过下标为0进行分配
连续内存空间，长度固定，一般不可动态扩容，随机访问
常见的Uitil有：String [],int [],ArrayList,Vector,CopyOnWriteArrayLis
ArrayList和Vector的区别是:Vector是线程安全的，方法同步
CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多
02.栈
线性表，只允许栈顶操作，栈底不允许操作，
先进后出，放入元素-出栈/取出元素入栈
常见的Uitil有：LinkedList，LinkedMap等
03.链表
通过链表的指针地址实现，有单链表，双向链表，循环链表
非连续内存空间，长度可以动态变化，顺序访问
常见的Uitil有：java.util.Stack
04.队列
线性表，
先进先出，放入元素-入队/取出元素-出队
如线程池，mq，连接池等。
05.串
字符串，是由N个字符组成的优先序列。
在Java里面就是指String,而String里面是由chat[]来进行储存。
1.3 非线性结构
01.多维数组
略
02.集合
由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义理解为实现了Collection接口的类叫集合。
03.树
最少有一个根节点组成，可以有多个子节点。
二叉树、 一般二叉树、完全二叉树
04.图
由结点的有穷集合V和边的集合E组成
05.散列表
哈希表，根据关键码和值 (key和value) 直接进行访问的数据结构
Java中的hashCode：class都是Object的子类，既所有的class都会有默认Object.java里面的hashCode的方法，
如果自己没有重写，默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。
1.4 附：8种数据结构
01.顺序表（数组）
a.介绍
顺序表是以数组为基础的数据结构，具有随机访问的特点，支持增删改查等基本操作。
b.算法技巧
线性枚举：逐一列举数组中的元素，常用于简单的查找或统计问题。
前缀和：用来快速计算某段连续子数组的和。
双指针：在数组上使用两个指针以不同的步伐进行移动，常用于滑动窗口、区间查找等。
二分枚举：在有序数组中查找元素，时间复杂度为O(log n)。
三分枚举：用于查找单峰函数的极值点。
离散化：将数据映射到较小范围的整数，用于降低复杂度。
c.排序算法
冒泡排序：每次比较相邻元素并交换，时间复杂度O(n^2)。
选择排序：每次选择最小值并放置于前端，时间复杂度O(n^2)。
插入排序：每次将一个新元素插入已排序的序列，时间复杂度O(n^2)。
希尔排序：插入排序的改进版，使用间隔排序，时间复杂度O(n log n)。
归并排序：分治法排序，时间复杂度O(n log n)。
快速排序：分区交换排序，时间复杂度O(n log n)。
堆排序：利用堆这种数据结构排序，时间复杂度O(n log n)。
计数排序：适合元素范围小的整数排序，时间复杂度O(n+k)。
基数排序：对数字按位数分配排序，时间复杂度O(n*k)。
d.常用思想
模拟：直接按照题意逐步实现。
贪心：每一步选择局部最优解，求全局最优。
02.链表
a.介绍
链表是一种动态数据结构，适合频繁插入和删除操作。
b.类型
单向链表：只有一个方向的指针。
双向链表：每个节点有前后两个指针，便于双向遍历。
03.栈
a.介绍
栈是一种LIFO（后进先出）的数据结构。
b.类型
普通栈：用于函数调用、括号匹配等。
单调栈：栈内元素单调递增或递减，用于解决区间最值问题。
04.队列
a.介绍
队列是一种FIFO（先进先出）的数据结构。
b.类型
普通队列：常用于广度优先搜索。
双端队列：可从两端插入和删除元素。
单调队列：队列中的元素保持单调性，适用于滑动窗口问题。
05.字符串
a.介绍
字符串问题常见的有模式匹配、前缀树等。
b.算法
KMP：用于字符串模式匹配，时间复杂度O(n)。
字典树（Trie）：用于词频统计、单词查找。
马拉车算法：用于求最长回文子串，时间复杂度O(n)。
AC自动机：多模式串匹配，结合字典树和KMP。
后缀数组：用于字符串后缀排序，求最长重复子串。
BM算法：用于长文本中快速定位模式串。
06.树
a.介绍
树是分层结构的数据结构，广泛用于存储有层次关系的数据。
b.类型
二叉树：每个节点最多有两个子节点。
二叉搜索树：左子树小于根，右子树大于根。
AVL树：自平衡的二叉搜索树。
线段树：动态维护区间和、区间最值等。
霍夫曼树：用于数据压缩。
堆：一种完全二叉树，常用于优先队列。
红黑树：平衡二叉树，插入和删除操作较快。
伸展树：用于动态维护节点的访问频率。
左偏树：用于优先队列合并。
Treap：结合二叉搜索树和堆的性质。
B+树：多路搜索树，常用于数据库索引。
树链剖分：将树拆分成链以便于查询。
07.图
a.介绍
图是一种复杂的结构，表示节点间的关系。
b.常用算法
二分图：图的节点可以分成两部分，且没有同一部分内部的边。
最短路算法：如Dijkstra、Bellman-Ford、Floyd等。
最小生成树：如Prim、Kruskal算法。
最近公共祖先：用于求解两个节点的最近公共父节点。
深度优先搜索（DFS）：图的遍历算法。
强连通分量：求图中的强连通子图。
双连通分量：图中没有割点的最大子图。
2-SAT问题：布尔表达式可满足性问题。
欧拉回路和哈密尔顿回路：图的特殊路径问题。
广度优先搜索（BFS）：图的遍历，常用于最短路径。
拓扑排序：用于有向无环图的线性排序。
A*算法：用于最短路径的启发式搜索。
稳定婚姻问题：配对问题。
双向广搜：双端搜索，减小搜索空间。
差分约束：用于约束问题建模。
并查集：用于动态连通性问题。
哈希表和跳跃表：快速查找数据结构。
树状数组：用于动态维护前缀和等。
最大流：如Edmonds-Karp、Dinic算法。
08.动态规划
a.介绍
动态规划是分治思想的延伸，常用于求解最优子结构问题。
b.类型
递推：通过状态转移方程不断递推求解。
线性DP：如最长子序列问题。
记忆化搜索：将递归结果存储以避免重复计算。
背包问题：多种背包类型的动态规划求解。
树形DP：树结构上的动态规划。
区间DP：如矩阵连乘问题。
数位DP：处理数值的动态规划。
状态压缩DP：将状态以二进制压缩表示。
2 常见算法
2.1 排序算法
00.八大排序算法
1.直接插入排序（Insertion Sort）
2.希尔排序（Shell Sort）
3.选择排序（Selection Sort）
4.堆排序（Heap Sort）
5.冒泡排序（Bubble Sort）
6.快速排序（Quick Sort）
7.归并排序（Merging Sort）
8.基数排序（Radix Sort）
01.冒泡排序
a.说明
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²).
最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²).
b.示例
/**
* 冒泡排序
*
* ①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* ②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
* ③. 针对所有的元素重复以上的步骤，除了最后一个。
* ④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr){
for (int i = arr.length; i > 0; i--) { //外层循环移动游标
for(int j = 0; j < i && (j+1) < i; j++){ //内层循环遍历游标及之后(或之前)的元素
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
}
}
02.选择排序
a.说明
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
b.示例
int[] arr = { 1, 5, 6, 12, 4, 9, 3, 23, 39, 403, 596, 87 };
System.out.println("排序前：" + Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
int lowerIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 循环找出最小的一个索引
if (arr[j] < arr[lowerIndex]) {
lowerIndex = j;
}
}
// 交换
int temp = arr[i];
arr[i] = arr[lowerIndex];
arr[lowerIndex] = temp;
}
System.out.println("排序后：" + Arrays.toString(arr));
03.插入排序
a.说明
把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。
在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。
b.示例
int[] arr = { 2, 1, 5, 6, 12, 4, 9, 3, 23, 39, 403, 596, 87 };
System.out.println("排序前：" + Arrays.toString(arr));
// i从一开始，因为第一个数已经是排好序的
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
// 元素交换
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
System.out.println("排序后：" + Arrays.toString(arr));
04.希尔排序
a.说明
简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
b.示例
/**
* 希尔排序
*
* @param array
* @return
*/
public static int[] ShellSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
return array;
}
2.2 冒泡排序
01.魔术步骤的算法化拆解
a.初始状态
将筷子、杯子和勺子随机排列在左、中、右三个位置
b.筷子与左边交换
如果筷子不在最左边，则与左边物品交换位置，交换后的摆放情况如下
c.杯子与右边交换
如果杯子不在最右边，则与右边物品交换位置，交换后的摆放情况如下
d.勺子与左边交换
如果勺子不在最左边，则与左边物品交换位置，交换后的摆放情况如下
e.最终结果
无论初始排列如何，杯子最终都会出现在最右侧
02.冒泡排序是一种通过相邻元素交换逐步将最大值“冒泡”到序列末端的算法
a.核心特征
交换操作：通过多次遍历，每次比较相邻元素并交换位置。
确定性结果：无论初始排列如何，最终总能使元素有序。
循环结构：依赖循环次数与条件判断实现目标。
b.在刘谦的魔术中，某些操作步骤与冒泡排序的交换逻辑不谋而合
交换操作的相似性：魔术中的每一步交换都类似于冒泡排序中的相邻元素交换。例如，筷子与左边交换、杯子与右边交换，都是通过局部调整逐步将目标物品移动到指定位置。
确定性结果的映射：无论初始排列如何，魔术最终总能将杯子移动到最右侧，这与冒泡排序的确定性结果一致。
循环结构的体现：魔术中的三步交换操作可以看作是一个循环过程，类似于冒泡排序的多轮遍历。
c.数学共性：置换群与位置控制
从数学角度看，魔术中的操作可抽象为**置换群（Permutation Group）**的应用。例如：
1.冒泡排序的交换步骤：每次交换相当于对排列施加一次置换操作。
2.魔术中的牌序调整：插入、丢弃和循环移动均可视为对物品排列的置换。
-----------------------------------------------------------------------------------------------------
以2025年刘谦魔术中涉及杯、勺、筷的操作为例：
1.交换规则：筷子与左侧交换、杯子与右侧交换、勺子与左侧交换。
2.冒泡排序映射：通过三次交换操作，杯子被强制移动到最右侧，类似于冒泡排序中将最大值“冒泡”到末尾。
d.魔术与算法的本质联系
刘谦的魔术设计巧妙融合了数学与表演艺术，其底层逻辑与计算机算法的共性体现在：
确定性流程：通过固定规则保证结果的唯一性。
位置操作：利用循环、置换等操作控制元素位置。
抽象映射：将复杂问题简化为数学模型（如置换群或冒泡排序）。
-----------------------------------------------------------------------------------------------------
尽管2025年魔术的核心更贴近排列组合问题，但其步骤中隐含的交换与循环逻辑与冒泡排序的哲学不谋而合。
这种跨界关联不仅展现了数学的普适性，也为我们理解魔术的“奇迹时刻”提供了新的视角。
e.原理
冒泡排序是一种简单的比较排序算法，其核心思想是通过多次比较相邻元素并交换位置，将最大（或最小）的元素逐步 “冒泡” 到数组末尾（或开头）。
-----------------------------------------------------------------------------------------------------
以下是用 JavaScript 实现冒泡排序的代码
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换arr[j] 与 arr[j + 1]
[arr[j],arr[j+1]] = [arr[j + 1],arr[j]];
}
}
}
return arr;
}
// 测试示例
let numbers = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(numbers));
3 字符串
3.1 每个字符出现的次数
01.说明
a.HashMap
使用 HashMap 来统计字符出现的次数，适用于任何字符集。首先将字符串转换为字符数组，遍历每个字符，
并在 HashMap 中更新每个字符的出现次数。最后输出每个字符的计数。
b.Array
使用一个大小为 256 的 int[] 数组来存储所有字符的计数，适用于 ASCII 字符集。遍历字符串中的字符，
将其 ASCII 值作为数组索引，直接增加计数。最后输出出现次数大于 0 的字符及其次数。
c.Stream
使用 Java 8 引入的 Stream API，通过 Collectors.groupingBy 和 Collectors.counting 来统计字符出现次数。
mapToObj 将每个字符的 int 值转换为 Character，然后按字符进行分组并计数。
d.TreeMap
使用 TreeMap 来统计字符出现的次数，并按字典顺序输出结果。TreeMap 会自动按字符排序，适合需要有序输出的场景。
e.ApacheCommons
使用 Apache Commons Lang 库中的 StringUtils.countMatches 方法来统计每个字符的出现次数。
此方法非常简洁，但需要额外引入 Apache Commons Lang 库。
02.代码
import java.util.*; // 导入集合框架
import org.apache.commons.lang3.StringUtils; // 导入Apache Commons Lang库
public class CharacterCount {
// 方法一：使用 HashMap 来统计字符出现的次数
public static void countUsingHashMap(String str) {
// 将字符串转化为字符数组
char[] chars = str.toCharArray();
// 创建一个 HashMap 来存储字符及其出现次数
HashMap<Character, Integer> hm = new HashMap<>();
// 遍历字符数组
for (char c : chars) {
// 使用 containsKey 判断字符是否已经出现过
if (!hm.containsKey(c)) {
// 如果没有出现过，初始化次数为 1
hm.put(c, 1);
} else {
// 否则，获取当前次数并加 1
hm.put(c, hm.get(c) + 1);
}
}
// 输出每个字符及其出现次数
System.out.println("方法一：使用 HashMap");
for (Character key : hm.keySet()) {
System.out.println(key + " === " + hm.get(key));
}
}
// 方法二：使用 int[] 数组（仅适用于 ASCII 字符）
public static void countUsingArray(String str) {
// 创建一个大小为 256 的数组，用于存储所有 ASCII 字符的出现次数
int[] count = new int[256];
// 遍历字符串中的每个字符
for (char c : str.toCharArray()) {
// 将字符的 ASCII 值作为数组的索引，增加对应位置的计数
count[c]++;
}
// 输出每个字符及其出现次数
System.out.println("方法二：使用 int[] 数组");
for (int i = 0; i < 256; i++) {
if (count[i] > 0) {
System.out.println((char) i + " === " + count[i]);
}
}
}
// 方法三：使用 Java 8 的 Stream API 来统计字符出现的次数
public static void countUsingStream(String str) {
// 使用 Stream API 统计每个字符出现的次数
Map<Character, Long> charCountMap = str.chars()
.mapToObj(c -> (char) c) // 将 int 转换为 Character
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); // 按字符分组并计数
// 输出每个字符及其出现次数
System.out.println("方法三：使用 Stream API");
charCountMap.forEach((key, value) -> System.out.println(key + " === " + value));
}
// 方法四：使用 TreeMap 来统计字符出现的次数，并按字典顺序输出
public static void countUsingTreeMap(String str) {
// 创建一个 TreeMap，按字符的自然顺序排序
Map<Character, Integer> charCountMap = new TreeMap<>();
// 遍历字符串中的每个字符
for (char c : str.toCharArray()) {
// 使用 getOrDefault 方法来统计每个字符的次数
charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
}
// 输出每个字符及其出现次数
System.out.println("方法四：使用 TreeMap");
charCountMap.forEach((key, value) -> System.out.println(key + " === " + value));
}
// 方法五：使用 Apache Commons Lang 库中的 StringUtils 来统计字符出现的次数
public static void countUsingApacheCommons(String str) {
// 使用 StringUtils.countMatches 来统计每个字符出现的次数
System.out.println("方法五：使用 Apache Commons Lang");
for (char c : str.toCharArray()) {
System.out.println(c + " === " + StringUtils.countMatches(str, String.valueOf(c)));
}
}
public static void main(String[] args) {
// 示例字符串
String input = "aabccddeea";
// 调用每种方法进行字符计数
countUsingHashMap(input); // 使用 HashMap
System.out.println();
countUsingArray(input); // 使用 int[] 数组
System.out.println();
countUsingStream(input); // 使用 Stream API
System.out.println();
countUsingTreeMap(input); // 使用 TreeMap
System.out.println();
countUsingApacheCommons(input); // 使用 Apache Commons Lang
}
}
3.2 判断是否是回文字符串
01.说明
a.通过反转字符串判断
通过 StringBuilder 的 reverse() 方法反转字符串，然后判断原字符串与反转后的字符串是否相同。
如果相同，则是回文，否则不是回文。
b.通过双指针法判断
使用双指针法，从字符串的两端开始比较字符，逐步向中间逼近。
如果有任何一对字符不相等，返回 false，否则返回 true。
c.忽略大小写和非字母数字字符判断回文
先将字符串转换为小写，并删除非字母和数字的字符（使用正则表达式）。
然后通过双指针法判断回文。
e.通过递归法判断
使用递归的方式检查字符串的首尾字符是否相等，然后递归地处理剩余部分。
02.代码
public class Palindrome {
// 方法一：通过反转字符串判断
public static boolean isPalindromeByReverse(String str) {
// 如果字符串为空或仅包含一个字符，直接返回 true
if (str == null || str.length() <= 1) {
return true;
}
// 反转字符串
String reversed = new StringBuilder(str).reverse().toString();
// 判断原字符串与反转字符串是否相同
return str.equals(reversed);
}
// 方法二：通过双指针法判断
public static boolean isPalindromeByTwoPointers(String str) {
// 如果字符串为空或仅包含一个字符，直接返回 true
if (str == null || str.length() <= 1) {
return true;
}
int left = 0;
int right = str.length() - 1;
// 双指针从两端向中间移动，逐个字符进行比较
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false; // 一旦发现不相等，直接返回 false
}
left++;
right--;
}
return true; // 全部字符相等，返回 true
}
// 方法三：忽略大小写和非字母数字字符判断回文
public static boolean isPalindromeIgnoreCaseAndSymbols(String str) {
// 如果字符串为空或仅包含一个字符，直接返回 true
if (str == null || str.length() <= 1) {
return true;
}
// 将字符串转为小写并去除非字母数字字符
String cleanedStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// 使用双指针法判断回文
int left = 0;
int right = cleanedStr.length() - 1;
while (left < right) {
if (cleanedStr.charAt(left) != cleanedStr.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 方法四：通过递归法判断回文
public static boolean isPalindromeByRecursion(String str) {
// 基本情况：如果字符串长度为 0 或 1，返回 true
if (str == null || str.length() <= 1) {
return true;
}
// 递归：检查首尾字符是否相等，并递归处理中间部分
if (str.charAt(0) != str.charAt(str.length() - 1)) {
return false;
}
// 递归检查去掉首尾字符的子字符串
return isPalindromeByRecursion(str.substring(1, str.length() - 1));
}
// 主函数，执行所有方法并展示结果
public static void main(String[] args) {
String str1 = "madam";
String str2 = "hello";
String str3 = "A man, a plan, a canal: Panama";
String str4 = "race a car";
// 方法一：通过反转字符串判断
System.out.println("方法一：通过反转字符串判断");
System.out.println("字符串 \"" + str1 + "\" 是否是回文: " + isPalindromeByReverse(str1)); // 输出: true
System.out.println("字符串 \"" + str2 + "\" 是否是回文: " + isPalindromeByReverse(str2)); // 输出: false
System.out.println();
// 方法二：通过双指针法判断
System.out.println("方法二：通过双指针法判断");
System.out.println("字符串 \"" + str1 + "\" 是否是回文: " + isPalindromeByTwoPointers(str1)); // 输出: true
System.out.println("字符串 \"" + str2 + "\" 是否是回文: " + isPalindromeByTwoPointers(str2)); // 输出: false
System.out.println();
// 方法三：忽略大小写和非字母数字字符判断回文
System.out.println("方法三：忽略大小写和非字母数字字符判断回文");
System.out.println("字符串 \"" + str3 + "\" 是否是回文: " + isPalindromeIgnoreCaseAndSymbols(str3)); // 输出: true
System.out.println("字符串 \"" + str4 + "\" 是否是回文: " + isPalindromeIgnoreCaseAndSymbols(str4)); // 输出: false
System.out.println();
// 方法四：通过递归法判断回文
System.out.println("方法四：通过递归法判断");
System.out.println("字符串 \"" + str1 + "\" 是否是回文: " + isPalindromeByRecursion(str1)); // 输出: true
System.out.println("字符串 \"" + str2 + "\" 是否是回文: " + isPalindromeByRecursion(str2)); // 输出: false
}
}