通过之前几道栈基础题,我们可以总结一个规律: 对于每个元素,需要考虑它前面若干个数的影响时,可以使用栈来解决。
栈1:每一个右括号,需要寻找之前离它最近的左括号
栈2:每一个元素,需要寻找之前连续的两个相同元素
栈3:每一个数x,需要寻找之前连续若干个数的和等于x。
本题为2024年9月19日华为-秋招机考原题
华为机考的介绍点击这里
设计一个程序来处理特定的数组分析问题。
给定一个非负整数数组arr,其中每个整数用其十六进制表示中的数字之和来表示其“权重”(权重计算是基于十六进制表示中每位数字的和,0 ~ 9代表权重0~ 9,权重A:10、B:11、C:12、D:13、E:14、F:15)。
您的任务是找出数组中每个元素右侧第一个具有更大“权重”的元素,并返回一个新的数组,该数组包含这些元素的索引。
如果一个元素的右侧没有更大“权重”的元素,则对应位置返回 −1。
第一行:一个整数 N,表示数组 arr 的大小,0<N<100000
第二行:N 个由空格分隔的非负整数,表示数组 arr,0≤arri≤0xffffffff
一行:N个整数,表示每个元素右侧第一个权重更大的元素的索引,如果不存在则为−1。
输入
3
12 3 24
输出
-1 2 -1
说明
十六进制表示分别为:[C,3,18]
对应的权重分别为:[12,3,1+8=9]
对于第一个元素 12(权重12),其右侧没有更大权重的元素,因此返回 −1
对于第二个元素 3(权重3),其右侧第一个更大权重的元素是24(权重9),位于索引2
对于第三个元素 24(权重9),其不侧没有更大权重的元素,因此返回 −1。
输入
5
15 8 23 42 7
输出
-1 3 3 -1 -1
说明
十六进制表示分别为:[F,8,17,2A,7]。
对应的权重分别为:[15,8,8,2+10=12,7]。
对于第一个元素 15(权重15),其右侧没有更大权重的元素,因此返回 −1。
对于第二个元素8(权重8)和第三个元素 23(权重8),右侧第一个更大权重的元素是 42(权重12),位于索引3。
对于第四个元素 42(权重12)和第五个元素7(权重7),其右侧没有更大权重的元素,因此对应位置返回 −1。