华为OD刷题C卷 - 每日刷题32（执行任务赚积分，计算三叉搜索树的高度）

1、（执行任务赚积分）：

这段代码是解决“执行任务赚积分”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算在有限的时间内，处理任务可以获得的最多积分。

main方法首先读取任务数量n和可用于处理任务的时间t，然后读取每个任务的最晚处理时间限制和积分值，存储在二维数组wos中。接着，调用getResult方法并打印出可获得的最多积分。

getResult方法首先按任务的最晚处理时间对任务进行升序排序。接着，使用一个ArrayList来维护在当前时间curTime内可以获得的积分列表。遍历所有任务，如果当前时间小于任务的最晚处理时间，则将任务积分添加到列表中，并更新当前时间。如果当前时间已经过了任务的最晚处理时间，则使用列表中的最小积分与当前任务积分进行比较，保留积分较高的任务。

最后，对列表进行排序并只保留最大的t个积分值，计算并返回这些积分值的总和。

2、（计算三叉搜索树的高度）：

这段代码是解决“计算三叉搜索树的高度”的问题。它提供了一个Java类Main，其中包含main方法，以及两个内部类TreeNode和Tree，用于构建三叉搜索树并计算树的高度。

main方法首先读取要插入的数的数量n，然后读取这些数，使用Tree类的add方法将它们按规则插入三叉搜索树中。最后，打印出树的高度。

TreeNode内部类表示树的节点，包含节点值、高度以及指向左右中子树的引用。

Tree内部类包含根节点和树的高度。add方法实现了将新数按照给定规则插入三叉搜索树的逻辑。在插入过程中，同时更新节点的高度和树的当前最大高度。

package OD359;import com.sun.source.tree.Tree;import java.util.*;/*** @description 执行任务赚积分* @level 7* @score 100*//*** 题目描述* 现有N个任务需要处理，同一时间只能处理一个任务，处理每个任务所需要的时间固定为1。* <p>* 每个任务都有最晚处理时间限制和积分值，在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。* <p>* 可用于处理任务的时间有限，请问在有限的时间内，可获得的最多积分。* <p>* 输入描述* 第一行为一个数 N，表示有 N 个任务* <p>* 1 ≤ N ≤ 100* 第二行为一个数 T，表示可用于处理任务的时间* <p>* 1 ≤ T ≤ 100* 接下来 N 行，每行两个空格分隔的整数（SLA 和 V），SLA 表示任务的最晚处理时间，V 表示任务对应的积分。* <p>* 1 ≤ SLA ≤ 100* 0 ≤ V ≤ 100000* 输出描述* 可获得的最多积分*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//有n个任务int n = sc.nextInt();//用于处理任务的时间int t = sc.nextInt();//n个任务的 最晚处理时间 对应积分int[][] wos = new int[n][2];for (int i = 0; i < n; i++) {wos[i][0] = sc.nextInt();wos[i][1] = sc.nextInt();}//可获得的最多积分System.out.println(getResult(t, wos));}//再t时间内可获得的最多积分public static int getResult(int t, int[][] wos) {//按endTime升序排序Arrays.sort(wos, (a, b) -> a[0] - b[0]);//已获得的积分int value = 0;//当前时间int curTime = 0;//存放可能获得的积分ArrayList<Integer> list = new ArrayList<>();//遍历for (int[] wo : wos) {int endTime = wo[0];int score = wo[1];//当curTime<endTime 时，加入if (curTime < endTime) {list.add(score);value += score;curTime++;} else {//当curTime >= endTime时，用list总最小值与当前score比较，放入较大值//总是能存放最大的几个值list.sort((a, b) -> a - b);int min_score = list.get(0);if (score > min_score) {list.remove(0);list.add(score);value += score - min_score;}}}//升序排列list.sort((a, b) -> a - b);//只保留最大的t个值while (list.size() > t) {value -= list.remove(0);}return value;}}

package OD360;import java.util.Scanner;/*** @description 计算三叉搜索树的高度* @level 4* @score 100*/
/*** 题目描述* 定义构造三叉搜索树规则如下：* <p>* 每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。查找的规则是：* <p>* 如果数小于节点的数减去500，则将数插入节点的左子树* 如果数大于节点的数加上500，则将数插入节点的右子树* 否则，将数插入节点的中子树* 给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。* <p>* 输入描述* 第一行为一个数 N，表示有 N 个数，1 ≤ N ≤ 10000* <p>* 第二行为 N 个空格分隔的整数，每个数的范围为[1,10000]* <p>* 输出描述* 输出树的高度（根节点的高度为1）*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//可能有多行输入try-catchint n = sc.nextInt();Tree tree = new Tree();for (int i = 0; i < n; i++) {int val = sc.nextInt();tree.add(val);}System.out.println(tree.tree_height);}//定义树节点static class TreeNode {int val;//节点值int height;//节点高度TreeNode left;//左子树TreeNode mid;//中子树TreeNode right;//右子树//赋值构造方法public TreeNode(int val) {this.val = val;}}//定义三叉树 和添加节点的逻辑static class Tree {//根节点TreeNode root;//数的高度int tree_height;//add方法public void add(int val) {TreeNode node = new TreeNode(val);//如果没有根节点if (this.root == null) {node.height = 1;//根节点高度为1this.root = node;//temp定为root节点this.tree_height = 1;//目前数的高度为1} else {//已存在根节点，则用temp从根节点去逐层比较TreeNode cur = this.root;while (true) {//假设temp是当前cur节点的子节点node.height = cur.height + 1;//更新树的高度this.tree_height = Math.max(this.tree_height, node.height);//如果小于当前节点的数-500，则插入到cur的左子树if (val < cur.val - 500) {//如果没有左子树，则新建左子树，如果有，则更新cur=cur.leftif (cur.left == null) {cur.left = node;//插入后就跳出break;} else {//否则回到while继续搜索cur = cur.left;}} else if (val > cur.val + 500) {//插入右子树if (cur.right == null) {cur.right = node;break;} else {cur = cur.right;}} else {//插入中子树if (cur.mid == null) {cur.mid = node;break;} else {cur = cur.mid;}}}}}}
}