第一题：小美的排列询问
解题思路:
简单题，一次遍历数组，判断 是否有和x、y相等并且相连 即可。
可优化逻辑：因为x和y是后输入的，必须存储整个数组，但是上面说了 **排列是指一个长度为n的数组，其中 1 到 n 每个元素恰好出现一次。**可以充分利用该信息创建一个大小为n+1的数组存储各个元素的所在位置，这样最终直接判断x和y所在位置差是否为1即可判断结果。、
解法一 ：哈希表（比较灵活运用哈希表）
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();//int[] arr = new int[n];//map 记录每个元素所在的位置int[] map = new int[n+1];for (int i = 0; i < n; i++) {int ai = scanner.nextInt();map[ai] = i;}int x = scanner.nextInt();int y = scanner.nextInt();if(Math.abs(map[x]-map[y])==1){System.out.println("Yes");return;}System.out.println("No");}
}
Math.abs是 Java 中java.lang.Math类的一个静态方法，用于返回一个数的绝对值。绝对值指的是一个数在数轴上距离原点的距离，因此它始终是非负数。这个方法有多个重载版本，可以处理不同的数据类型，包括int、long、float和double。
时空复杂度
时间复杂度 ：O(n)。一次遍历数组。
空间复杂度 ：O(``n``)。哈希表所占空间
解法二：直接模拟（简单粗暴，易想到的方法）
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = scanner.nextInt();}int x = scanner.nextInt();int y = scanner.nextInt();//遍历数组arr，只有x在前，y在后，或者x在后，y在前的情况满足题意，属于Yesfor (int i = 0; i < n - 1; i++) {if ((arr[i] == x && arr[i + 1] == y) || (arr[i] == y && arr[i + 1] == x)) {System.out.println("Yes");return;}}System.out.println("No");}
}
第二题：小美走公路
解题思路
注意，本题和LeetCode1184.公交站间的距离完全一致。
题目要求计算最短距离，实际上一共只有两条可能的路径：顺时针从x走到y和逆时针从x走到y。
因此只需要计算顺时针和逆时针的两个结果进行比较即可。
唯一需要注意的地方就是边界，即第n站到第1站的距离的计算，这里可以通过 逻辑判断 是否到达边界，也可以通过 取余的方式避免边界问题。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 读取站的数量int[] distances = new int[n]; // 存储各站之间的距离for (int i = 0; i < n; i++) {distances[i] = scanner.nextInt(); // 读取各站之间的距离}int x = scanner.nextInt(); // 读取出发站int y = scanner.nextInt(); // 读取目的站int clockwiseDistance = 0; // 顺时针方向的距离int counterClockwiseDistance = 0; // 逆时针方向的距离// 计算顺时针距离// 从出发站到目的站，顺时针方向逐个累加距离for (int i = x - 1; i != y - 1; i = (i + 1) % n) {clockwiseDistance += distances[i];}// 计算逆时针距离// 从目的站到出发站，逆时针方向逐个累加距离for (int i = y - 1; i != x - 1; i = (i + 1) % n) {counterClockwiseDistance += distances[i];}// 输出顺时针和逆时针两种情况下的最短距离System.out.println(Math.min(clockwiseDistance, counterClockwiseDistance));}
}
(i + 1) % n: 是一种常见的操作，用于在循环列表（或环形缓冲区、圆形队列）中循环递增索引。这个操作确保了当索引增加到列表的末尾时，它会自动回到开头，从而实现环形访问。这里是详细解释：
i：当前的索引。i + 1：下一个索引。% n：取模运算符，n是列表的长度。作用
当
i增加时，(i + 1)可能会超过数组的最大索引（即n-1）。为了使索引在超出数组边界时回到起点（形成一个环），使用了取模操作% n。例如：
- 当
i为 0 到n-2时，(i + 1) % n简单地返回i + 1。- 当
i为n-1（即最后一个元素的索引）时，(i + 1) % n返回 0，这样就回到了数组的开头。为了防止顺时针 x到y遇到边界（y在x前时有可能）或者y逆时针走，一定会遇到边界。都需要处理。
如果用逻辑判断的方法：
这个代码使用逻辑判断来处理数组索引超出边界的情况，使得索引在到达数组边界时正确循环。这样，可以计算两个站之间的最短距离。
// 将站的编号转换为数组的索引（转化为从索引x 到 索引 y） -- 这么操作更方便理解
int x = scanner.nextInt(); // 读取出发站的编号（假设从1开始）int y = scanner.nextInt(); // 读取目的站的编号（假设从1开始）// 将站的编号转换为数组的索引（转化为从索引x 到 索引 y）x = x - 1;y = y - 1;int clockwiseDistance = 0; // 初始化顺时针方向的距离int counterClockwiseDistance = 0; // 初始化逆时针方向的距离// 计算顺时针距离// 从出发站开始，按顺时针方向逐个累加距离，// 直到到达目的站。通过判断 i == n 确保索引在数组末尾时回到开头。int i = x;while (i != y) {clockwiseDistance += distances[i];i++;if (i == n) {i = 0; // 超出数组末尾，回到开头}}// 计算逆时针距离// 从目的站开始，按逆时针方向逐个累加距离，直到回到出发站。// 通过判断 i == -1 确保索引在数组开头时回到末尾。i = y;while (i != x) {i--;if (i == -1) {i = n - 1; // 超出数组开头，回到末尾}counterClockwiseDistance += distances[i];}
力扣解法 ：更秒，直接 交换起始地和目的地的位置，再计算相关索引的距离值的和，再比较
class Solution {public int distanceBetweenBusStops(int[] distance, int start, int destination) {// 如果start 在 des后面，交换二者if (start > destination) {int temp = start;start = destination;destination = temp;}int sum1 = 0, sum2 = 0;// 遍历整个distance数组for (int i = 0; i < distance.length; i++) {// 计算从start到destination的总距离if (i >= start && i < destination) { //顺时针总距离sum1 += distance[i];} else { //i < start && i >= destination 逆时针总距离// 计算从destination到start的总距离sum2 += distance[i];}}// 返回从start到destination和从destination到start的距离中较小的值return Math.min(sum1, sum2);}
}
第三题：小美的蛋糕切割
第四题：小美的字符串变换
解题思路
这个问题的需求其实是很明确的，根据题意我们需要做两件事
- 找到所有可以摆列的方式，需要满足x*y=n，假设其中x为小的，那么可以枚举1到k(k*k=n，不需要枚举到n)，找到所有的枚举方式
- 每一个具体的枚举，通过DFS或者BFS的方式，找到其中的联通块数量。具体实现上标记每个位置是否访问，然后从一个方块如果未访问，那么联通块+1然后向四周搜索拓展、标记。
解法一：DFS
import java.util.*;public class Main {// 方法用于计算最小权值，输入为整数n和字符串spublic static int minWeight(int n, String s) {int minW = Integer.MAX_VALUE; // 初始化最小权值为最大整数值// 遍历所有可能的矩阵大小，找到所有满足x*y=n的x和yfor (int i = 1; i * i <= n; i++) {if (n % i == 0) {int x = i;int y = n / i;// 构建矩阵 (情况1: x为行数，y为列数)char[][] matrix = new char[x][y];for (int j = 0; j < x; j++) {for (int k = 0; k < y; k++) {matrix[j][k] = s.charAt(j * y + k); // 将字符串s的字符填入矩阵}}// 计算矩阵的权值并更新最小权值minW = Math.min(minW, countConnected(matrix));// 情况2: 交换x和y的位置x = n / i;y = i;// 构建矩阵matrix = new char[x][y];for (int j = 0; j < x; j++) {for (int k = 0; k < y; k++) {matrix[j][k] = s.charAt(j * y + k); // 将字符串s的字符填入矩阵}}// 计算矩阵的权值并更新最小权值minW = Math.min(minW, countConnected(matrix));}}return minW; // 返回最小权值}// 计算矩阵的连通块数量public static int countConnected(char[][] matrix) {int count = 0; // 初始化连通块计数器boolean[][] visited = new boolean[matrix.length][matrix[0].length]; // 记录访问状态的数组int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向的移动向量// 遍历矩阵的每个元素for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {// 如果该位置未被访问if (!visited[i][j]) {count++; // 连通块计数加一dfs(matrix, visited, directions, i, j); // 执行深度优先搜索}}}return count; // 返回连通块的数量}// 深度优先搜索连通块public static void dfs(char[][] matrix, boolean[][] visited, int[][] directions, int x, int y) {visited[x][y] = true; // 标记为已访问，避免重复计算// 遍历四个方向for (int[] direction : directions) {int nx = x + direction[0];int ny = y + direction[1];// 如果新位置在矩阵范围内且未被访问且与当前字符相同，则递归调用DFSif (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && !visited[nx][ny] && matrix[nx][ny] == matrix[x][y]) {dfs(matrix, visited, directions, nx, ny);}}}// 主方法public static void main(String[] args) {Scanner scanner = new Scanner(System.in); // 创建Scanner对象以读取输入int n = scanner.nextInt(); // 读取整数nscanner.nextLine(); // 读取换行符String s = scanner.nextLine(); // 读取字符串sSystem.out.println(minWeight(n, s)); // 调用minWeight方法并输出结果}
}第五题：小美的树上染色
