华为实习笔试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))#华为实习##笔试题目##华为#