携程2021.3.4 研发笔试

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.新春红包礼盒

1. 添加n+1个元素到treeset中
2. 超出大小的元素需要与当前set倒数第二个元素比较，大于则合并set中倒数两个元素，并添加当前元素
3. 小于，则合并当前元素+倒数第一个元素，

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;
		}
	}
}