蓝桥杯寒假模板总结
API
Arrays
排序：
当我们使用 Scanner 类的 nextInt() 方法读取整数时，会在输入缓冲区留下换行符。这会导致接下来使用 nextLine() 方法时直接读取到这个换行符，而不是我们想要的输入。
让我用代码演示一下这种情况：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入一个整数：");
int num = scanner.nextInt(); // 读取整数
System.out.println("你输入的整数是：" + num);
System.out.println("请输入一行字符串：");
String str = scanner.nextLine(); // 本来想读取一行字符串，但实际上会读取到之前的换行符
System.out.println("你输入的字符串是：" + str);
scanner.close();
}
}
如果我们输入如下内容：
123
hello
输出结果将会是：
请输入一个整数：
你输入的整数是：123
请输入一行字符串：
你输入的字符串是：
可以看到，由于之前的 nextInt() 留下了一个换行符，导致接下来的 nextLine() 直接读取到了这个换行符，而不是我们期望的输入 “hello”。
为了解决这个问题，可以在 nextInt() 后面加上一个 nextLine() 来消耗掉这个换行符，保证接下来的 nextLine() 可以正确读取到我们想要的输入。
归并排序模板
static void mergeSort(int[] a, int[] aa, int x, int y) {
// 如果数组只有一个元素，则返回，不需要排序
if (x == y) return;
// 找到数组的中间位置
int mid = (x + y) >> 1;
// 递归地对左半部分进行排序
mergeSort(a, aa, x, mid);
// 递归地对右半部分进行排序
mergeSort(a, aa, mid + 1, y);
// 合并左右两部分并排序
int i = x, j = mid + 1, k = x;
while (i <= mid && j <= y) {
// 如果左半部分当前元素小于等于右半部分当前元素，将左半部分的当前元素放入临时数组
if (a[i] <= a[j]) {
aa[k++] = a[i++];
} else {
// 如果右半部分当前元素小于左半部分当前元素，将右半部分的当前元素放入临时数组
aa[k++] = a[j++];
// 计算逆序对数量，即右半部分当前元素与左半部分剩余元素的数量
ans += mid - i + 1;
// 对结果取模，防止溢出
ans %= mod;
}
}
// 处理左半部分剩余元素
while (i <= mid) {
aa[k++] = a[i++];
}
// 处理右半部分剩余元素
while (j <= y) {
aa[k++] = a[j++];
}
// 将临时数组中排好序的元素复制回原数组
for (int index = x; index <= y; index++) {
a[index] = aa[index];
}
}
归并排序是一种分治算法，其基本思想是将待排序数组分割成两部分，分别对这两部分进行排序，然后将两部分合并起来得到有序数组。
在这段代码中，mergeSort方法实现了归并排序算法。具体步骤包括：
- 将数组a在范围[x, y]内进行归并排序。
- 如果x等于y，表示当前待排序数组只有一个元素，直接返回。
- 计算中间位置mid，以mid为界将数组分为左右两部分，分别继续进行归并排序。
- 合并左右两部分：利用i、j、k三个指针分别指向左部分、右部分和辅助数组aa，比较左右两部分的元素大小，并将较小的元素放入辅助数组aa中。
- 在合并过程中，如果发现a[i] > a[j]，则累加逆序对数量ans，并对mod取模。
- 将剩余未处理的元素依次放入辅助数组aa中。
- 最后将aa中的排序结果复制回原数组a。
冒泡排序
//冒泡排序
for(int i=0;i<arr.length-1;i++) {
for(int x=0;x< arr.length-1-i;x++) {
if(arr[x] > arr[x+1]) {
//当前一个大于后一个时，双方交换位置
int temp = arr[x];
arr[x] = arr[x+1];
arr[x+1] = temp;
}
}
}
二维数组的初始化
char[][] arr = {
{'U', 'D', 'D', 'L', 'U', 'U', 'L', 'R', 'U', 'L'},
{'U', 'U', 'R', 'L', 'L', 'L', 'R', 'R', 'R', 'U'},
{'R', 'R', 'U', 'U', 'R', 'L', 'D', 'L', 'R', 'D'},
{'R', 'U', 'D', 'D', 'D', 'U', 'U', 'U', 'U', 'U'},
{'U', 'R', 'U', 'D', 'L', 'L', 'R', 'R', 'U', 'U'},
{'D', 'U', 'R', 'L', 'R', 'L', 'D', 'L', 'R', 'L'},
{'U', 'L', 'L', 'U', 'R', 'L', 'L', 'R', 'D', 'U'},
{'R', 'D', 'L', 'U', 'L', 'L', 'R', 'D', 'D', 'D'},
{'U', 'U', 'D', 'D', 'U', 'D', 'U', 'D', 'L', 'L'},
{'U', 'L', 'R', 'D', 'L', 'U', 'U', 'R', 'R', 'R'}
};
整形
int[][] myArray = new int[3][3];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray[i].length; j++) {
myArray[i][j] = sc.nextInt(); // 从标准输入中读取数据并赋值给数组元素
}
}
字符型
arr = new char[10][10]; // 创建一个 10 行 10 列的字符型二维数组 arr，并将其初始化
for(int i = 0;i<arr.length;i++) { // 对于 arr 中的每一行
String s = sc.next(); // 从标准输入读入一行字符串
arr[i] = s.toCharArray(); // 将字符串转换为字符数组，并将其赋值给 arr 中的对应行
}
char[][] arr = new char[10][10]; // 创建一个大小为 10x10 的字符数组
String str = "UDDLUULRUL\n" +
"UURLLLRRRU\n" +
"RRUURLDLRD\n" +
"RUDDDDUUUU\n" +
"URUDLLRRUU\n" +
"DURLRLDLRL\n" +
"ULLURLLRDU\n" +
"RDLULLRDDD\n" +
"UUDDUDUDLL\n" +
"ULRDLUURRR";
// 定义一个包含一串字符串的变量
String[] arr1 = str.split("\n");
// 使用换行符 "\n" 将字符串分割成多行，并存储到字符串数组 arr1 中
int count = 0;
// 定义一个计数器变量，初始值为 0
for (int i = 1; i <= 10; i++) {
for (int j = 1; j <= 10; j++) {
arr[i - 1][j - 1] = arr1[i - 1].charAt(j - 1);
// 将每个字符数组 arr1 中的字符赋值给二维字符数组 arr
}
}
for (char[] row : arr) {
System.out.println(Arrays.toString(row));
}
// 打印二维字符数组 arr 的内容，每一行以字符串形式打印出来
结果
[U, D, D, L, U, U, L, R, U, L]
[U, U, R, L, L, L, R, R, R, U]
[R, R, U, U, R, L, D, L, R, D]
[R, U, D, D, D, D, U, U, U, U]
[U, R, U, D, L, L, R, R, U, U]
[D, U, R, L, R, L, D, L, R, L]
[U, L, L, U, R, L, L, R, D, U]
[R, D, L, U, L, L, R, D, D, D]
[U, U, D, D, U, D, U, D, L, L]
[U, L, R, D, L, U, U, R, R, R]
数学
模运算
模运算是大数运算中的常用操作。如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后，缩小数值再输出。取模也是哈希的常用技术。
定义取模运算为 a 除以 m 的余数，记为：amodm=a
对于 a mod m = a，必须要求 a 和 m 的正负号一致，都为正数或都为负数；如果正负不同，取模和求余的结果是不同的。另外取模的结果满足 0 ≤ a mod m < m−1，题目会用给定的 m，限制计算结果的范围。
取模运算的加减乘除
java里有快速幂库函数
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BigInteger bigInteger1 = scanner.nextBigInteger();
BigInteger bigInteger2 = scanner.nextBigInteger();
BigInteger bigInteger3 = scanner.nextBigInteger();
System.out.println(bigInteger1.modPow(bigInteger2,bigInteger3));
}
}
计算第一个大整数的第二个大整数次方对第三个大整数取模的结果，并将结果打印到标准输出。
不用函数
package 模板; // 定义一个包名为"模板"
import java.util.Scanner; // 导入 Scanner 类，用于从控制台读取输入
public class 快速幂模运算 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象，用于从控制台读取输入
// 输入三个整数
int b = scanner.nextInt(); // 读取第一个整数
int p = scanner.nextInt(); // 读取第二个整数
int k = scanner.nextInt(); // 读取第三个整数
int ans = 1; // 初始化结果变量为 1
// 使用快速幂算法计算 b^p % k 的结果
while (p != 0) {
if (p % 2 == 1) { // 如果 p 是奇数
ans = (ans * b) % k; // 更新结果变量
}
p >>= 1; // 将 p 右移一位，相当于 p 除以 2
b = (b * b) % k; // 更新 b 的值为 b 的平方取模 k
}
System.out.println(ans); // 输出结果
}
}
单纯取模
BigInteger result = a.mod(b);
计算大整数的幂运算后对另一个大整数取模的结果
System.out.println(bigInteger1.modPow(bigInteger2,bigInteger3));
N = q*p 求qp
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
// 给定的大整数字符串
String s = "1001733993063167141";
// 将字符串转换为 BigInteger 对象
BigInteger temp = new BigInteger(s);
BigInteger bigInteger = new BigInteger(s);
// 计算给定大整数的平方根
bigInteger = bigInteger.sqrt();
// 初始化计数器和常量
BigInteger i = new BigInteger("2");
BigInteger one = BigInteger.ONE;
BigInteger zero = BigInteger.ZERO;
// 从 2 开始迭代直到平方根
for (; i.compareTo(bigInteger) < 0; ) {
// 检查是否能整除给定的大整数
if (temp.remainder(i).equals(zero)) {
// 如果能整除，则打印出因子
System.out.println(i);
}
// 增加计数器
i = i.add(BigInteger.ONE);
}
// 打印结束标志
System.out.println("END!");
}
}
解决方法
i.compareTo(sqrtN)<=0
大整数的加减乘除
// 使用 BigInteger.TWO 进行大整数除法，实现对两个 BigInteger 对象相除
// 返回商，这里是对 left 和 right 之和进行除以 2 的操作，用于更新二分查找的中间值
BigInteger mid = left.add(right).divide(BigInteger.TWO);
// 使用 BigInteger.TWO 进行大整数加法，实现对两个 BigInteger 对象的加法操作
// 将 left 和 right 相加后除以 2，得到新的中间值，用于更新二分查找的中间值
BigInteger mid = left.add(right).divide(BigInteger.TWO);
// 使用 BigInteger.TWO 进行大整数减法，实现对两个 BigInteger 对象的减法操作
// 将当前中间值 mid 减去 1，向左移动一个单位，用于更新二分查找的右边界
BigInteger right = mid.subtract(BigInteger.ONE);
// 使用 BigInteger.TWO 进行大整数乘法，实现对两个 BigInteger 对象的乘法操作
// 将当前中间值 mid 乘以 2，用于更新二分查找的右边界
BigInteger square = mid.multiply(mid);
// 使用 BigInteger.TWO 进行大整数除法，实现对两个 BigInteger 对象相除
// 将 left 和 right 之和除以 2，用于更新二分查找的中间值
BigInteger mid = left.add(right).divide(BigInteger.TWO);
//取余和0
if (temp.remainder(i).equals(zero)) {
矩阵乘法
样例输入
2 1 3
1
2
1 2 3
样例输出
1 2 3
2 4 6
package 模板;
import java.util.Scanner;
public class 矩阵乘法 {
public static void main(String[] args) {
//矩阵乘法
//输入数据 N,M,K;
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int K = scanner.nextInt();
//定义二维数组存放
int [][] k1 = new int[N][M];
int [][] k2 = new int[M][K];
int [][] k3 = new int[N][K];
for (int i = 0;i < N ; i++){
for(int j = 0;j< M;j++) {
k1[i][j] = scanner.nextInt();
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < K; j++) {
k2[i][j] = scanner.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
int sum = 0;
for (int k = 0; k < M; k++) {
sum = sum + k1[i][k] * k2[k][j];
}
k3[i][j] = sum;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
System.out.print(k3[i][j] + " ");
}
System.out.println();
}
}
}
矩阵乘法模板
// 矩阵乘法
private static int[][] solve(int[][] a1, int[][] a2) {
int[][] a3 = new int[N + 1][N + 1]; // 存储计算结果
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int sum = 0;
for (int k = 1; k <= N; k++) {
sum = sum + a1[i][k] * a2[k][j]; // 计算矩阵元素乘积的和
}
a3[i][j] = sum; // 存储结果
}
}
return a3; // 返回计算结果
}
计算矩阵幂次
// 计算矩阵的幂次
private static int[][] modPow() {
int[][] ans = new int[N + 1][N + 1]; // 存储计算结果
for (int i = 1; i <= N; i++) {
ans[i][i] = 1; // 单位矩阵
}
while (M > 0) {
if (M % 2 == 1) { // 若幂次是奇数
ans = solve(ans, a); // 计算结果乘以原始矩阵
}
M = M / 2; // 幂次除以 2
a = solve(a, a); // 计算原始矩阵的平方
}
return ans; // 返回计算结果
}
最大公约数
整数 a 和 b 的最大公约数是指能同时整除 a 和 b 的最大整数 编码时只需要考虑正整数的最大公约数
java 大数有gcd函数
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 从标准输入读取两个整数
int a = scanner.nextInt();
int b = scanner.nextInt();
// 调用 gcd 方法计算最大公约数并打印结果
System.out.println(gcd(a, b));
}
// 计算两个整数的最大公约数
private static int gcd(int a, int b) {
// 如果 b 为 0，则返回 a，a 即为最大公约数
if (b == 0) {
return a;
} else {
// 否则递归调用 gcd 方法，传入 b 和 a%b，并返回结果
return gcd(b, a % b);
}
}
}
最小公倍数
- 是指几个自然数共有的倍数中除0以外最小的一个数。
- 有结论：lcm（a,b）gcd（a,b）= ab；
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
System.out.println((a*b)/gcd(a,b));
}
private static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
}
等差数列
- 最小数量 = （最大值-最小值）/公差 +1
- 公差 = 最小公倍数
- 思路：首先排序数组，然后找到数组中相邻元素的最大公约数作为等差数列的公差，最后通过等差数列的性质计算出最长等差子序列的长度。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static int[] a;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取数组长度
int N = scanner.nextInt();
// 初始化数组
a = new int[N];
// 读取数组元素
for (int i = 0; i < N; i++) {
a[i] = scanner.nextInt();
}
// 对数组元素进行排序
Arrays.sort(a);
// 初始化公共差
int temp = a[1] - a[0];
// 计算数组中所有相邻元素的最大公约数
for (int i = 1; i < N; i++) {
temp = gcd(temp, a[i] - a[i - 1]);
}
// 输出结果：数组中所有元素按照公共差排列的长度
System.out.println((a[N-1]-a[0])/temp+1);
}
// 计算两个数的最大公约数
private static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
}
素数
最大最小公倍数
一定要挑出三个互质的数才能使最小公倍数 最大
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
BigInteger n = new BigInteger(String.valueOf(N));
BigInteger n1 = new BigInteger(String.valueOf(N-1));
BigInteger n2 = new BigInteger(String.valueOf(N-2));
BigInteger n3 = new BigInteger(String.valueOf(N-3));
if (N % 2 == 1) {
System.out.println(n.multiply(n1).multiply(n2));
} else {
if (N % 3 == 0) {
System.out.println(n1.multiply(n2).multiply(n3));
} else {
System.out.println(n.multiply(n1).multiply(n3));
}
}
}
}
贪心
贪心（Greedy）可以说是最容易理解的算法思想：把整个问题分解成多个步骤，在每个步骤，都选取当前步骤的最优方案，直到所有步骤结束；在每一步，都不考虑对后续步骤的影响，在后续步骤中也不再回头改变前面的选择。简单地说，其思想就是“走一步看一步”、“目光短浅”。
虽然贪心法不一定能得到最优解，但是它思路简单、编程容易。因此，如果一个问题确定用贪心法能得到最优解，那么应该使用它。
贪心法求解的问题，需要满足以下特征：
最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。也就是说，从局部最优能扩展到全局最优。
贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。
贪心算法没有固定的算法框架，关键是如何选择贪心策略。
所谓贪心策略，必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。另外，把贪心法用在“虽然不是最好，但是还不错，我表示满意！”的某些难解问题上，例如旅行商问题，是很难得到最优解的。但是用贪心法常常能得到不错的近似解。如果不一定非要求得最优解，那么贪心的结果，也是很不错的方案。
折半查找模板
public static int binarySearch(String [] a, String x) {
int low = 0,high = a.length-1;
while(low <= high){
int mid = (low + high)/2;
if(a[mid].compareTo(x) <0){
low = mid +1;
}
else if(a[mid].compareTo(x)>0){
high = mid-1;
}
else
return mid;
}
return -1;
}
判断质数
// 检查一个数是否为质数的方法
static boolean check(int sum) {
if (sum <= 1) {
return false; // 如果 sum 小于等于 1，则返回 false
}
for (int i = 2; i * i <= sum; ++i) { // 循环检查 sum 是否可以被 i 整除
if (sum % i == 0) return false; // 如果可以被整除，则不是质数，返回 false
}
return true; // 否则是质数，返回 true
}
dfs
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
算法思想
沿着树的深度来遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
int check(参数)
{
if(满足条件)
return 1;
return 0;
}
void dfs(int step)
{
判断边界
{
相应操作
}
尝试每一种可能
{
满足check条件
标记
继续下一步dfs(step+1)
恢复初始状态（回溯的时候要用到）
}
}
static ans;//全局变量
static void dfs(层数，其他参数){
if(出局判断){
更新答案；//答案用全局变量表示
return;//返回上一层
}
(剪枝)
for(枚举下一层可能的情况){//每一种情况
if (used[i] == 0){//判断有没有使用过
used[i] = 1;//标记已经使用过
dfs(层数+1，其他参数);//下一层
used[i] = 0; //恢复状态
}
return;
}
}
static Set<Integer> st; // 用于存储结果集，其中不会包含重复元素
static void dfs(int pos, int sum) {
if (pos == len) { // 如果当前位置等于字符串的长度
if (check(sum)) { // 检查当前生成的数是否为质数
st.add(sum); // 如果是质数，则加入结果集
return;
}
return;
}
for (int i = 0; i < len; ++i) { // 遍历字符串中的每一个字符
if (!vis[i]) { // 如果当前字符未被访问过
sum = sum * 10 + (s.charAt(i) - '0'); // 将当前字符转换为数字并加到 sum 中
vis[i] = true; // 将当前位置标记为已访问
dfs(pos + 1, sum); // 递归调用，继续生成下一个数字
sum /= 10; // 回溯，恢复 sum 的值
vis[i] = false; // 恢复当前位置的访问状态
}
}
}
排列
全排列
import java.util.Scanner;
public class Main {
// 创建一个数组用于存储输入的数字
public static int[] a = new int[3];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 循环读取输入的数字并存储到数组中
for (int i = 0; i <= 2; i++) {
a[i] = scanner.nextInt();
}
// 调用深度优先搜索函数，从索引 0 到索引 2 进行全排列
dfs(0, 2);
}
// 深度优先搜索函数，用于生成从第 s 到第 t 的全排列
public static void dfs(int s, int t) {
// 如果 s 等于 t，表示已经生成一个完整的排列，可以打印结果并返回
if (s == t) {
for (int i = 0; i <= 2; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
return;
}
// 使用循环进行交换操作，生成全排列
for (int i = s; i <= t; i++) {
// 交换位置，将第 s 个元素与第 i 个元素交换
swap(s, i);
// 递归调用，继续生成剩余部分的排列
dfs(s + 1, t);
// 恢复原来的顺序，用于下一次循环
swap(i, s);
}
}
// 交换数组中两个位置的元素
public static void swap(int i, int j) {
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
迷宫
import java.util.Scanner;
public class Main {
static final int n = 10;
static char[][] mp = new char[n + 2][n + 2];
static boolean[][] vis = new boolean[n + 2][n + 2];
static int[][] solve = new int[n + 2][n + 2]; // solve[i][j]=1表示这个点能走出去；=2表示出不去
static int ans = 0;
static int cnt = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mp[i][j] = scanner.next().charAt(0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
vis = new boolean[n + 2][n + 2];
if (dfs(i, j)) ans++;
}
System.out.println("ans=" + ans + ",cnt=" + cnt);
}
static boolean dfs(int i, int j) {
if (i < 0 || i > n - 1 || j < 0 || j > n - 1) return true;
if (solve[i][j] == 1) return true; // 点(i,j)已经算过了，能出去
if (solve[i][j] == 2) return false; // 点(i,j)已经算过了，出不去
if (vis[i][j]) return false;
cnt++; // 统计 dfs() 了多少次
vis[i][j] = true;
if (mp[i][j] == 'L') {
if (dfs(i, j - 1)) {
solve[i][j] = 1;
return true;
} else {
solve[i][j] = 2;
return false;
}
}
if (mp[i][j] == 'R') {
if (dfs(i, j + 1)) {
solve[i][j] = 1;
return true;
} else {
solve[i][j] = 2;
return false;
}
}
if (mp[i][j] == 'U') {
if (dfs(i - 1, j)) {
solve[i][j] = 1;
return true;
} else {
solve[i][j] = 2;
return false;
}
}
if (mp[i][j] == 'D') {
if (dfs(i + 1, j)) {
solve[i][j] = 1;
return true;
} else {
solve[i][j] = 2;
return false;
}
}
return false;
}
}
哈希表的使用
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取输入的第一个整数，表示第一个数组的长度
int m = scanner.nextInt(); // 读取输入的第二个整数，表示第二个数组的长度
HashMap<Integer, Integer> mp = new HashMap<>(); // 创建一个 HashMap，用于存储第一个数组中每个元素出现的次数
for (int i = 0; i < n; i++) {
int x = scanner.nextInt(); // 读取第一个数组中的每个元素
mp.put(x, mp.getOrDefault(x, 0) + 1); // 将元素加入 HashMap，并更新其出现次数
}
int cnt = 0; // 用于统计第二个数组中与第一个数组中元素相同的个数
for (int i = 0; i < m; i++) {
int x = scanner.nextInt(); // 读取第二个数组中的每个元素
if (mp.containsKey(x) && mp.get(x) > 0) { // 如果该元素在第一个数组中出现，并且出现次数大于 0
mp.put(x, mp.get(x) - 1); // 将其出现次数减 1
cnt++; // 统计个数加 1
}
}
System.out.println(cnt); // 输出统计结果
}
}
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// 创建一个 HashMap 对象
HashMap<Integer, String> map = new HashMap<>();
// 添加键值对
map.put(1, "Java");
map.put(2, "Python");
map.put(3, "C++");
// 获取值
String value = map.get(2);
System.out.println("Value at key 2: " + value);
// 检查键是否存在
boolean containsKey = map.containsKey(3);
System.out.println("Key 3 exists: " + containsKey);
// 删除键值对
map.remove(1);
System.out.println("After removing key 1: " + map);
}
}
双指针找相同元素
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象，用于从标准输入读取数据
Scanner sc = new Scanner(System.in);
// 读取两个整数，分别表示两个数组的长度
int n = sc.nextInt();
int m = sc.nextInt();
// 创建两个整型数组，分别用于存储两个数组的元素
int a[] = new int[n];
int b[] = new int[m];
// 初始化变量 sum，用于统计相同元素的个数
int sum = 0;
// 读取第一个数组的元素，并存储到数组 a 中
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 读取第二个数组的元素，并存储到数组 b 中
for (int i = 0; i < m; i++) {
b[i] = sc.nextInt();
}
// 使用 Arrays.sort 对数组 a 和 b 进行排序，使其从小到大排列
Arrays.sort(a);
Arrays.sort(b);
// 关闭 Scanner 对象，释放资源
sc.close();
// 始化两个指针 x 和 y，分别指向数组 a 和 b 的起始位置
int x = 0;
int y = 0;
// 遍历数组 a 和 b，统计相同元素的个数
while (x < n && y < m) {
if (a[x] == b[y]) { // 如果两个元素相等，则相同元素个数加一，并移动两个指针
sum++;
x++;
y++;
} else if (a[x] < b[y]) { // 如果数组 a 的元素小于数组 b 的元素，则将指针 x 向后移动一位
x++;
} else { // 如果数组 a 的元素大于数组 b 的元素，则将指针 y 向后移动一位
y++;
}
}
// 输出相同元素的个数
System.out.println(sum);
}
}
BFS
计算斐波那契数列的第 n 项
// 计算斐波那契数列的第 n 项
private static BigInteger fb(int n) {
BigInteger[] fib = new BigInteger[n + 1];
fib[1] = BigInteger.ONE;
fib[2] = BigInteger.ONE;
for (int i = 3; i <= n; i++) {
fib[i] = fib[i - 1].add(fib[i - 2]);
}
return fib[n];
}
加入记忆化更高效 DP
public class 斐波那契数列 {
//求第20个数
static int cnt;
static long[] memo; // 使用静态数组作为记忆化存储
static long fib(int n) {
cnt++;
if (n == 1 || n == 2) {
return 1;
}
// 如果已经计算过第 n 个斐波那契数，则直接返回结果
if (memo[n] != 0) {
return memo[n];
}
// 否则进行递归计算，并将结果存储到 memo 数组中
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
public static void main(String[] args) {
int n = 20;
memo = new long[n + 1]; // 初始化 memo 数组
System.out.println(fib(n));
System.out.println(cnt);
}
}
排列与组合
字典序模板
private static boolean next(int[] nums, int[] prev) {
// 从右往左找到第一个递增的数 nums[i]
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 如果找不到递增的数，则说明当前排列已经是最大排列，无法生成下一个排列
if (i < 0) {
return false;
}
// 从右往左找到第一个比 nums[i] 大的数 nums[j]
int j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
// 交换 nums[i] 和 nums[j]
swap(nums, i, j);
// 对 i 后面的数字进行逆序排列，保证新排列是下一个字典序的排列
reverse(nums, i + 1);
// 检查新生成的排列是否与上一个排列相同，如果相同则继续生成下一个排列
if (prev != null && Arrays.equals(nums, prev)) {
return next(nums, prev);
}
return true;
}
public static void reverse(int[] nums, int start) {
int i = start;
int j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
递归实现全排列
public static void fullsort(int []num,int st,int m,int [] cnt,boolean[] used) {
if (st == num.length -1){
cnt[0]++;
if (cnt[0] == m){
printArray(num);
}
return;
}
for (int i = st; i<num.length;i++)
{
if (!used[i]) {
used[i] = true;
swap(num, st, i);
fullsort(num, st + 1, m, cnt, used);
swap(num, st, i);
used[i] = false;
}
}
}
public static void swap(int []a,int b,int c) {
int temp = a[b];
a[b] = a[c];
a[c] = temp;
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
手写排列
public static void main(String[] args) {
//定义数组
// 4选3 循环3次
int cnt = 0;
int []m = {1,2,3,4};
for (int i = 0; i<4;i++){
for(int j = 0; j<4;j++){
if (j != i){
for (int k = 0; k<4;k++){
if (k != j && k != i){
// 输出排列结果
cnt++;
System.out.printf("%d%d%d，", m[i],m[j],m[k]);
}
}
}
}
}
System.out.println();
System.out.println(cnt);
// 123，124，132，134，142，143，213，214，231，234，241，243，312，314，321，324，341，342，412，413，421，423，431，432，
//24
//字典序 从小到大排序
手写组合
public static void main(String[] args) {
//组合 n个数选m个
//n!/m!(n-m!)
//4选3
//循环3次不用判断
int []m = {1,2,3,4};
int cnt = 0;
for (int i = 0; i<4;i++){
for(int j = i+1; j<4;j++){
for (int k = j+1; k<4;k++){
cnt++;
System.out.printf("%d%d%d，", m[i],m[j],m[k]);
}
}
}
System.out.println();
System.out.println(cnt);
// 123，124，134，234，
// 4
// 字典序 从小到大排序
}
DFS实现全排列
public class 全排列 {
static int[] sequences = {1,2,3,4};//待全排序的序列
public static void main(String[] args) {
dfs(0,sequences.length-1);
}
public static void dfs(int start,int end) {
//递归结束条件
if(start == end){
System.out.println(Arrays.toString(sequences));//输出一个全排列序列
return;
}
for(int i = start;i<=end;i++){
swap(sequences, start, i);//把当前第1个数与后面所有数交换位置，注意所以i是从start开始
dfs(start+1, end);
swap(sequences, start, i);//恢复，用于下一次交换
}
}
public static void swap(int[] a,int i,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
拼接字符串大小再进行输出
”231“”342“”1“输出最大
”342“”231“”1“
package 排列和组合;
import java.util.Arrays;
import java.util.Scanner;
public class 拼数字符串比较大小再拼接输出 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int inputCount = Integer.parseInt(scanner.nextLine());
String[] nums = new String[inputCount];
for (int i = 0; i < inputCount; i++) {
nums[i] = scanner.next();
}
// 记录最大的排列
StringBuilder maxPermutation = new StringBuilder();
// 求全排列
generatePermutations(nums, 0, inputCount - 1, maxPermutation);
// 输出最大的排列
System.out.println(maxPermutation);
}
private static void generatePermutations(String[] nums, int start, int end, StringBuilder maxPermutation) {
if (start == end) {
// 当只有一个元素时，输出排列结果
StringBuilder currentPermutation = new StringBuilder();
for (String num : nums) {
currentPermutation.append(num);
}
// 如果当前排列比记录的最大排列大，则更新最大排列
if (currentPermutation.toString().compareTo(maxPermutation.toString()) > 0) {
maxPermutation.setLength(0);
maxPermutation.append(currentPermutation);
}
return;
}
// 递归地生成全排列
for (int i = start; i <= end; i++) {
// 将第i个元素与第start个元素交换位置
swap(nums, start, i);
// 递归生成以第start+1个元素开头的子数组的全排列
generatePermutations(nums, start + 1, end, maxPermutation);
// 恢复原始顺序，以便下一轮交换
swap(nums, start, i);
}
}
private static void swap(String[] nums, int i, int j) {
String temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
二分法
二分法有「整数二分」和「实数二分」两种情况。实数二分的代码好写不易出错；整数二分的代码因为要考虑整除的问题，代码容易出错。
二分法的效率极高。比如在有序的n个数中找某个数，只需要二分log2n 次，也就是说它的时间复杂度是 O(log2n) 的。例如有 n = 10^7个数，只需要24 次就能找到答案。
总结一下，二分法把一个长度为 n 的有序序列上 O(n) 的查找时间，优化到了O(log2n)。注意，这个序列的数字一定要是「有序」的，二分才有意义。在乱序的一堆数字上搞二分，没有任何用处。所以这个数字序列如果是乱序的，应该先排序再二分。
只搜索一个数的话二分法不如直接暴力搜索，但是搜m个数。那么排序再二分就是 O(nlogn+mlogn)，而你的暴力法是 O(mn)的，显然就快多了。
整数二分
假设目标值在闭区间[l,r]中
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0){ //数组为空
return -1;
}
int l = 0, r = nums.length - 1; //设置左右边界
while(l <= r){
int mid = l + (r-l) / 2; // 等同于mid=(l+r)/2,这种写法是为了防止数组越界,也可以写为(l+r) >>> 1
if(nums[mid] == target){ //最终target=mid,输出mid
return mid;
}else if(nums[mid] < target) { //目标值在(mid,r]之间
l = mid + 1;
}else { //目标值在[l,mid)之间
r = mid - 1;
}
}
// 最后判断: l>r 即数组不存在
return -1;
}
关于开闭区间问题
static int bin_search(int[] a, int n, int x) { // a[0]～a[n-1]是单调递增的
int left = 0, right = n ;//注意：不是 n-1，此时是左闭右开的[0,n)
while (left < right) {
int mid = left + (right - left) / 2; // int mid = (left + right) >> 1;
if (a[mid] >= x)
right = mid;
else
left = mid + 1;
} // 终止于left = right
return left; // 返回x的位置，如果不存在则返回x应该插入的位置
}
static int search_2(int[] arr,int l,int r,int x){
Arrays.sort(arr);
while (l<r){
int mid=(l+r+1)/2;
if (check(mid)){
l=mid;
}else{
r=mid-1;
}
}
return l;
}
二分查找 (left, right)
// 二分查找 (left, right)
int binarySearch3(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// target 在右区间，在(middle, right)中
left = mid;
} else {
// target 在左区间，在(left, middle)中
right = mid;
}
}
// 当: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
浮点数二分
double binarySearch(int[] nums,int target){
// eps 表示精度，取决于题目对精度的要求
double l = 0; double r = nums.length-1;
const double eps = 1e-6; //科学计数法1*10^-6 当区间长度小于eps时退出循环
while (r - l > eps){ //当区间长度大于eps时继续二分
double mid = (l + r) / 2;
if (nums[mid] > target ) r = mid;
else l = mid;
}
return l; //最后while循环退出的时候l和r近似相等
}
分巧克力
import java.util.Scanner;
public class Main {
private static int max = 100000;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
int[] H = new int[max];
int[] W = new int[max];
for (int i = 0; i < N; i++) {
H[i] = scanner.nextInt();
W[i] = scanner.nextInt();
}
int left = 0, right = max;
while (left < right) {
int mid = left + (right - left + 1) / 2;
int temp = 0;
for (int i = 0; i < N; i++) {
temp = temp + (H[i] / mid) * (W[i] / mid);
}
if (temp >= K) {
left = mid;
} else {
right = mid - 1;
}
}
System.out.println(left);
}
}
实数二分
double bsearch_3(double left, double right)
{
for (int i = 0; i < 100; i++)
{
double mid = (left + right) / 2;
if (check(mid))
left = mid;
else
right = mid;
}
return left;
}
double bsearch_4(double left, double right)
{
while(right-left>0.0000001){
double mid = (left + right) / 2;
if (check(mid))
left = mid;
else
right = mid;
}
return left;
}
前缀和
对于一个长度为n的数组 a[0]∼a[n−1]，它的前缀和 sum[i] 等于 a[0]∼a[i] 的和。例如：
sum[0] = a[0]
sum[1] = a[0] + a[1]
sum[2] = a[0] + a[1] + a[2]
⋯
利用递推，只要计算 n 次，就能计算出所有的前缀和：sum[i] = sum[i-1] + a[i]。当然，我们也能用 sum[] 反推计算出 a[]：a[i] = sum[i] - sum[i-1]。
如果预先算出了前缀和，这时想知道 a[i]∼a[j] 的和，可以用sum[j]−sum[i−1]。 可以利用前缀和快速计算出数组中任意一个区间的和。本来复杂度为 O(n)的区间和计算，优化到了 O(1) 的前缀和计算。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入的行数、列数和阈值 L
int N = sc.nextInt(); // 行数
int M = sc.nextInt(); // 列数
int L = sc.nextInt(); // 阈值 L
// 创建二维数组用于存储输入的矩阵
int[][] arr = new int[N + 1][M + 1];
// 输入数组元素
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
arr[i][j] = sc.nextInt();
}
}
// 计算二维数组的前缀和
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// 使用动态规划的思想，计算每个位置的前缀和
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
}
}
long cnt = 0; // 计数器，用于统计符合条件的子矩阵数量
// 暴力查询子矩阵，遍历所有可能的子矩阵
for (int i1 = 1; i1 <= N; i1++) {
for (int i2 = i1; i2 <= N; i2++) {
for (int j1 = 1; j1 <= M; j1++) {
for (int j2 = j1; j2 <= M; j2++) {
// 计算子矩阵中元素总和
int z = arr[i2][j2] - arr[i2][j1 - 1] - arr[i1 - 1][j2] + arr[i1 - 1][j1 - 1];
// 如果子矩阵中元素总和不超过 L，则增加计数器
if (z <= L) {
cnt++;
}
}
}
}
}
// 输出符合条件的子矩阵数量
System.out.println(cnt);
}
灵能传输
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cinScanner = new Scanner(System.in);
int T;
T = cinScanner.nextInt(); // 读取测试用例数量
while (T != 0) { // 循环处理每个测试用例
T--;
long in0 = 0, inn = 0; // 记录起始和结束位置
long n;
long s0, sn;
n = cinScanner.nextLong(); // 读取数组长度
long[] a = new long[(int) n + 2]; // 输入数组
long[] s = new long[(int) n + 1]; // 前缀和数组
long[] vis = new long[(int) n + 2]; // 标记数组
long[] ans = new long[(int) n + 2]; // 存储排序后的结果
for (int i = 0; i < n; i++) {
a[i] = cinScanner.nextLong(); // 读取数组元素
s[i + 1] = a[i]; // 计算前缀和
s[i + 1] += s[i];
}
s0 = s[0]; // 获取最小的前缀和
sn = s[(int) n]; // 获取最大的前缀和
if (s0 > sn) { // 保证 s0 是最小的前缀和
long t = s0;
s0 = sn;
sn = t;
}
Arrays.sort(s); // 对前缀和进行排序
// 找到最小和最大前缀和的位置
for (int i = 0; i <= (int) n; i++)
if (s[i] == s0) {
in0 = i;
break;
}
for (int i = (int) n; i >= 0; i--)
if (s[i] == sn) {
inn = i;
break;
}
int l = 0;
int r = (int) n;
// 从最小前缀和的位置开始向左遍历
for (int i = (int) in0; i >= 0; i -= 2) {
ans[l++] = s[i];
vis[i] = 1; // 标记已经使用的位置
}
// 从最大前缀和的位置开始向右遍历
for (int i = (int) inn; i <= n; i += 2) {
ans[r--] = s[i];
vis[i] = 1; // 标记已经使用的位置
}
// 将未使用的位置填充到结果数组中
for (int i = 0; i <= n; i++)
if (vis[i] == 0)
ans[l++] = s[i];
long res = 0;
// 计算相邻元素之间的最大差值
for (int i = 1; i <= n; i++)
res = Math.max(Math.abs((ans[i] - ans[i - 1])), res);
System.out.println(res); // 输出结果
}
}
}
并查集
判断连通性除了可以用学习过的 BFS、DFS 外，还可以用一个叫”并查集“的算法
并查集又可以理解为不相交集合上的合并查询
并查集是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并和查询问题。经典的应用有：判断连通性、最小生成树 Kruskal 算法、最近公共祖先（Least Common Ancestors, LCA）等。并查集在算法竞赛中也十分常见：一是简单且高效，二是应用很直观，三是容易和其他数据结构和算法结合。
1、什么是并查集
首先并查集是一个集合一种数据结构， 主要有两个操作，分别是
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：判断两个元素是否在同一个集合中。
主要用于处理不相交集合的合并及判断连接问题。
2、并查集能做什么
判断连接问题 （社交网络、关系网）
最近公共祖先
渗滤
图像处理
有限状态自动机的等价性
Hinley-Milner 的多态类型推断
Kruskal 的最小生成树算法
游戏(围棋、十六进制)
在 Fortran 中的编译语句的等价性问题
2、并查集实现结构
并查集的结构有点类似树型结构， 不过与树不同， 指针是指向父节点。并且里面会存在多颗树， 如下图
3、算法原理
3.1、合并（Union）
即将两个节点合并归属为同一个集合。 假设有两个节点A 和 B， 一般不是将A 和 到 B， 就是将B合并到A。 在实现上其实也就是将 A的根节点的parent指针指向节点B的根节点即可。 不过为了维持这颗树结构的平衡高度， 一般由较矮的节点树 和合并到 较高的节点树。
如下图， 如果要合并 g 和 b， 先找到g和b的根节点a和e， 然后把e的父指针指向a即可完成合并。
3.2、查询（Find)
即判断两个节点是否有关系， 通过parent指针不断向上寻找该节点的根节点， 然后判断它们两个的根节点是否一样即可， 如果一样说明属于同一个集合， 反之不是。
虽然一般查找根节点这个算法非常简单， 但是一般为了性能优化， 减少每次向上搜索的深度， 在查找find根节点的过程中会进行路径压缩。
压缩路径过程就是， 在向上寻找的过程中如果发现父节点不是根节点， 就把父指针指向爷爷节点， 然后自己直接跳到爷爷节点进行下一次判断，依次类推。 当遍历到根节点后， 整颗路径树就会变得非常的矮壮， 大大降低的搜索的深度。
字符串
字符串函数
package 字符串;
import java.util.Scanner;
public class 标题统计 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String s = sc.nextLine().replace(" ", "");
System.out.println(s.length());
}
}
图论
1.图的基本概念
图是由顶点集合以及顶点间的关系组成的一种数据结构:G = {V,E}.(顶点:vertex , 边:edge)
V是顶点集合 , V = {x|x属于某个对象集}.
E是边集 , E = {(x,y)|x , y 属于V}或者E = {<x,y>|x , y 属于V}.
Tips: (x,y)表示x,y 之间的双向通路 , 即(x,y)是无方向的.<x,y>表示x,y之间的有向通路 . 即<x,y>是有向的.
- 完全图
假设有n个顶点 , 对于无向图任意两个顶点之间有且仅有一条边.
完全无向图有n*(n-1)/2条边 .(因为每个顶点都重复计算了一次)
对于无向图 , 任意两个顶点之间都存在方向相反的两条弧.
完全有向图有n*(n-1)条边 .
- 领接顶点
两个顶点 v1 , v2 之间有边相连 , 则称 v1是v2的领接顶点或v2是v1的领接顶点.
- 顶点的度
顶点的度指的是它关联边的条数.有向图中顶点的度=入度(指出顶点的边)与出度(指入顶点的边)之和.
- 简单路径与回路
若路径上 v1,v2...vm均不重复 , 称这样的路径为简单路径. 若路径上第一个顶点 v1与最后一个顶点 vm 重合 , 则称这样的路径为回路或者环.
- 连通图
在无向图中 , 如果图中任意顶点都是连通的 , 则称此图为连通图.
- 强连通图
在有向图中，若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj 到 vi 的路径，则称此图是强连通图
- 极小连通子图
既有要保证连通 , 又要保证边数最小.
- 生成树
一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边
2.图的存储结构
因为图中既有节点又有边(节点与节点之间的关系) , 因此在图的存储中 , 我们可以使用一段连续的数组来存储节点 , 但边的关系存储较为复杂 , 通常有以下两种方式~~
2.1 邻接矩阵
因为节点与节点之间的关系就是是否连通 , 即为0 或 1 , 因此可以使用一个二维数组(领接矩阵)来保存节点与节点之间的关系.
无向图的矩阵是对称的 , 第 i 行(列)元素之和就是顶点 i 的度. 有向图的领接矩阵不一定是对称的 , 第 i 行(列)元素之和就是顶点 i 的出度(入度).
如果边带权值 , 并且两个顶点之间是连通的 , 上图中的边的关系就用权值代替 , 如果两个节点不通 , 则用无穷大代替.
用领结矩阵存储图的优点是能够快速知道两个节点之间是否连通 , 缺陷是如果顶点较多 , 边较少(领接矩阵较为稀疏) , 矩阵中存储了大量的0 , 比较浪费空间 , 并且要求两个顶点之间的路径不是很好求.
有向图的领接矩阵表示法中 , 顶点 i 的出度为: 第 i 行非0元素之和.顶点 i 的入度为: 第 i 列非0元素之和.
package Review;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class GraphOfMatrix {
private char[] arrayV;//节点数组
private int[][] Matrix;//领接矩阵
private boolean isDirect;//是否是有向图
HashMap<Character, Integer> map;//优化版的写法 , 目的是建立节点数组与其下标之间的映射关系
//构造节点数组和领接矩阵 size表示当前节点的个数
public GraphOfMatrix(int size, boolean isDirect) {
arrayV = new char[size];
Matrix = new int[size][size];
//将领接矩阵的每一位都初始化为无穷大
for (int i = 0; i < size; i++) {
Arrays.fill(Matrix[i], Integer.MIN_VALUE);
}
this.isDirect = isDirect;
}
/**
* 初始化节点数组
*
* @param array
*/
public void initArray(char[] array) {
for (int i = 0; i < array.length; i++) {
//要么初始化节点数组 , 要么建立映射关系.二选一
map.put(array[i], i);
// arrayV[i] = array[i];
}
}
/**
* 添加边
*
* @param src 起始节点
* @param dest 终止节点
* @param weight 权值
*/
public void addEdg(char src, char dest, int weight) {
//首先要确定起始节点和终止节点在矩阵中的位置
int srcIndex = getIndexOfV(src);
int destIndex = getIndexOfV(dest);
//将节点和节点之间的关系存储在矩阵中
Matrix[srcIndex][destIndex] = weight;
//如果是无向图 , 矩阵对称的位置同样需要赋值
if (!isDirect) {
Matrix[destIndex][srcIndex] = weight;
}
}
/**
* 获取节点数组的下标
*
* @param v
* @return
*/
public int getIndexOfV(char v) {
//同样两种写法二选一
return map.get(v);
// for (int i = 0; i < arrayV.length; i++) {
// if (arrayV[i]==v){
// return i;
// }
// }
// return -1;
}
/**
* 获取顶点的度
*
* @param v 有向图 = 入度+出度
* @return
*/
public int getDevOfV(char v) {
int count = 0;
int srcIndex = getIndexOfV(v);
for (int i = 0; i < Matrix.length; i++) {
if (Matrix[srcIndex][i] != Integer.MIN_VALUE) {
count++;
}
}
//计算有向图的出度
if (isDirect) {
for (int i = 0; i < Matrix[0].length; i++) {
if (Matrix[i][srcIndex] != Integer.MIN_VALUE) {
count++;
}
}
}
return count;
}
//打印领接表
public void printGraph() {
for (int i = 0; i < Matrix.length; i++) {
for (int j = 0; j < Matrix[0].length; j++) {
if (Matrix[i][j] != Integer.MIN_VALUE) {
System.out.print(Matrix[i][j] + " ");
} else {
System.out.print("∞ ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
char[] chars = {'A', 'B', 'C', 'D',};
graph.GraphOfMatrix graph = new graph.GraphOfMatrix(chars.length, true);
graph.initArray(chars);
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'D', 1);
graph.addEdge('B', 'A', 1);
graph.addEdge('B', 'C', 1);
graph.addEdge('C', 'B', 1);
graph.addEdge('C', 'D', 1);
graph.addEdge('D', 'A', 1);
graph.addEdge('D', 'C', 1);
graph.printGraph();
System.out.print("输入节点的度为: ");
System.out.println(graph.getDevOfV('A'));
System.out.println("=============");
}
}
2.2 邻接表
使用数组表示节点的集合 , 使用链表表示边的关系 , 每个链表的节点中即存放边的关系也存放权重.
1. 无向图临接表存储
A , B , C , D 分别代表 0 , 1 , 2, 3.
若 G 为无向图 , 则所需的存储空间为 O(V + 2E)
若 G 为有向图 , 则所需的存储空间为 O(V + E)
在有向图的领接表表示中 , 求一个给定顶点的出度/入度 , 只需计算领接表中相应节点的个数.
package Review;
import java.util.ArrayList;
public class GraphByNode {
//构造存储边的链表
static class Node {
public int src;//起始位置
public int dest;//目标位置
public int weight;//权值
public Node next;
public Node(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
//存储节点的数组
public char[] arrayV;
//存在链表的集合
public ArrayList<Node> edgList;
//判断是否为有向图
public boolean isDirect;
//构造领接表
public GraphByNode(int size, boolean isDirect) {
arrayV = new char[size];
edgList = new ArrayList<>(size);
this.isDirect = isDirect;
}
/**
* 初始化顶点数组
*
* @param array
*/
public void initArray(char[] array) {
for (int i = 0; i < arrayV.length; i++) {
arrayV[i] = array[i];
}
}
/**
* 添加边
*
* @param src 起点
* @param dest 终点
* @param weight 权重
*/
public void addEdge(char src, char dest, int weight) {
int srcIndex = getIndexOfV(src);
int destIndex = getIndexOfV(dest);
addEdgeChild(srcIndex, destIndex, weight);
}
public void addEdgeChild(int srcIndex, int destIndex, int weight) {
//获取链表的头结点
Node cur = edgList.get(srcIndex);
//遍历整个链表查看之前是否已存在该边
while (cur != null) {
if (cur.dest == destIndex) {
//之前存过这条边直接返回
return;
}
cur = cur.next;
}
//之前没有存储过这条边 , 头插法插入链表
Node node = new Node(srcIndex, destIndex, weight);
node.next = edgList.get(srcIndex);
edgList.set(srcIndex, node);
}
/**
* 获取 顶点下标
*
* @param v
* @return
*/
public int getIndexOfV(char v) {
for (int i = 0; i < arrayV.length; i++) {
if (arrayV[i] == v) {
return i;
}
}
return -1;
}
/**
* 获取顶点的度
*
* @param v
* @return
*/
public int getDevOfV(char v) {
int count = 0;
int srcIndex = getIndexOfV(v);
Node cur = edgList.get(srcIndex);
while (cur != null) {
count++;
cur = cur.next;
}
//以上仅仅计算了出度 , 还需计算入度
//遍历除了自身外 , 每一个顶点对应的链表中节点是否有指向srcIndex的.
if (isDirect) {
//将srcIndex当做目的下标.
int destIndex = srcIndex;
for (int i = 0; i < arrayV.length; i++) {
//出去自身
if (destIndex == i) {
continue;
}
Node pCur = edgList.get(i);
while (pCur != null) {
if (pCur.dest == destIndex) {
count++;
}
pCur = pCur.next;
}
}
}
return count;
}
/**
* 打印领接表
*/
public void printGraph() {
for (int i = 0; i < arrayV.length; i++) {
System.out.println(arrayV[i] + "->");
Node cur = edgList.get(i);
while (cur != null) {
System.out.println(arrayV[cur.dest] + "->");
cur = cur.next;
}
System.out.println();
}
}
public static void main(String[] args) {
graph.GraphByNode graph = new graph.GraphByNode(4, false);
char[] array = {'A', 'B', 'C', 'D',};
graph.initArray(array);
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'D', 1);
graph.addEdge('B', 'A', 1);
graph.addEdge('B', 'C', 1);
graph.addEdge('C', 'B', 1);
graph.addEdge('C', 'D', 1);
graph.addEdge('D', 'A', 1);
graph.addEdge('D', 'C', 1);
graph.printGraph();
System.out.println(graph.getDevOfV('A'));
System.out.println("=============");
}
}
3. 图的遍历
3.1 图的广度优先遍历
广度优先遍历类似于二叉树的层序遍历 , 由于二叉树的层序遍历借助队列 , 那么图的广度优先遍历也要借助队列. 广度优先遍历每次都访问起始节点相邻的所有节点 , 下图中的访问顺序就是B->A->C->D.
Tips:
注意入队和出队都要将visited数组下标置为true , 否则会出现多次打印最后一个元素的情况.
示例代码:
/**
* 广度优先搜索
* @param v
*/
public void bfs(char v) {
//获取起始节点的下标
int srcIndex = getIndexOfV(v);
//调用队列
Queue<Integer> queue = new LinkedList<>();
//使用visited数组记录节点是否被访问
boolean[] visited = new boolean[arrayV.length];
queue.offer(srcIndex);
while (!queue.isEmpty()) {
int top = queue.poll();
visited[top] = true;//每弹出一个元素visited数组相应下标就置为true
System.out.println(arrayV[top] + "->");
for (int i = 0; i < arrayV.length; i++) {//搜索领接矩阵中起始节点行的每一个元素
if (Matrix[top][i] != Integer.MAX_VALUE && visited[i] != true) {
queue.offer(i);
visited[i] = true;//每存入一个元素visited数组相应下标就置为true
}
}
}
}
3.2 图的深度优先遍历
图的深度优先优先遍历类似于二叉树的前序遍历 , 需要递归实现.从起始位置一条路走到底 , 再返回寻找下一条路.返回时需要一个visited数组记录元素使用遍历过.
图示过程:
代码：
/**
* 深度优先遍历
*
* @param v 起始元素
*/
public void dfs(char v) {
int srcIndex = getIndexOfV(v);
boolean[] visited = new boolean[arrayV.length];
dfsChild(srcIndex, visited);
}
public void dfsChild(int srcIndex, boolean[] visited) {
System.out.println(arrayV[srcIndex] + "->");
visited[srcIndex] = true;
for (int i = 0; i < Matrix[srcIndex].length; i++) {
if (Matrix[srcIndex][i] != Integer.MAX_VALUE) {
dfsChild(i, visited);
}
}
}
execl
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 涂良湘！