华为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-catch
        int 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;//根节点高度为1
                this.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.left
                        if (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;
                        }
                    }
                }
            }
        }
    }
}