华为OD机试 - 空栈压数 - 栈（Java 2024 E卷 100分）

本文主要是介绍华为OD机试 - 空栈压数 - 栈（Java 2024 E卷 100分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

向一个空栈压入正整数，每当压入一个整数时，执行以下规则（设：栈顶至栈底整数依次为n1, n2, …, nx，其中n1为最新压入的整数）

如果 n1 = n2，则 n1, n2 全部出栈，压入新数据 m (m = 2 * n1)
如果 n1 = n2 + … + ny 的范围为 3,n，则 n1, n2, …, ny 全部出栈，压入新数据 m (m = 2 * n1)
如果上述规则均不满足，则不做操作。

如：依次向栈压入 6，1，2，3，

当压入 2 时，栈顶至栈底依次为 2,1,6；
当压入 3 时，3 = 2 + 1，3，2，1 全部出栈，重新入栈整数 6，此时栈顶至栈底依次为 6,6；6 = 6，两个 6 全部出栈，压入 12，最终栈中只剩个元素 12。向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

二、输入描述

使用单个空格隔开的正整数的字符串 Q，如“5678”，左边的数字先入栈。

正整数大小为 [1，2³¹ - 1]
正整数个数为 [1,1000]。

三、输出描述

最终栈中存留的元素值，元素值使用单个空格隔开，从左至右依次为栈顶至栈底的数字。

四、测试用例

测试用例1：

1、输入

10 20 50 80 1 1

2、输出

2 160

测试用例2：

1、输入

5 10 20 50 85 1

2、输出

1 170

五、解题思路

这道题的核心在于使用栈（Stack）来模拟一个逐步压入数字，并根据特定规则进行元素处理的过程。问题要求我们根据输入的数字列表，按照一定的规则对栈进行操作，最后输出栈中的元素。

1、具体步骤如下：

输入解析:
- 从输入字符串中读取一组用空格分隔的正整数。按照顺序将这些整数逐个压入栈中。
栈操作:
- 每次压入一个新数字后，检查是否满足以下两个规则：
- 规则1：如果栈顶两个元素相等，则将这两个元素弹出栈，并将它们的两倍值压入栈中。
- 规则2：如果栈顶元素等于栈中前几个元素之和（范围为3到n），则将这些元素弹出栈，并将栈顶元素的两倍值压入栈中。
- 在每次应用规则后，需要重新检查栈是否满足规则（因为栈的状态可能发生了变化），直到不能再应用规则为止。
结果输出:
- 当所有输入数字都处理完毕，并且不能再应用任何规则时，将栈中的元素按顺序输出。输出的顺序应从栈顶到栈底。

2、算法复杂度分析

（1）时间复杂度:

由于每个元素可能会多次参与规则的匹配，最坏情况下，时间复杂度可以达到 O(n^2)，其中 n 是输入数字的个数。这是因为每次元素的压入可能会触发多个规则匹配和弹出操作，尤其是在规则2中需要遍历栈的部分元素进行求和匹配。

（2）空间复杂度:

空间复杂度主要由栈的使用决定，最坏情况下，需要额外的栈空间来保存所有元素，因此空间复杂度为 O(n)。

六、Java算法源码

public class OdTest01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取输入的数字串，并分割成单个数字的数组String input = sc.nextLine();String[] numbers = input.split(" ");// 使用栈来存放数字Stack<Integer> stack = new Stack<>();// 遍历每个数字并压入栈中for (String num : numbers) {int currentNumber = Integer.parseInt(num); // 将字符串转换为整数stack.push(currentNumber); // 压入栈中// 尝试应用规则1和规则2applyRules(stack); // 对栈应用规则}// 输出最终栈中的内容printStack(stack);}// 对栈应用规则1和规则2private static void applyRules(Stack<Integer> stack) {boolean ruleApplied;// 不断检查直到不能再应用规则do {ruleApplied = false;// 规则1：栈顶两个元素相等if (stack.size() >= 2) {int top1 = stack.pop();int top2 = stack.pop();if (top1 == top2) {int newElement = 2 * top1;stack.push(newElement);ruleApplied = true;} else {stack.push(top2); // 恢复栈的状态stack.push(top1);}}// 规则2：栈顶元素等于前若干元素之和if (!ruleApplied && stack.size() >= 3) {int top1 = stack.pop();int sum = 0;Stack<Integer> tempStack = new Stack<>(); // 临时栈用来保存弹出的元素// 计算前面的若干元素之和while (!stack.isEmpty()) {int element = stack.pop();tempStack.push(element); // 保存到临时栈sum += element;if (sum == top1) {int newElement = 2 * top1;stack.push(newElement); // 压入新元素ruleApplied = true;break;}}// 如果没有应用规则2，则恢复栈的状态if (!ruleApplied) {while (!tempStack.isEmpty()) {stack.push(tempStack.pop());}stack.push(top1);}}} while (ruleApplied); // 如果应用了规则，继续检查}// 按照要求输出栈中的元素private static void printStack(Stack<Integer> stack) {// 按栈顶到栈底的顺序输出while (!stack.isEmpty()) {System.out.print(stack.pop());if (!stack.isEmpty()) {System.out.print(" ");}}}
}

七、效果展示

1、输入

10 20 50 80 1 1

2、输出

2 160

3、说明

压入10:
- 栈：[10]
- 没有规则满足，继续。
压入20:
- 栈：[10, 20]
- 没有规则满足，继续。
压入50:
- 栈：[10, 20, 50]
- 没有规则满足，继续。
压入80:
- 栈：[10, 20, 50, 80]
- 没有规则满足，继续。
压入1:
- 栈：[10, 20, 50, 80, 1]
- 没有规则满足，继续。
再次压入1:
- 栈：[10, 20, 50, 80, 1, 1]
触发规则1：栈顶的两个元素相等（两个1），将它们弹出并将它们的两倍值（2）压入栈中。
- 栈变化为：[10, 20, 50, 80, 2]
触发规则2:
- 现在栈顶元素是2，但没有符合规则2的条件（即没有与2相等的前若干元素的和）。
- 栈保持为：[10, 20, 50, 80, 2]
- 接下来处理栈中的元素以检查是否有符合规则的。
再次触发规则2：
- 栈顶元素是2，无需处理，但栈中有：80、50、20和10，其中，80 = 50 + 20 + 10，满足规则2的条件。
- 弹出80、50、20、10，然后将160（2*80）压入栈中。
- 栈最终变为：[160, 2]
最终栈状态：
- 经过以上步骤操作，栈中元素从栈顶到栈底依次为：2 和 160。