华为OD刷题C卷 - 每日刷题36（剩余银饰的重量，最大坐标值、小明的幸运数）

1、（剩余银饰的重量）：

这段代码是解决“剩余银饰的重量”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算经过一系列熔化过程后剩余银饰的重量。

main方法首先读取银饰的个数n，然后读取每个银饰的重量并存储到LinkedList中。接着，调用getResult方法并打印最终剩余银饰的重量。

getResult方法首先对银饰重量进行升序排序。然后，使用循环每次从列表末尾移除三个最重的银饰，并根据题目描述计算熔化后剩余的银饰重量。如果存在剩余，则将这个重量插入到已排序的列表中。这个过程一直重复，直到列表中的银饰数量少于三个。

最后，根据列表中的银饰数量，返回剩余银饰的重量。如果剩余两块，则返回较重的那块的重量；如果只剩下一块，则返回那块的重量；如果没有剩余，则返回0。

2、（最大坐标值、小明的幸运数）：

这段代码是解决“最大坐标值、小明的幸运数”的问题。它提供了一个Java类Main，其中包含main方法和getMaxCoordinate方法，用于计算小明在游戏中达到的最大坐标值。

main方法首先读取指令的总数n，然后读取幸运数m和n个指令。接着，调用getMaxCoordinate方法并打印小明在游戏中达到的最大坐标值。

getMaxCoordinate方法首先进行异常检查，确保输入的幸运数和指令在合理的范围内。然后，使用一个ArrayList来存储小明每一步的坐标值。遍历指令序列，根据指令和幸运数更新当前坐标值，并将每一步的坐标值存储到列表中。

最后，对坐标值列表进行降序排序，并返回列表中的第一个元素，即小明达到的最大坐标值。

package OD367;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @description 剩余银饰的重量
 * @level 4
 * @score 100
 * @type 二分查找
 */

/**
 * 题目描述
 * 有 N 块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。
 * <p>
 * 每一回合，从中选出三块最重的银饰，然后一起熔掉。
 * <p>
 * 假设银饰的重量分别为 x 、y和z，且 x ≤ y ≤ z。那么熔掉的可能结果如下：
 * <p>
 * 如果 x == y == z，那么三块银饰都会被完全熔掉；
 * 如果 x == y 且 y != z，会剩余重量为 z - y 的银块无法被熔掉；
 * 如果 x != y 且 y == z，会剩余重量为 y - x 的银块无法被熔掉；
 * 如果 x != y 且 y != z，会剩余重量为 z - y 与 y - x 差值 的银块无法被熔掉。
 * 最后，
 * <p>
 * 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
 * 如果只剩下一块，返回该块的重量
 * 如果没有剩下，就返回 0
 * 输入描述
 * 输入数据为两行：
 * <p>
 * 第一行为银饰数组长度 n，1 ≤ n ≤ 40，
 * 第二行为n块银饰的重量，重量的取值范围为[1，2000]，重量之间使用空格隔开
 * 输出描述
 * 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；
 * <p>
 * 如果只剩下一块，返回该块的重量；
 * <p>
 * 如果没有剩下，就返回 0。
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //银饰个数
        int n = sc.nextInt();
        //n块银饰的重量 使用LinkedList方便排序和插入
        LinkedList<Integer> weight = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            weight.add(sc.nextInt());
        }
        System.out.println(getResult(weight));

    }

    //计算剩余银饰
    public static int getResult(LinkedList<Integer> weight) {
        //int res = 0;
        //升序排列，每次从最后取三个
        weight.sort(Integer::compareTo);
        //如果剩余银饰>=3个，则每次取后三个
        while (weight.size() >= 3) {
            int z = weight.removeLast();
            int y = weight.removeLast();
            int x = weight.removeLast();
            //取出差值
            // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
            // 如果 x == y && y != z，那么下面公式结果：remain = z - y
            // 如果 x != y && y == z，那么下面公式结果：remain = y - x
            // 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
            int remain = Math.abs((z - y) - (y - x));
            //如果有剩余，则把剩余的银饰插入到原升序列表中
            if (remain != 0) {
                //如果 remain 被找到，返回值是它在列表中的索引。
                //如果 remain 没有被找到，返回值是它应该插入的位置，以便保持列表的排序顺序。
                //这个值通常是在列表中的一个负数，其绝对值表示 remain 应该插入到的位置的索引。具体来说，-(insertion point + 1)。
                int index = Collections.binarySearch(weight, remain);
                if (index < 0) {
                    index = -(index + 1);
                }
                //插入到index位置
                weight.add(index, remain);
            }
        }
        //如果剩两个，返回较大值
        if (weight.size() == 2) {
            return Math.max(weight.get(0), weight.get(1));
        } else if (weight.size() == 1) {
            return weight.get(0);
        } else {
            //没有剩，则返回0
            return 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

package OD368;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @description 最大坐标值、小明的幸运数
 * @level 3
 * @score 100
 */

/**
 * 题目描述
 * <p>
 * 小明在玩一个游戏，游戏规则如下：
 * 在游戏开始前，小明站在坐标轴原点处（坐标值为0）.
 * 给定一组指令和一个幸运数，每个指令都是一个整数，小明按照指令前进指定步数或者后退指定步数。前进代表朝坐标轴的正方向走，后退代表朝坐标轴的负方向走。
 * 幸运数为一个整数，如果某个指令正好和幸运数相等，则小明行进步数+1。
 * <p>
 * 例如：
 * <p>
 * 幸运数为3，指令为[2,3,0,-5]
 * <p>
 * 指令为2，表示前进2步；
 * <p>
 * 指令为3，正好和幸运数相等，前进3+1=4步；
 * <p>
 * 指令为0，表示原地不动，既不前进，也不后退。
 * <p>
 * 指令为-5，表示后退5步。
 * <p>
 * 请你计算小明在整个游戏过程中，小明所处的最大坐标值。
 * <p>
 * 输入描述
 * 第一行输入1个数字，代表指令的总个数 n（1 ≤ n ≤ 100）
 * <p>
 * 第二行输入1个数字，代表幸运数m（-100 ≤ m ≤ 100）
 * <p>
 * 第三行输入n个指令，每个指令的取值范围为：-100 ≤ 指令值 ≤ 100
 * <p>
 * 输出描述
 * 输出在整个游戏过程中，小明所处的最大坐标值。异常情况下输出：12345
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //指令总数
        int n = sc.nextInt();
        //幸运数
        int luck = sc.nextInt();
        //指令序列
        int[] command = new int[n];
        for (int i = 0; i < n; i++) {
            command[i] = sc.nextInt();
        }
        System.out.println(getMaxCoordinate(command, luck));
    }

    //返回最大坐标，异常返回12345
    public static int getMaxCoordinate(int[] command, int luck) {
        //异常
        if (luck < -100 || luck > 100 || command == null || command.length == 0 || command.length > 100) {
            return 12345;
        }
        //指令范围：-100~100
        for (int i : command) {
            if (i < -100 || i > 100) {
                return 12345;
            }
        }

        List<Integer> list = new ArrayList<>();
        list.add(0);
        int now = 0;
        //步数分正负，负数幸运值的话就是多—1
        for (int i = 0; i < command.length; i++) {
            if (command[i] == luck && luck > 0) {
                now += command[i] + 1;
                list.add(now);
            } else if (command[i] == luck && luck < 0) {
                now += command[i] - 1;
                list.add(now);
            } else {
                //包括command[i]=luck=0的情况，不用多走一步
                now += command[i];
                list.add(now);
            }
        }
        list.sort((a, b) -> b - a);
        return list.get(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94