携程2021.3.4 研发笔试
1.表达式解析求解，需要利用栈进行处理
public class expressionStack {
public static void main(String[] args) {
String str = "(- (- (* 4 5 ) 4 6 ) 9)";
System.out.println(resolveString(str));
}
private static int resolveString(String str) {
char[] strArr = str.toCharArray();
Stack<String> stack = new Stack<>();
int i = 0;
//每次最多添加一个字符
while (i < strArr.length) {
if (strArr[i] == ' ') {
i++;
continue;
//处理当前括号内运算
} else if (strArr[i] == ')') {
//因为运算符总是跟在左括号前面，需要使用临时栈来放到临时栈顶
Stack<String> tmpStack = new Stack<>();
String tmp = stack.pop();
while (!"(".equals(tmp)) {
tmpStack.push(tmp);
tmp = stack.pop();
}
tmp = "";
i++;
String operator = tmpStack.pop();
int ans = 0;
switch (operator) {
case "+":
while (!tmpStack.isEmpty()) {
ans += Integer.parseInt(tmpStack.pop());
}
break;
case "-":
ans = Integer.valueOf(tmpStack.pop());
while (!tmpStack.isEmpty()) {
ans -= Integer.parseInt(tmpStack.pop());
}
break;
case "*":
ans = Integer.valueOf(tmpStack.pop());
while (!tmpStack.isEmpty()) {
ans *= Integer.parseInt(tmpStack.pop());
}
break;
}
stack.push(String.valueOf(ans));//计算后的数字添加到栈里
continue;//处理完一个括号内运算后进行下一次循环
}
if (strArr[i] == '(' || strArr[i] == '+' || strArr[i] == '-' || strArr[i] == '*') {
stack.push(String.valueOf(strArr[i++]));
} else {
stack.push(String.valueOf(strArr[i++]));//数字
}
}
return Integer.valueOf(stack.pop());
}
}
2.新春红包礼盒
找到自己能分得红包的最大值，即意味着之前拿到红包的人额度都比自己大，并且尽量不要让他们拿到的额度过大，否则自己分到的就更少。处理逻辑是在treeset中添加n+1个元素，得到最小值，即为自己能拿到的最大值，利用了treeset可以获得头和尾元素的特性，但要处理treeset自带的根据key值去重问题。具体步骤是：
- 添加n+1个元素到treeset中
- 超出大小的元素需要与当前set倒数第二个元素比较，大于则合并set中倒数两个元素，并添加当前元素
- 小于，则合并当前元素+倒数第一个元素，
public class PackageDivided {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = 5;
System.out.println(Arrays.toString(dividePakage(arr, n)));
}
//数组最后一项即为
private static int[] dividePakage(int[] arr, int n) {
TreeSet<Node> set = new TreeSet<>((o1, o2) -> {
if (o2.val != o1.val) {
return o2.val - o1.val;
}
return o2.startIndex - o1.startIndex;
});
for (int i = arr.length - 1; i >= 0; i--) {
if (set.size() <= n) {
set.add(new Node(i, arr[i]));
} else {
Node tail = set.pollLast();
//arr[i]比set倒数第二个元素大,则倒数两项相加合为一项，并添加arr[i]项
if (arr[i] > set.last().val) {
set.add(new Node(set.last().startIndex, set.last().val + tail.val));
set.pollLast();
set.add(new Node(i, arr[i]));
} else {
//arr[i]比set倒数第二个元素小，则最后一项tail.val加arr[i]和最小
set.add(new Node(tail.startIndex, tail.val + arr[i]));
}
}
}
int[] res = new int[n + 1];
int index = 0;
Iterator<Node> iterator = set.iterator();
while (iterator.hasNext()) {
res[index++] = iterator.next().val;
}
return res;
}
//创建Node避免treeset只根据数组值去重
static class Node {
int startIndex;
int val;
public Node(int index, int val) {
this.startIndex = index;
this.val = val;
}
}
}
