德科华为od机试编程题

3道题，400分，第1、2题，难度1星，各100分，第3题难度2星，200分
牛客网在线，答题时长3h，录屏+录像+手机微信小程序监控
可以开本地idea

牛客网
牛客竞赛: OJ在线编程常见输入输出练习场

总结

之前没有做过编程题，为了做这个，刷了一天牛客网，感觉还是挺有收货的，遇到了很多纯业务上遇不到的问题，所以以后要抽时间多刷刷

1.求字符串出现数字和的最小值，会有负数

字符串格式：a-zA-Z±
示例:abc12ss-123b
最小值：1+2+（-123）= -120

ab0c12ss-123b–1ss+dd–g1g
-120

char类实际工作中比较少用，所以在线用的是笨办法，创建了一个0-9的list来判断是不是数字

java判断是否为数字
Java中char 转化为int 的两种方法

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNextLine()){String input = sc.nextLine();char[] chars = input.toCharArray();// 进入负数领域开关boolean b = false;// 缓存负数String buf = "-";// 结果int sum = 0;for (int i = 0; i < chars.length; i++) {if (Character.isDigit(chars[i])) {if (!b) {// 将char转为int 不能直接强转 对应的会是ascii码sum += Character.getNumericValue(chars[i]);} else {buf += chars[i];}} else {if (b) {if (!"-".equals(buf)) {sum += Integer.parseInt(buf);}b = false;buf = "-";}if ('-' == chars[i]) {b = true;buf = "-";}}}System.out.println(sum);}}
}

2.求坐标轴上画出图形的面积

从(0,0)开始，指定终点x坐标，y轴坐标以偏移量呈现，-表示向下偏移
第1行：n e ，n表示有几组数据，e表示终点坐标
第2-n行：x offsety 每次x都会递增

比如：
3 8
0 1
2 1
4 -4

构成图形：

求得面积：12+2(4-2)+2*(8-4）= 14

只通过了90%的测试用例

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()){// 几组数据int n = sc.nextInt();// x轴终点坐标int e = sc.nextInt();// 结果int sum = 0;int x = 0, y = 0;for (int i = 0; i < n; i++) {int a = sc.nextInt();int b = sc.nextInt();// y轴提供的是偏移量 可以为负if (y != 0){sum += (a-x)*Math.abs(y);}x = a;y = y + b;}if (x < e) {sum += (e-x)*Math.abs(y);}System.out.println(sum);}}
}

3.平分积木重量

有一堆积木，小明和小王兄弟两平方，但小明只认识二进制，而且不会进位（舍掉进位），求最终小王可以获得的最大积木重量
比如：3 5 6
3的二进制：11
5的二进制：101
6的二进制：110
小明的舍掉进位算法
5和6的二进制运算= 011 = 3
所以小王最多可以拿到 5+6 = 11

在线没有做出来，主要是不会写组合算法，所以没有跑测试用例，下面代码也不知道对不对

组合算法Java实现
java获取list集合中最大值最小值
int数组和Integer数组以及List＜Integer＞集合三者的相互转化

组合算法最好不用递归，数据多了，会栈溢出

新解，使用异或运算，且两部分都应该采用异或运算求累计重量

import java.util.*;
import java.util.stream.Collectors;/***  * 舍掉进位算法就是异或算法 ^*  * 计算重量相等时，两部分都要使用舍掉进位求和*/
public class Main{// 输入数据static List<Integer> list = null;// 所有可能结果static List<Integer> result = null;// 输入数据总和static int totalSum = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {// 积木数量int n = sc.nextInt();// 初始化，重置list = new ArrayList<>(n);result = new ArrayList<>();totalSum = 0;for (int i = 0; i < n; i++) {int input = sc.nextInt();list.add(input);totalSum += input;}// 不能取全部数 最少取一个数// 列举出每种取值数量所对应的组合for (int i = 1; i <= n/2; i++) {int[] output = new int[i];dfs(n, output, 0, 0);}if (result.size() == 0) {System.out.println(0);} else {// java.util.NoSuchElementExceptionSystem.out.println(Collections.max(result));}}}/*** 获取指定数量的所有组合* @param num 元素数量（积木数量）* @param output 输出数组* @param index 要填充的output当前下标* @param start 从input第几个下标开始选择*/public static void dfs(int num, int[] output, int index, int start) {if (index == output.length) {compareEquals(output);return;} else {for (int j = start; j < num; j++) {output[index] = j; // 记录选取的元素的下标dfs(num, output, index + 1, j + 1);//选取下一个元素，可选下标区间为[j+1,input.length]}}}/*** 二进制累加求和, 舍掉进位，即异或运算 （同为0，异为1）* 比较分隔的两部分积分重量是否相等*/public static void compareEquals(int[] output) {// int数组转list，list不能存基本数据类型List<Integer> outputList = Arrays.stream(output).boxed().collect(Collectors.toList());int a = 0;int b = 0;// System.out.println("output: " + Arrays.toString(output));for (int i = 0; i < list.size(); i++) {// output里面存的是下标if (outputList.contains(i)) {// 选中a = a^list.get(i);} else {b = b^list.get(i);}}if (a == b && a > 0){int sum = getSum(output);result.add(sum);result.add(totalSum - sum);}}/*** 选中元素之和*/public static int getSum(int[] output){int sum = 0;for(int i = 0; i < output.length; i++){sum += list.get(output[i]);}return sum;}
}

老解：错误，仅记录

import java.util.*;
import java.util.stream.Collectors;public class Main{// 输入数据static List<Integer> list = null;// 对应二进制数据static List<String> abList = null;// 所有可能结果static List<Integer> result = null;// 输入数据总和static int totalSum = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 积木数量int n = sc.nextInt();while (sc.hasNext()) {// 初始化，重置list = new ArrayList<>(n);abList = new ArrayList<>(n);result = new ArrayList<>();totalSum = 0;for (int i = 0; i < n; i++) {int input = sc.nextInt();list.add(input);totalSum += input;}list = list.stream().sorted(Comparator.comparingInt(Integer::intValue).reversed()).collect(Collectors.toList());for (int i = 0; i < n; i++) {abList.add(Integer.toString(list.get(i), 2));}// 最多取全部数 最少取一个数// 列举出每种取值数量所对应的组合for (int i = n; i > 0; i--) {int[] output = new int[i];dfs(n, output, 0, 0);}// System.out.println(result);System.out.println(Collections.max(result));}}/*** 二进制累加求和, 舍掉进位*/public static Integer abSum(int[] output) {String res = abList.get(output[0]);for(int i = 1; i < output.length; i++){res = abAdd(res, abList.get(output[i]));}return Integer.parseInt(res, 2);}/*** 剩下元素之和*/public static int removeSum(int[] output){int sum = 0;for(int i = 0; i < output.length; i++){sum += list.get(output[i]);}return totalSum - sum;}/*** 获取指定数量的所有组合* @param num 元素数量（积木数量）* @param output 输出数组* @param index 要填充的output当前下标* @param start 从input第几个下标开始选择*/public static void dfs(int num, int[] output, int index, int start) {if (index == output.length) {// 计算组合数组之和 舍掉进位int abSum = abSum(output);// 剩下数组之和 十进制直接相加int sum = removeSum(output);if (abSum == sum && sum > 0){// System.out.println("result: " + abSum + " " + sum);// System.out.println(Arrays.toString(output));result.add(totalSum - sum);}return;} else {for (int j = start; j < num; j++) {output[index] = j; // 记录选取的元素的下标dfs(num, output, index + 1, j + 1);//选取下一个元素，可选下标区间为[j+1,input.length]}}}/*** 算法: 二进制相加舍掉进位，比如： 11 + 101 = 110*/public static String abAdd(String a, String b) {int al = a.length();int bl = b.length();String c,d;if (al >= bl){c = a;d = b;} else {c = b;d = a;}al = c.length();bl = d.length();StringBuilder sb = new StringBuilder();for (int i = 0; i < al; i++) {if (i < bl) {char c1 = c.charAt(al - i - 1);char c2 = d.charAt(bl - i - 1);char temp = '0';if (c1 == '0') {temp = c2;} else if (c2 == '0'){temp = c1;}sb.append(temp);} else {sb.append(c.charAt(al - i - 1));}}return sb.reverse().toString();}
}