华为实习笔试5.6 100%+80%+50% 大家挑挑错

题目见https://www.nowcoder.com/discuss/422885?type=post&order=time&pos=&page=1&channel=

第一题偷鸡的，不贴了

第二题80% 思路就是贪心，先优先考虑费用最高的，如果费用相同就先考虑内存最小的。然后二分查找刚好大于等于他所需内存的服务器

设置boolean数组标记服务器是不是已经被用过了，如果查到的被用过，就再往后搜索没用过且拥有内存最小的服务器。

怀疑是没考虑边界情况，只写了80%，希望有大神挑挑错。

package 华为;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
class order {
    int consume;
    int fee;
    public order(int c, int f) {
        consume=c;
        fee = f;
    }
}
public class 函数调度策略 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] memory = new int[M];
        boolean[] isUsed = new boolean[M];
        for (int i = 0; i < M; i++)
            memory[i] = sc.nextInt();
        Arrays.sort(memory);
        ArrayList arr = new ArrayList(N);
        for (int i = 0; i < N; i++)
            arr.add(new order(sc.nextInt(), sc.nextInt()));
        arr.sort((o1, o2) -> {
            if (o1.fee != o2.fee)
                return o2.fee - o1.fee;
            else
                return o1.consume - o2.consume;
        });
        int idx;
        int notUsed = M;
        long count = 0;
        order o;
        for (int i = 0; i < arr.size() && notUsed != 0; i++) {
            o = arr.get(i);
            idx = searchwithBoolean(memory, isUsed, o.consume);
            if (idx == memory.length) {
                continue;
            }
            isUsed[idx] = true;
            count += o.fee;
        }
        System.out.println(count);
    }

    public static int searchwithBoolean(int[] memory, boolean[] isUsed, int key) {
        int idx = Arrays.binarySearch(memory, key);
        idx = (idx < 0) ? -idx - 1 : idx;
        while (idx < memory.length && isUsed[idx] == true) {
            idx++;
        }
        return idx;
    }
}

第三题 50% 思路就是每次递归返回 不一定包括头节点的最大值 与 一定包括头节点的最大值

每个结点的

• 不一定包括头节点的最大值为：左右结点所有值（左头，左可无头，右头，右可无头）的最大值
• 一定包括头节点的最大值：（左头，右头）的最大值+当前结点的值

感觉思路美问题，最后WA的原因是说下标越界了，但是没找出来什么原因……希望有大佬挑挑错

package 华为;

import java.util.Scanner;

class Node {
    int i;
    Node LeftNode;
    Node RightNode;

    Node(int i, Node l, Node r) {
        this.i = i;
        LeftNode = l;
        RightNode = r;
    }
}

public class 最大阶段路径 {
    public static int[] getN(String s, int beg) {
        boolean isMinus = false;
        if (s.charAt(beg) == '-') {
            isMinus = true;
            beg++;
        }
        StringBuilder sb = new StringBuilder();
        char ch;
        while (beg != s.length() && Character.isDigit(ch = s.charAt(beg))) {
            sb.append(ch);
            beg++;
        }
        int[] arr = new int[2];
        arr[0] = beg;
        arr[1] = isMinus ? -Integer.parseInt(sb.toString()) : Integer.parseInt(sb.toString());
        return arr;
    }// 返回第一个不是数字的下标

    // 输入不带括号的串
    // 返回右括号的位置
    public static int BuildTree(Node root, int beg, String s) {
        //针对只有一个节点的情况，我猜提示越界是因为这个
        if (beg >= s.length())
            return -1;
        int arr[] = getN(s, beg);
        int leftEnd = -1;// 逗号位置
        // 获取左子树
        if (arr[1] != 0) {
            Node left = new Node(arr[1], null, null);
            if (s.charAt(arr[0]) == '(') {
                leftEnd = BuildTree(left, arr[0] + 1, s) + 1; // 因为有右括号
            } else {
                leftEnd = arr[0];
            }
            root.LeftNode = left;
        } else {
            root.LeftNode = null;
            leftEnd = arr[0];
        }
        // 获取右子树
        arr = getN(s, leftEnd + 1);
        int rightEnd = -1;
        if (arr[1] != 0) {
            Node right = new Node(arr[1], null, null);
            if (s.charAt(arr[0]) == '(') {
                rightEnd = BuildTree(right, arr[0] + 1, s) + 1;
            } else {
                rightEnd = arr[0];
            }
            root.RightNode = right;
        } else {
            root.RightNode = null;
            rightEnd = arr[0];
        }
        return rightEnd;
    }

    // 第一个元素是(可以)无头的最大值，第二个元素是必须有头的最大值
    public static int[] maxPath(Node root) {
        if (root == null) {
            return null;
        }
        int[] left = maxPath(root.LeftNode);
        int[] right = maxPath(root.RightNode);
        int[] tmp = new int[2];
        if (left == null && right == null) {
            tmp[0] = root.i;
            tmp[1] = root.i;
        } else if (left == null) {
            tmp = right;
            tmp[1] = tmp[1] + root.i;
        } else if (right == null) {
            tmp = left;
            tmp[1] = tmp[1] + root.i;
        } else {
            tmp[0] = Math.max(Math.max(left[0], left[1]), Math.max(right[0], right[1]));
            tmp[1] = Math.max(left[1], right[1]) + root.i;
        }
        tmp[0] = Math.max(tmp[0], tmp[1]);// 我刚刚出来想了下觉得要加上这个条件，我猜加上这个可以A的
        return tmp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int arr[] = getN(s, 0);
        Node root = new Node(arr[1], null, null);
        BuildTree(root, arr[0] + 1, s);
        int[] tmp = maxPath(root);
        System.out.println(Math.max(tmp[0], tmp[1]));
    }
}
//错误：越界
// -1(3(2,1),4(0,1(3,4))) 测试了下都没错
// -1(3(0,0),-4(-1,1))