华为OD机试C卷“学生排队最小移动次数”Java编程_1到n的n个连续的数字组成一个数组,n为3的倍数 每次按照顺序从数组中取出3个元素,

描述

1 2 3 4 5 6

1 3 2 4 5 6

2 3 1 5 6 4

5 6 4 1 2 3

1 2 4 3 5 6

示例

7 9 8 5 6 4 2 1 3

7 8 9 4 2 1 3 5 6

1

8 9 7 5 6 3 2 1 4

7 8 9 4 2 1 3 5 6

0

算法思路1

1. main 方法中首先使用 Scanner 从标准输入读取两行字符串，分别代表学生目前排队情况和随机抽签分组情况。
2. 将学生排队情况和分组情况分别解析为列表 originList 和列表 groupArr。
3. 对于每个小组，通过遍历学生排队情况，找到属于当前小组的三名学生的位置。具体实现如下：
   • 获取当前小组的第一个学生在学生排队情况中的位置 first，第二个学生和第三个学生的位置类似计算。 
   • 在分组情况列表 groupArr 中找到与当前小组相对应的行 row，并遍历当前行，判断当前小组的学生是否已经相邻。
   • 如果相邻，则不需要调整；否则，需要调整学生的位置，使它们相邻。
4. 在调整学生的位置时，分为以下三种情况：
   • 如果第二个学生和第三个学生已经相邻，则不需要调整。
   • 如果只有第二个学生相邻，则需要调整一次，将第一个学生移到第三个学生之后。
   • 如果两个学生都不相邻，则需要调整两次，将第一个学生移到第二个学生之后，将第三个学生移到第二个学生之后。
5. 最后，根据调整的次数，计算出最少需要调整的次数，并输出结果。

答案1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line;
        while (scanner.hasNextLine()) {
            line = scanner.nextLine();
            String[] tokens = line.split(" ");
            int groupNum = tokens.length / 3;//分组数量，每个分组包含三个元素
            List<Integer> originList = new ArrayList<>();//用于存储学生当前排队情况
            for (String token : tokens) {
                originList.add(Integer.parseInt(token));
            }
 
            line = scanner.nextLine();//读取下一行输入，并将其赋值给变量 line。
            tokens = line.split(" ");
            List<int[]> groupArr = new ArrayList<>();//用于存储学生的分组情况
            for (int i = 0; i < groupNum; i++) {//循环遍历每个分组
                groupArr.add(new int[]{//将每个分组的三个学生编号作为一个整数数组添加到 groupArr 中。
                        Integer.parseInt(tokens[i * 3]),
                        Integer.parseInt(tokens[i * 3 + 1]),
                        Integer.parseInt(tokens[i * 3 + 2])
                });
            }
 
            int result = 0;//用于记录调整次数
            for (int i = 0; i < groupNum; i++) {//循环遍历每个分组，进行学生位置调整
                int first = originList.get(i * 3);//当前小组的第一个学生在学生排队情况中的位置
                int second = originList.get(i * 3 + 1);//当前小组的第二个学生在学生排队情况中的位置
                int third = originList.get(i * 3 + 2);//当前小组的第三个学生在学生排队情况中的位置
                int row = 0;
                for (; row < groupNum; row++) {//再次遍历 groupArr，找到包含当前小组第一个学生的小组，并记录该小组的索引为 row
                    if (groupArr.get(row)[0] == first || groupArr.get(row)[1] == first || groupArr.get(row)[2] == first) {
                        break;
                    }
                }
                if (exist_2(groupArr.get(row), second, third)) {//如果第二个学生和第三个学生已经与第一个学生在同一组，则不需要调整。
                    continue;
                } else if (exist_1(groupArr.get(row), second)) {//检查第二个学生是否在当前小组中。
                    //如果第二个学生在当前小组中，则说明第三个学生与第二个学生不相邻，需要进行调整。
                    //如果第二个学生不在当前小组中，则说明第二个和第三个学生都不在当前小组中，无需调整。
                    result++;
                    int tmpNum = find_1(groupArr.get(row), first, second);//查找当前小组中不是第一个和第二个学生的学生，将其记录为 tmpNum
                    originList.remove(Integer.valueOf(tmpNum));//Integer.valueOf(tmpNum) 是将一个基本数据类型 int 转换为对应的包装类 Integer 的方法。
                    // 在这段代码中，tmpNum 是一个基本数据类型 int，而 originList 是一个列表，它存储的是 Integer 对象而不是基本数据类型。
                    // 因此，为了使用 remove 方法从列表中移除特定的元素，需要将 tmpNum 转换为 Integer 对象。这就是使用 Integer.valueOf(tmpNum) 的作用。
                    originList.add(i * 3 + 2, tmpNum);//将其插入到当前小组的第三个位置之后（i * 3 + 2）。
                } else {//如果两个学生都不相邻，则需要调整两次，将第一个学生移到第二个学生之后，将第三个学生移到第二个学生之后。
                    result += 2;
                    int[] tmpArr = find_2(groupArr.get(row), first);
                    for (int j = 0; j < 2; j++) {
                        int tmpNum = tmpArr[j];
                        originList.remove(Integer.valueOf(tmpNum));
                        originList.add(i * 3 + j + 1, tmpNum);
                    }
                }
            }
            System.out.println(result);
        }
        scanner.close();
    }
 
    static boolean exist_1(int[] arr, int num) {//用于判断给定的整型数组中是否存在指定的元素 num。
        for (int j : arr) {
            if (j == num) {
                return true;
            }
        }
        return false;
    }
 
    static boolean exist_2(int[] arr, int num1, int num2) {//用于判断给定的整型数组中是否同时存在指定的两个元素 num1 和 num2。
        boolean exist1 = false;
        boolean exist2 = false;
        for (int j : arr) {
            if (!exist1 && j == num1) {
                exist1 = true;
            }
            if (!exist2 && j == num2) {
                exist2 = true;
            }
            if (exist1 && exist2) {
                break;
            }
        }
        return exist1 && exist2;
    }
 
    static int find_1(int[] arr, int num1, int num2) {//用于在给定的整型数组中查找不等于指定的两个元素 num1 和 num2 的元素。
        for (int j : arr) {
            if (j != num1 && j != num2) {
                return j;
            }
        }
        return -1;
    }
 
    static int[] find_2(int[] arr, int num) {//用于在给定的整型数组中查找不等于指定元素 num的元素。
        int[] result = new int[2];
        int j = 0;
        for (int i : arr) {
            if (i != num) {
                result[j++] = i;
            }
        }
        return result;
    }
}

详解1

• void add(int index, E element)：在指定位置插入元素。List 接口的 add 方法在指定位置插入元素时，会将该位置原来的元素及其之后的元素向后移动一个位置，以便为新元素腾出空间。
• 举个例子，假设原来的列表为 [1, 2, 3, 4, 5]，现在要在位置 2 插入元素 10，那么操作后的列表将变为 [1, 10, 2, 3, 4, 5]