华为OD刷题C卷 - 每日刷题33（小华最多能得到多少克黄金，智能成绩表）

1、（小华最多能得到多少克黄金）：

这段代码是解决“小华最多能得到多少克黄金”的问题。它提供了一个Java类Main，其中包含main方法和dfs方法，以及辅助变量和getDigitSum方法，用于计算小华在地图上能收集到的最多黄金数量。

main方法首先读取地图的行数m、列数n和数位之和阈值k。然后，初始化访问标记数组isUsed和数位和数组digitSum。调用dfs方法从入口(0, 0)开始收集黄金，并打印出最多能获得的黄金数量。

dfs方法是一个递归函数，用于深度优先搜索所有可达的方格。如果当前方格的横纵坐标数位之和不大于k，并且方格未被访问过，则标记为已访问，并将该方格的黄金计入总数ans。然后，尝试向四个方向（上、下、左、右）移动，继续收集黄金。

getDigitSum方法用于计算从0到n-1每个数的数位之和，存储在数组digitSum中，以便快速检查横纵坐标数位之和。

2、（智能成绩表）：

这段代码是解决“智能成绩表”的问题。它提供了一个Java类Main，其中包含main方法和solution方法，用于根据指定科目的成绩对一群学生进行排序。

main方法首先读取学生人数n、科目数量m和科目名称列表。然后，读取每个学生的姓名和成绩，存储在二维数组student中。接着，读取用于排名的科目名称sort，并调用solution方法进行排序和打印输出。

solution方法首先将学生的姓名和成绩转换为整数数组temp，并使用HashMap来存储姓名与数组索引的映射。然后，根据输入的科目名称sort，使用Arrays.sort方法对数组temp进行排序。如果科目不存在，则按照总分进行排序。排序规则是：首先按照指定科目的成绩降序排序，如果成绩相同，则按照学生姓名的字典顺序排序。

最后，遍历排序后的数组temp，打印出排序后的学生姓名。

package OD361;

import java.util.Scanner;

/**
 * @description 小华最多能得到多少克黄金
 * @level 5
 * @score 100
 */

/**
 * 题目描述
 * 小华按照地图去寻宝，地图上被划分成 m 行和 n 列的方格，横纵坐标范围分别是 [0, n-1] 和 [0, m-1]。
 * <p>
 * 在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标之和大于 k 的方格存在危险不可进入。小华从入口 (0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。
 * <p>
 * 请问小华最多能获得多少克黄金？
 * <p>
 * 输入描述
 * 坐标取值范围如下：
 * <p>
 * 0 ≤ m ≤ 50
 * 0 ≤ n ≤ 50
 * k 的取值范围如下：
 * <p>
 * 0 ≤ k ≤ 100
 * 输入中包含3个字数，分别是m, n, k
 * <p>
 * 输出描述
 * 输出小华最多能获得多少克黄金
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //能取得的黄金数
    static int ans = 0;
    //行 列 设为static 方便dfs中判断边界
    static int m, n, k;
    //标记是否被访问过
    //存放对应下标的数位和
    static int[] digitSum;
    static boolean[][] isUsed;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //行 列 数位和阈值k
        m = sc.nextInt();
        n = sc.nextInt();
        k = sc.nextInt();
        isUsed = new boolean[m][n];
        //存放数位和 长度是m n 最大值的数位和
        digitSum = getDigitSum(Math.max(m, n));
        dfs(0, 0);
        System.out.println(ans);

    }

    //递归
    public static void dfs(int x, int y) {
        //返回上一层标志 下标越界 被使用 数位和超过k
        if (x < 0 || y < 0 || x >= m || y >= n || isUsed[x][y] || digitSum[x] + digitSum[y] > k) {
            return;//返回上一层
        }
        //如果没有返回上一层，说明该位置还没被使用，刷新
        isUsed[x][y] = true;
        ans++;
        //遍历上下左右位置 使用位移偏移数组遍历
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] offset : offsets) {
            int newX = x + offset[0];
            int newY = y + offset[1];
            dfs(newX, newY);
        }
    }

    //存放从0-n-1的数位和数组 下标是数，值是数位和
    public static int[] getDigitSum(int n) {
        int[] temp = new int[n];
        for (int i = 0; i < n; i++) {
            int num = i;
            while (num > 0) {
                temp[i] += num % 10;
                num /= 10;
            }
        }
        return temp;
    }


}

package OD362;

import java.util.*;

/**
 * @description 智能成绩表
 * @level 5
 * @type 动态条件排序、多条件排序
 */

/**
 * 输入描述
 * 第 1 行输入两个整数，学生人数 n 和科目数量 m。
 * <p>
 * 0 < n < 100
 * 0 < m < 10
 * 第 2 行输入 m 个科目名称，彼此之间用空格隔开。
 * <p>
 * 科目名称只由英文字母构成，单个长度不超过10个字符。
 * 科目的出现顺序和后续输入的学生成绩一一对应。
 * 不会出现重复的科目名称。
 * 第 3 行开始的 n 行，每行包含一个学生的姓名和该生 m 个科目的成绩（空格隔开）
 * <p>
 * 学生不会重名。
 * 学生姓名只由英文字母构成，长度不超过10个字符。
 * 成绩是0~100的整数，依次对应第2行种输入的科目。
 * 第n+2行，输入用作排名的科目名称。若科目不存在，则按总分进行排序。
 * <p>
 * 输出描述
 * 输出一行，按成绩排序后的学生名字，空格隔开。成绩相同的按照学生姓名字典顺序排序。
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //学生人数
        int n = sc.nextInt();
        //科目数量
        int m = sc.nextInt();
        List<String> subject = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            //科目名称
            subject.add(sc.next());
        }


        //存放学生姓名、科目成绩
        //如 姓名 语文 数学 英语
        //   张三 100  90  80
        String[][] student = new String[n][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m + 1; j++) {
                student[i][j] = sc.next();
            }
        }
        //按某科目排序
        String sort = sc.next();
        //排序并打印输出
        solution(student, subject, sort);

    }

    //按照科目名字从高到低排序
    public static void solution(String[][] student, List<String> subject, String sort) {
        //新数组，用编号代替名字
        int[][] temp = new int[student.length][student[0].length + 1];
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < student.length; i++) {
            temp[i][0] = i;
            //各学科 和 总分
            for (int j = 1; j < student[0].length; j++) {
                temp[i][j] = Integer.parseInt(student[i][j]);
                temp[i][student[0].length] += temp[i][j];
            }
            //存放名字
            map.put(i, student[i][0]);
        }

        //如果科目sort不存在subject中，则按总分排序
        if (!subject.contains(sort)) {
            int index = temp[0].length - 1;
            Arrays.sort(temp, (o1, o2) -> o2[index] - o1[index] == 0 ? map.get(o1[0]).compareTo(map.get(o2[0])) : o2[index] - o1[index]);
        } else {
            //学科下标0 对应student中下标1
            int index = subject.indexOf(sort) + 1;
            //二维数组按照第i列降序排列
            Arrays.sort(temp, (o1, o2) -> o2[index] - o1[index] == 0 ? map.get(o1[0]).compareTo(map.get(o2[0])) : o2[index] - o1[index]);
        }

        //打印输出
        for (int i = 0; i < temp.length; i++) {
            System.out.print(map.get(temp[i][0]) + " ");
        }
    }
}