3道题，400分，第1、2题，难度1星，各100分，第3题难度2星，200分
牛客网在线，答题时长3h，录屏+录像+手机微信小程序监控
可以开本地idea
总结
之前没有做过编程题，为了做这个，刷了一天牛客网，感觉还是挺有收货的，遇到了很多纯业务上遇不到的问题，所以以后要抽时间多刷刷
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
在线没有做出来，主要是不会写组合算法，所以没有跑测试用例，下面代码也不知道对不对
组合算法最好不用递归，数据多了，会栈溢出
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();
}
}