空栈压数 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

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

1. 如果 ，则 全部出栈，压入新数 。
2. 如果 （y 的范围为 [3, x])，即 全部出栈，压入新数。
3. 如果上述规则都不满足，则不做操作。

向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

输入描述

一行字符串，包含使用单个空格隔开的正整数，如“5 6 7 8”，左边的数字先入栈。

1. 正整数大小为 [1, 2^31-1]
2. 正整数个数为[1, 1000]

输出描述

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

示例1

输入：
10 20 50 80 1 1

输出：
2 160

示例2

输入：
5 10 20 50 85 1

输出：
1 170

题解

这道题目是关于栈的操作，属于栈模拟类型的算法题。核心是通过栈的特性完成特定规则的数字压入和出栈操作。题目的规则有两个主要分支：

1. 如果栈顶的两个数字相等，则弹出这两个数字，代之以它们的两倍压入栈。
2. 如果栈顶的某些数字之和等于新加入的数字，则将这些数字弹出，压入它们两倍的新数字。

我们可以借助栈的后进先出（LIFO）特点，逐步模拟这些规则。

解题思路

1. 栈模拟：首先初始化一个空栈，从输入的数字序列逐个压入栈中。
2. 处理相等的数字：在每次压入新数字时，检查栈顶两个数字是否相等，如果相等，则将它们合并成新的数字。
3. 处理和等于新数字的情况：如果栈中一部分数字之和等于当前压入的数字，则将这部分数字合并为新的数字压入栈。
4. 输出结果：最终栈中剩余的数字逆序输出即可。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        MyStack stack = new MyStack(1010);
        for (int num : arr) stack.push(num);
        stack.print();
    }
}


class MyStack {
    private int[] data;
    private int len;

    public MyStack(int capatity) {
        this.data = new int[capatity];
        this.len = 0;
    }

    public void push(int num) {
        // 如果 n1 == n2 ,压入 m = 2 * n1
        if (this.len < 0 && this.data[this.len - 1] == num) {
            this.data[this