华为OD机试真题 - 支持优先级队列 (C++ Python JAVA JS GO)
支持优先级队列
2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解
题目描述
实现一个支持优先级的队列，高优先级先出队列；同优先级时先进先出。
如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。
队列存储的数据内容是一个整数。
输入描述
一组待存入队列的数据 (包含内容和优先级)
备注
不用考虑输入数据不合法的情况，测试数据不超过100个
输出描述
队列的数据内容(优先级信息输出时不再体现)
用例1
输入
(10,1),(20,1),(30,2),(40,3)输出
40,30,10,20说明
输入样例中，向队列写入了4个数据，每个数据由数据内容和优先级组成。
数据40的优先级最高，所以最先输出，其次是30;10和20优先级相同，所以按输入顺序输出。
用例2
输入
(10,1),(10,1),(30,2),(40,3)输出
40,30,10说明
输入样例中，向队列写入了4个数据，每个数据由数据内容和优先级组成。
数据40的优先级最高，所以最先输出，其次是30;
两个10和10构成重复数据，被丢弃一个。
题解
思路：模拟
- 使用哈希表按优先级分类存储每个优先级顺序出现数字的数组。
- 至于每个优先级出现的数字去重可以使用一个哈希表按优先级分类保存一个集合用于去重。
- 接下里就是正常处理，这部分比较简单可以参照下面逻辑。
- 然后高优先级的数组先输出，低优先级数组后输出就行。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> #include<set> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<string> split(const string& str, const string& delimiter) { vector<string> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(str.substr(start, end - start)); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } int main() { string input; getline(cin, input); // 解析输入,(10,1),(20,1),(30,2) = > 10,1),(20,1),(30,2 input = input.substr(1, input.size() - 2); vector<string> num = split(input, "),("); // 记录出现过的优先级 set<int> priority; // 记录同一优先级按顺序出现数字 map<int, vector<int>> priorityNum; // 记录同一优先级已经出现数字 map<int, set<int>> priorityCountNum; int n = num.size(); for (int i = 0; i < n; i++) { string st = num[i]; vector<string> tmp = split(st, ","); int value = stoi(tmp[0]); int pri = stoi(tmp[1]); priority.insert(pri); // 已经存在,跳过 if (priorityCountNum[pri].count(value)) { continue; } priorityCountNum[pri].insert(value); priorityNum[pri].push_back(value); } vector<int> priorityArr(priority.begin(), priority.end()); // 降序 sort(priorityArr.rbegin(), priorityArr.rend()); vector<int> result; // 记录结果输出顺序 for (int i = 0; i < priorityArr.size(); i++) { int priority = priorityArr[i]; for (auto& value : priorityNum[priority]) { result.push_back(value); } } // 输出结果 for (int i = 0; i < result.size(); i++) { if (i !=0) { cout << ","; } cout << result[i]; } return 0; }JAVA
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); // 去掉首尾括号 input = input.substring(1, input.length() - 1); // 按 "),(" 分割 String[] parts = input.split("\\),\\("); // 记录出现过的优先级 Set<Integer> prioritySet = new HashSet<>(); // 记录同一优先级下按顺序出现的数字 Map<Integer, List<Integer>> priorityNum = new HashMap<>(); // 记录同一优先级下已经出现过的数字（去重） Map<Integer, Set<Integer>> priorityCountNum = new HashMap<>(); for (String part : parts) { String[] tmp = part.split(","); int value = Integer.parseInt(tmp[0]); int pri = Integer.parseInt(tmp[1]); prioritySet.add(pri); priorityCountNum.putIfAbsent(pri, new HashSet<>()); priorityNum.putIfAbsent(pri, new ArrayList<>()); // 已出现过则跳过 if (priorityCountNum.get(pri).contains(value)) { continue; } priorityCountNum.get(pri).add(value); priorityNum.get(pri).add(value); } // 优先级降序排列 List<Integer> priorityArr = new ArrayList<>(prioritySet); priorityArr.sort(Collections.reverseOrder()); // 输出结果 StringBuilder sb = new StringBuilder(); boolean first = true; for (int pri : priorityArr) { for (int value : priorityNum.get(pri)) { if (!first) sb.append(","); sb.append(value); first = false; } } System.out.println(sb.toString()); } }Python
importsysdefmain():input_str=sys.stdin.readline().strip()# 去掉首尾括号input_str=input_str[1:-1]# 按 "),(" 分割parts=input_str.split("),(")# 记录出现过的优先级priority_set=set()# 记录同一优先级按顺序出现的数字priority_num={}# 记录同一优先级已出现的数字（去重）priority_count_num={}forpartinparts:value_str,pri_str=part.split(",")value=int(value_str)pri=int(pri_str)priority_set.add(pri)ifprinotinpriority_num:priority_num[pri]=[]priority_count_num[pri]=set()# 已出现过则跳过ifvalueinpriority_count_num[pri]:continuepriority_count_num[pri].add(value)priority_num[pri].append(value)# 优先级降序priority_arr=sorted(priority_set,reverse=True)# 输出结果result=[]forpriinpriority_arr:result.extend(priority_num[pri])print(",".join(map(str,result)))if__name__=="__main__":main()JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput='';rl.on('line',line=>{input=line.trim();});rl.on('close',()=>{// 去掉首尾括号input=input.substring(1,input.length-1);// 按 "),(" 分割constparts=input.split("),(");// 记录出现过的优先级constprioritySet=newSet();// 同一优先级下的数字（保持顺序）constpriorityNum=newMap();// 同一优先级已出现的数字（去重）constpriorityCountNum=newMap();for(constpartofparts){const[valueStr,priStr]=part.split(",");constvalue=Number(valueStr);constpri=Number(priStr);prioritySet.add(pri);if(!priorityNum.has(pri)){priorityNum.set(pri,[]);priorityCountNum.set(pri,newSet());}// 已出现过则跳过if(priorityCountNum.get(pri).has(value)){continue;}priorityCountNum.get(pri).add(value);priorityNum.get(pri).push(value);}// 优先级降序constpriorityArr=Array.from(prioritySet).sort((a,b)=>b-a);// 输出结果letresult=[];for(constpriofpriorityArr){result.push(...priorityNum.get(pri));}console.log(result.join(","));});Go
packagemainimport("bufio""fmt""os""sort""strings")funcmain(){in:=bufio.NewReader(os.Stdin)input,_:=in.ReadString('\n')input=strings.TrimSpace(input)// 去掉首尾括号input=input[1:len(input)-1]// 按 "),(" 分割parts:=strings.Split(input,"),(")// 记录出现过的优先级prioritySet:=make(map[int]bool)// 记录同一优先级按顺序出现的数字priorityNum:=make(map[int][]int)// 记录同一优先级已出现的数字（去重）priorityCountNum:=make(map[int]map[int]bool)for_,part:=rangeparts{tmp:=strings.Split(part,",")varvalue,priintfmt.Sscanf(tmp[0],"%d",&value)fmt.Sscanf(tmp[1],"%d",&pri)prioritySet[pri]=trueif_,ok:=priorityNum[pri];!ok{priorityNum[pri]=[]int{}priorityCountNum[pri]=make(map[int]bool)}// 已出现过则跳过ifpriorityCountNum[pri][value]{continue}priorityCountNum[pri][value]=truepriorityNum[pri]=append(priorityNum[pri],value)}// 优先级降序priorityArr:=make([]int,0)forpri:=rangeprioritySet{priorityArr=append(priorityArr,pri)}sort.Sort(sort.Reverse(sort.IntSlice(priorityArr)))// 输出结果first:=truefor_,pri:=rangepriorityArr{for_,value:=rangepriorityNum[pri]{if!first{fmt.Print(",")}fmt.Print(value)first=false}}}