给定一组正整数 n
,我们需要按顺序将这些数字逐个加入栈中。但在每次压入数字时,需要根据以下两种情况进行特殊处理:
x
和栈顶元素 y
相同,那么需要取出栈顶元素 y
,并将一个新的数字 x + y
(即 2 * x
)压入栈中。x
和栈顶开始往下的若干个元素(至少 2 个)的和相等,那么需要将这些元素全部取出,并将一个新的数字 2 * x
压入栈中。本题为2023年5月10日华为暑期实习机考原题
华为机考的介绍点击这里
有一个叫做小红的人,他非常喜欢喝茶。他有 x 个奇怪的杯子,每个杯子都可以装入一个正整数。小红决定将这些杯子中的个数字压入一个栈中,但他有些规矩:每次他要向栈中压入一个数字,如果栈顶数字与前一个数字相同,他就会将这两个数字取出来相加,并且将它们的和压入栈中。另外,如果栈顶数字等于前面连续的 y 个数字的和(1 ≤ y ≤ x),他也会将这 y+1 个数字取出来相加,并且将它们的和压入栈中。当然,如果以上两个规则都不满足,他就不会进行任何操作。现在,小红将一组正整数依次压入栈中,请你告诉他最终栈中剩下的数字是什么。
使用单个空格隔开的正整数的字符串,如"5 6 7 8", 左边的数字先入栈。
正整数的范围为[1, 231−1]
正整数个数的范围为[1,1000]。
最终栈中存留的元素值,元素值使用的单个空格隔开,如"8 7 6 5", 从做至右依次为栈顶至栈底的数字。
输入
55 66 121 5 5
输出
10 242
解释:向栈压入 121 时,55 + 66 = 121 ,数据合并后入栈 242 ,压入两个 5 时,合并为 10 ,最终栈顶至栈底的数字为 10 和 242 .
输入
7 5 8 9 3
输出
3 9 8 5 7
解释:无任何整数合并