5道编程题
2小时
如果您看到哪里有问题，万望 评论区指正，在此谢过 ！！！
第一题：数组遍历
import java.util.Scanner;
public class NextNumbers {
/*
题目：给你一个排列 和两个数 问你：这两个数在排列里是不是相邻
输入：第一行：n 代表排列中数的个数
第二行：a1 -- an 代表排列中的数
第三行：a b 问a和b在排列里是否相邻
输出：Yes或者No
*/
public static void main(String[] args) {
//输入部分：
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
int a = in.nextInt(), b = in.nextInt();
//判断逻辑：
if(nums.length < 2){//特殊情况先排除
System.out.println("No");
return;
}
for(int i = 0; i < n; i++){
if(nums[i] == a){//排列中有a
if((i - 1 >= 0 && nums[i-1] == b) || (i + 1 < n && nums[i + 1] == b)){//b在a的左边或者右边
System.out.println("Yes");
return;
}
}
}
System.out.println("No");
}
}
//测试：
//5
//1 2 3 4 4
//4 3
//Yes
第二题：环形数组遍历
import java.util.Scanner;
public class MinDistance {
/*
题目：环形公路，n个站点，求站点x和y之间的最短距离
输入：第一行 n 代表n和站点
第二行 d1 -- dn 代表相邻站点间的距离
第三行 x y 代表x和y站点
输出：minDistance 代表x和y站点的最短距离
*/
public static void main(String[] args) {
//输入部分：
Scanner in = new Scanner(System.in);
int n = in.nextInt();//站点个数
int[] distance = new int[n];//记录相邻站点的距离
int sumDistance = 0;//输入的同时记录下环形公路总长度
for(int i = 0; i < n; i++){
distance[i] = in.nextInt();
sumDistance += distance[i];
}
int x = in.nextInt(), y = in.nextInt();//求距离的两个站点
//求解部分：
//求出顺时针走的路径长度，总长度-顺时针长度=逆时针长度，再取较小的一个即为答案，输出即可
int distance1 = 0;//顺时针距离
//顺时针走：从下标较小的站点走到下标较大的站点
if(x > y){//保持x<y,即x记录下标较小的站点
int tmp = x;
x = y;
y = tmp;
}
//站点--》数组下标
x--;
y--;
//顺时针从x走到y，计算顺时针距离
for(int i = x; i < y; i++){
distance1 += distance[i];
}
//输出部分：
System.out.println(Math.min(distance1, sumDistance-distance1));//两个方向走的距离取较小的即为所求最短距离
}
}
//测试：
//6
//1 2 3 4 5 6
//1 5
//10
第三题：二维数组分割
import java.util.Scanner;
public class CutCake {
/*
题目：n*m的蛋糕，切一刀，求分成的两部分，总权值的差值 最小是多少
输入：
第一行：n m 代表蛋糕的尺寸，n为行，m为列
接下来n行：m个数，代表本行的m小块各自的权值
输出：权值和的最小差
*/
public static void main(String[] args){
//分析：
//其实不需要关注每个小块的具体权值，主要用的是行和列的权值和
//所以在接收n行m个权值时不必记录下具体权值，直接算出行和列的权值和即可 --》整体思维
//同时计算出总权值和，后面切割后就可以只计算一部分的权值和即可，另一半直接用 总权值-已求出的那一半的权值
//输入部分：
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
long sumWeight = 0;
long[] rowWeight = new long[n], columnWeight = new long[m];
for (int i = 0; i < n; i++){
int rowSum = 0;
for(int j = 0; j < m; j++){
int now = in.nextInt();
columnWeight[j] += now;
rowSum += now;
sumWeight += now;
}
rowWeight[i] = rowSum;
}
//求解部分：
long minDifference = sumWeight;
//按行切 分成上下两部分
long nowSum = 0;
for (int i = 0; i < n - 1; i++){
nowSum += rowWeight[i];//求上半部分权值和
//求两部分权值差值：其中sumWeight - 2*nowSum = (sumWeight - nowSum) - nowSum
minDifference = Math.min(minDifference, Math.abs(sumWeight - 2*nowSum));
}
//按列切 分成左右两部分
nowSum = 0;
for (int i = 0; i < m - 1; i++){
nowSum += columnWeight[i]; //求左半部分权值和
//求两部分权值差值
minDifference = Math.min(minDifference, Math.abs(sumWeight - 2*nowSum));
}
//minDifference不断迭代，现在已经是所求的最小值 输出即可
System.out.println(minDifference);
}
}
//测试：
//输入：
//4 4
//1 2 3 4
//5 6 7 8
//9 10 11 12
//13 14 15 16
//输出：
//16
第四题：字符串转换 + 二维数组dfs
import java.util.Scanner;
public class StrConversion {
/*
题目：给长度为n的字符串str，要求：将该字符串转换成x*y的数组，并求出连通块数的最小值
其中需要n=x*y，连通：字符char的上下左右四个方向的字符与其相等即为联通
例子：给字符串：aababbabb
可以转换成3*3数组：aab
abb
abb
最小连通块数:2
输入：第一行：n 代表字符串长度
第二行：n个小写字母 代表该字符串
输出：最小连通块数
*/
static int[][] nMove = {{0,1},{0,-1},{-1,0},{1,0}};//用于遍历n的上下左右
public static void main(String[] args) {
//分析：1.字符串-->数组 需要求n的约数 可以直接1~n循环判断 判断x是n的约数 则可以完成n=x*y的转换
// 2.计算 当下转换的x*y数组 的连通块数
// 2.1 同一个字符的上下左右四个方向dfs搜索
// 2.2 需要一个辅助数组记录每个位置的字符是否被遍历过了
// 2.3 对不同字符各进行一次dfs遍历直到每个字符都被遍历过，同时统计dfs次数 即为连通块数
// 3.取所有x*y数组的连通块数 最小值
//输入部分：
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str = in.next();
//算法逻辑：
int minCount = n;//记录连通块数的最小值,初始化为最大值,n个字符,连通块数不超过n
//字符串-->数组
for (int i = 1; i < n; i++){
if(n % i != 0) continue;
//可以整除时进行 字符串-->数组 的转换
int len = n / i;//将str转换成 i行len列 的数组
String[] row = new String[i];//按行存 共i行
for(int j = 0; j < i; j++){
row[j] = str.substring(j*len, (j+1)*len); //每行len个字符
}
//计算 i*len数组 的连通块数,并更新目前 连通块数的最小值
minCount = Math.min(minCount, cal(row));//计算连通块数部分的实现 封装到cal()方法中
}
//输出结果：
System.out.println(minCount);
}
private static int cal(String[] row) {
int count = 1;//记录连通块数
int n = row.length, m = row[0].length(); //数组尺寸: n行m列
boolean[][] visited = new boolean[n][m]; //记录n*m数组每个元素是否被遍历过,初始默认为false
//从第一个元素开始,先进行一次dfs遍历, 所以上面count初始化为1
dfs(row, 0, 0, row[0].charAt(0),visited);
//下面遍历visited数组,遇到false 则从该位置代表的字符 进行dfs遍历,并更新连通块数
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!visited[i][j]){
dfs(row,i,j,row[i].charAt(j),visited);
count++;
}
}
}
return count;
}
private static void dfs(String[] arr, int x, int y, char c, boolean[][] visited) {
//主要思想: 从(x, y)开始,沿着上下左右四个方向分别递归dfs
// 跳出递归的条件: 就是当前字符超出数组边界 或者变成其他字符了 或者已经遍历过了
//方向不一定本题中的上下左右,所以可以提出去,方便定义修改, 比如上面封装成nMove[][]数组
int n = arr.length, m = arr[0].length(); //数组尺寸: n行m列
if(x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || c != arr[x].charAt(y)) return;
visited[x][y] = true;
for (int i = 0; i < nMove.length; i++){
// x += nMove[i][0]; //这样做x和y被改变了，错误
// y += nMove[i][1];
// dfs(arr,x,y,c,visited);
// 因为向四个方向走的出发点都是（x, y），所以不能改变x和y的值，只改变传入dfs的参数即可
dfs(arr,x + nMove[i][0],y + nMove[i][1],c,visited);
}
}
}
//测试：
//输入：
// 9
// aababbabb
//输出：
// 2
第五题：树dfs + 动态规划
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class ColorTree {
/*
题目：一棵树 n个节点 每个节点有个权值 初始全是白色
提供哪些节点 相邻的信息
如果两个都是白色的 相邻节点的 权值乘积是完全平方数 则将两个节点涂红色
求该树 最多 多少个节点涂成红色
输入：第一行：n 代表节点个数
第二行：n个整数 代表n个节点各自的权值
接下来n-1行：a b 代表a和b两个节点相邻
输出：红色节点个数的最大值
*/
static long[] weight;
static List<Integer>[] nodes;
static long[] dpWhite;
static long[] dpRed;
public static void main(String[] args){
//分析：
// 1.树-->dfs
// 2.遍历的当前节点now：
// step1：now所有相邻节点 各自为根的子树涂色 --> 需要维护一个动态数组dpWhite[] 表示now涂色前的涂色最大值
// step2：遍历判断now与相邻节点是否满足涂红条件，满足则完成涂色 --> 需要维护一个动态数组dpRed[] 表示now被涂红情况下的涂色最大值
// step3：取dpWhite[now]和dpRed[now]较大的一个，即为以now为根节点的树的涂色最大值
// 3.取dpWhite[0]和dpRed[0]较大的一个，即为所给树的红色节点个数的最大值
//1-输入部分：
Scanner in = new Scanner(System.in);
int n = in.nextInt();
weight = new long[n];
for (int i = 0; i < n; i++){
weight[i] = in.nextLong();
}
nodes = new ArrayList[n];
for (int i = 0; i < n; i++){
nodes[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++){
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
nodes[a].add(b);
nodes[b].add(a);
}
//2-算法逻辑：
dpWhite = new long[n];
dpRed = new long[n];
dfs(0,0);
//3-输出部分：
System.out.println(Math.max(dpWhite[0],dpRed[0]));
}
private static void dfs(int now, int root) {
for (int node: nodes[now]){
if(node != root){
dfs(node,now);
dpWhite[now] += Math.max(dpWhite[node], dpRed[node]);
//理解：本段代表 now节点白色的情况下，以now为根的树涂色最大值 即为now的所有相邻点代表的子树涂色结果的最大值
}
}
for (int node: nodes[now]){
if (node != root && check(weight[now] * weight[node])){
//如果now节点和相邻的node节点满足涂色条件 则需要更新now为红色时其代表的树的涂色结果
dpRed[now] = Math.max(dpRed[now], dpWhite[now] - Math.max(dpRed[node],dpWhite[node]) + dpWhite[node] + 2 );
}
}
}
private static boolean check(long num) {
long tmp = (long) Math.sqrt(num);
return checkSquare(tmp,num) || checkSquare(tmp-1,num) || checkSquare(tmp+1,num);
}
private static boolean checkSquare(long a, long b) {
return a * a == b;
}
}
//测试：
//输入：
// 6
// 1 1 1 1 1 1
// 1 2
// 1 3
// 1 4
// 1 5
// 1 6
//输出：
// 2