4 solutions
-
1
#include <iostream> #include <vector> #include <stack> using namespace std; int ten_to_six(int n){ int sum=0; while (n>0) { sum+=n%16; n/=16; } return sum; } int main(){ int n; cin>>n; vector<int> num(n); for (int i=0; i<n; i++) { cin>>num[i]; } vector<int> weight(n); for (int i=0; i<n; i++) { weight[i]=ten_to_six(num[i]); } stack<int> s; vector<int> res(n,-1); for(int i=0;i<n;i++){ while (!s.empty()&&weight[i]>weight[s.top()]) { res[s.top()]=i; s.pop(); } s.push(i); } for (int i=0; i<n; i++) { if(i!=0){ cout<<" "; } cout<<res[i]; } } -
0
n = int(input()) data = list(map(int,input().split())) def quanzhong(num): hex_num = hex(num) #bin（）转换为二进制，oct()转换为8进制，hex（）转换为16进制 hex_num = hex_num[2:] result = 0 for i in range(len(hex_num)): if hex_num[i] == 'a': result += 10 elif hex_num[i] == 'b': result += 11 elif hex_num[i] == 'c': result += 12 elif hex_num[i] == 'd': result += 13 elif hex_num[i] == 'e': result += 14 elif hex_num[i] == 'f': result += 15 else: result += int(hex_num[i]) return result qz = [0]*n res = [-1]*n stack = [] for i in range(n): qz[i] = quanzhong(data[i]) while stack and qz[stack[-1]]<qz[i]: index = stack.pop() res[index] = i stack.append(i) print(*res) -
0
TaZi
@ 2024-9-20 10:07:47
题面解释:
题目要求设计一个程序来处理一个非负整数数组的分析。给定数组中的每个整数，我们需要计算其在十六进制表示中的“权重”，即每个数字之和（0-9代表其权重为0-9，A-F分别代表权重10-15）。然后，对于数组中每个元素，我们要找到其右侧第一个权重更大的元素，并返回该元素的索引。如果没有这样的元素，返回-1。
类似的题目:
思路:单调栈
计算每个元素的“权重”（基于其十六进制表示中各位数字的和），然后找出每个元素右侧第一个具有更大“权重”的元素的索引。如果不存在，则返回 -1。
我们可以使用单调栈来高效地解决这个问题。使用单调栈从右向左遍历数组，计算每个元素的权重并记录其右侧第一个更大权重元素的索引，不存在则为-1。
题解
我们需要解决的问题是，给定一个非负整数数组，我们需要计算每个元素在十六进制表示中的“权重”，即所有数字之和。接着，找出每个元素右侧第一个具有更大“权重”的元素的索引。如果没有这样的元素，返回-1。
权重计算
权重的计算基于十六进制的表示，十六进制数字0-9的权重分别为0-9，而A-F的权重分别为10-15。我们可以通过位运算高效地计算权重。具体而言，利用位运算获取每个数字的值并累加起来。
使用单调栈的思路
为了找到每个元素右侧第一个权重更大的元素，我们可以使用单调栈的策略：
- 从右到左遍历数组。
- 使用栈来存储元素的索引，保持栈内元素的权重递减的特性。
- 遍历过程中，对于当前元素，弹出所有权重小于或等于当前元素的索引，这样栈顶的元素就是右侧第一个更大权重的元素。
- 如果栈为空，说明右侧没有更大权重的元素，返回-1；否则返回栈顶元素的索引。
这种方法的时间复杂度为O(N)，因为每个元素最多被入栈和出栈一次，非常高效。
代码
Python
def compute_weight(n): """计算整数 n 的十六进制表示中各位数字的和""" if n == 0: return 0 s = 0 while n > 0: digit = n & 0xF # 获取最低四位，即一个十六进制数字 s += digit n >>= 4 # 右移四位，处理下一个十六进制数字 return s def main(): import sys # 读取第一个输入，数组的大小 N N = int(input()) # 读取第二行的 N 个整数 arr = list(map(int, input().split())) # 确保读取的数组长度与 N 一致 if len(arr) != N: print("输入的数组长度与指定的 N 不一致。") return # 计算每个元素的权重 weights = [compute_weight(num) for num in arr] # 初始化答案数组，默认所有位置为 -1 answer = [-1] * N stack = [] # 栈中存储的是元素的索引 # 从右到左遍历数组 for i in range(N-1, -1, -1): # 弹出栈中所有权重小于或等于当前元素权重的元素 while stack and weights[stack[-1]] <= weights[i]: stack.pop() # 如果栈不为空，栈顶元素就是右侧第一个权重更大的元素 if stack: answer[i] = stack[-1] else: answer[i] = -1 # 将当前元素的索引压入栈中 stack.append(i) # 输出结果，以空格分隔 print(' '.join(map(str, answer))) if __name__ == "__main__": main()cpp
#include <bits/stdc++.h> using namespace std; // 函数用于计算整数 n 的十六进制表示中各位数字的和 int compute_weight(unsigned int n) { if (n == 0) return 0; // 如果 n 为 0，权重为 0 int sum = 0; // 初始化权重和 while (n > 0) { sum += (n & 0xF); // 获取最低四位（十六进制的最后一位） n >>= 4; // 右移四位，处理下一个十六进制位 } return sum; // 返回计算得到的权重 } int main(){ ios::sync_with_stdio(false); // 提高输入输出效率 cin.tie(0); // 解除 cin 和 cout 的绑定，进一步提高效率 int N; cin >> N; // 读取数组大小 vector<unsigned int> arr(N); // 初始化数组 for(int i = 0; i < N; ++i){ cin >> arr[i]; // 读取数组元素 } // 计算每个元素的权重 vector<int> weights(N); for(int i = 0; i < N; ++i){ weights[i] = compute_weight(arr[i]); // 计算并存储权重 } // 初始化答案数组，默认所有位置为 -1 vector<int> answer(N, -1); // 使用栈存储索引 stack<int> st; // 从右到左遍历 for(int i = N - 1; i >= 0; --i){ // 弹出栈中所有权重小于或等于当前元素的索引 while(!st.empty() && weights[st.top()] <= weights[i]){ st.pop(); // 弹出不满足条件的元素 } // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素 if(!st.empty()){ answer[i] = st.top(); // 记录结果 } // 将当前元素的索引压入栈中 st.push(i); } // 输出结果 for(int i = 0; i < N; ++i){ if(i > 0) cout << ' '; // 在输出前加空格 cout << answer[i]; // 输出结果 } cout << '\n'; // 输出换行符 return 0; // 程序结束 }java
import java.io.*; import java.util.*; public class Main { // 函数用于计算整数 n 的十六进制表示中各位数字的和 public static int computeWeight(long n){ if(n == 0) return 0; int sum = 0; while(n > 0){ sum += (n & 0xF); n >>=4; } return sum; } public static void main(String[] args) throws IOException { // 使用 BufferedReader 和 BufferedWriter 提高输入输出效率 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; // 读取第一个输入，数组的大小 N int N = Integer.parseInt(br.readLine()); // 读取第二行的 N 个整数 st = new StringTokenizer(br.readLine()); long[] arr = new long[N]; for(int i=0; i<N; i++){ arr[i] = Long.parseUnsignedLong(st.nextToken()); } // 计算每个元素的权重 int[] weights = new int[N]; for(int i=0; i<N; i++){ weights[i] = computeWeight(arr[i]); } // 初始化答案数组，默认所有位置为 -1 int[] answer = new int[N]; Arrays.fill(answer, -1); // 使用栈存储索引 Deque<Integer> stack = new ArrayDeque<>(); // 从右到左遍历数组 for(int i=N-1; i>=0; i--){ // 弹出栈中所有权重小于或等于当前元素的索引 while(!stack.isEmpty() && weights[stack.peek()] <= weights[i]){ stack.pop(); } // 如果栈不为空，栈顶元素就是右侧第一个更大权重的元素 if(!stack.isEmpty()){ answer[i] = stack.peek(); } // 将当前元素的索引压入栈中 stack.push(i); } // 构建输出结果 StringBuilder sb = new StringBuilder(); for(int i=0; i<N; i++){ sb.append(answer[i]); if(i != N-1){ sb.append(' '); } } sb.append('\n'); bw.write(sb.toString()); bw.flush(); } }
wangxuehui
LV 9
@ 2024-9-22 17:11:41
- 1