当前位置：首页 > news >正文

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

news 2024/9/22 14:20:42

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

题目描述

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

如果 $ n_1 = n_2 $，则 $n_1, n_2 $全部出栈，压入新数 $ m = 2 \times n_1$。
如果 $ n_1 = n_2 + \dots + n_y $（y 的范围为 [3, x])，即 $ n_1, n_2, \dots, n_y $ 全部出栈，压入新数$ m = 2 \times n_1 $。
如果上述规则都不满足，则不做操作。

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

输入描述

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

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

输出描述

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

示例1

输入：
10 20 50 80 1 1输出：
2 160

示例2

输入：
5 10 20 50 85 1输出：
1 170

题解

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

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

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

解题思路

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

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 * n1if (this.len < 0 && this.data[this.len - 1] == num) {this.data[this.len - 1] = num * 2;return;}// 满足 n1 == n2 + ... + nylong sum = 0L;for (int idx = this.len - 1; sum < num && idx >= 0; idx--) {sum += this.data[idx];if (sum == num) {this.data[idx] = num * 2;this.len = idx + 1;return;}}// 不满足上述合并this.data[len++] = num;}public void print() {StringBuilder sb = new StringBuilder();for (int i = len - 1; i >= 0; i--) {sb.append(data[i]).append(' ');}System.out.println(sb.toString());}
}

Python

def push(stack, num):# 如果 n1 == n2 ,压入 m = 2 * n1if stack and stack[-1] == num:stack[-1] = num * 2return# 满足 n1 == n2 + ... + nytotal_sum = 0for idx in range(len(stack) - 1, -1, -1):total_sum += stack[idx]if total_sum == num:stack[idx] = num * 2stack = stack[:idx + 1]return# 不满足上述合并stack.append(num)def main():stack = []# 读入数据input_data = input().strip().split()for num in input_data:push(stack, int(num))# 逆序输出print(" ".join(map(str, reversed(stack))))if __name__ == "__main__":main()

C++

#include <iostream>
#include <vector>using namespace std;;void push(vector<int> &stack, int num) {// 如果 n1 == n2 ,压入 m = 2 * n1if (!stack.empty() && stack.back() == num) {stack[stack.size() - 1] = num * 2;return;}// 满足 n1 == n2 + ... + nylong long sum = 0LL;for (int idx = stack.size() - 1; sum < num && idx >= 0; idx--) {sum += stack[idx];if (sum == num) {stack[idx] = num * 2;stack.resize(idx + 1);return;}}// 不满足上述合并stack.push_back(num);
}int main() {vector<int> stack;// 读入数据int num;while (cin >> num) push(stack, num);for (auto it = stack.rbegin(); it != stack.rend(); it++) {cout << *it << " ";}return 0;
}