题目描述与示例
题目描述
现有两门选修课,每门选修课都有一部分学生选修,每个学生都有选修课的成绩,需要你找出同时选修了两门选修课的学生,先按照班级进行划分,班级编号小的先输出,每个班级按照两门选修课成绩和的降序排序,成绩相同时按照学生的学号升序排序。
输入
第一行为第一门选修课学生的成绩,第二行为第二门选修课学生的成绩,每行数据中学生之间以英文分号分隔,每个学生的学号和成绩以英文逗号分隔,学生学号的格式为 8
位数字(2
位院系编号+入学年份后 2
位+院系内部 1
位专业编号+所在班级 3
位学号),学生成绩的取值范围为 [0,100]
之间的整数,两门选修课选修学生数的取值范围为 [1-2000]
之间的整数。
输出
同时选修了两门选修课的学生的学号,如果没有同时选修两门选修课的学生输出 NULL
,否则,先按照班级划分,班级编号小的先输出,每个班级先输出班级编号(学号前五位),然后另起一行输出这个班级同时选修两门选修课的学生学号,学号按照要求排序(按照两门选修课成绩和的降序,成绩和相同时按照学号升序),学生之间以英文分号分隔。
示例一
输入
01202021,75;01201033,95;01202008,80;01203006,90;01203088,100
01202008,70;01203088,85;01202111,80;01202021,75;01201100,88
输出
01202
01202008;01202021
01203
01203088
说明
同时选修了两门选修课的学生 01202021
、01202008
、01203088
,这三个学生两门选修课的成绩和分别为 150
、150
、185
。01202021
、01202008
属于 01202
班的学生,按照成绩和降序,成绩相同时按学号升序输出的结果为 01202008;01202021
。01203088
属于 01203
班的学生,按照成绩和降序,成绩相同时按学号升序输出的结果为 01203088
。01202
的班级编号小于 01203
的班级编号,需要先输出。
示例二
输入
01201022,75;01202033,95;01202018,80;01203006,90;01202066,100
01202008,70;01203102,85;01202111,80;01201021,75;01201100,88
输出
NULL
说明
没有同时选修了两门选修课的学生,输出 NULL
。
解题思路
这题属于典型的哈希表和排序的应用,难度不大。但题干较长,需要仔细读题并理解题目含义。由于分了多层的排序,因此代码也比较长,需要写题时对问题时刻保持清晰的头脑。
代码
Python
# 题目:2023Q2B-选修课
# 分值:100
# 作者:许老师-闭着眼睛学数理化
# 算法:哈希表,排序
# 代码看不懂的地方,请直接在群上提问
from collections import defaultdict
# 定义根据传入的lst构建哈希表的函数
def buildDict(lst):
# 初始化一个空哈希表dic
dic = dict()
# 遍历lst中的每一个字符串元素item
for item in lst:
# item中用","隔开学号和成绩
num, grade = item.split(",")
# 以学号num为key,成绩int(grade)为value,存入哈希表dic中
dic[num] = int(grade)
# 哈希表dic构建完毕,返回dic
return dic
# 分别输入两行字符串,表示两门选修课情况,
# 对字符串根据";"进行分割,存入两个列表中
lst1 = input().split(";")
lst2 = input().split(";")
# 根据两个列表,构建两个字典分别表示选修课1和2的选课情况
# 字典中的key为学号,value为成绩
dic1 = buildDict(lst1)
dic2 = buildDict(lst2)
# 由于要统计两门选修课均选了的学生的成绩情况,使用字典推导式构建一个新字典dic_total
# dic_total的key为学号,value为两门选修课成绩的和
dic_total = {num: (dic1[num] + dic2[num]) for num in dic1 if num in dic2}
# 如果dic_total长度为0,说明没有任何一个学生同时选了两门选修课
# 按照题意直接输出"NULL"
if len(dic_total) == 0:
print("NULL")
# 否则可以进行后续的排序和输出
else:
# 构建一个新的字典用于储存特定班级所包含的学生
# key为5位的班级编号,value为储存若干学号的列表
dic_class = defaultdict(list)
for num in dic_total:
# 学号的前5位为班级编号
class_num = num[:5]
dic_class[class_num].append(num)
# 遍历dic_class排序后的key,即为班级编号
for class_num in sorted(dic_class.keys()):
# 先输出班级
print(class_num)
# 获得班级class_num的所有学号
num_lst = dic_class[class_num]
# 对num_lst进行排序
# 先按照成绩降序排列,即根据-dic_total[x]升序排列
# 成绩相同时再按照学号排列,即根据x排列
num_lst.sort(key = lambda x: (-dic_total[x], x))
# 输出该班级中排序后的学生学号
print(";".join(num_lst))
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*2023Q2B-选修课*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String course1 = br.readLine();
String course2 = br.readLine();
String[] split1 = course1.split(";");
String[] split2 = course2.split(";");
HashMap<String, Integer> hashMap1 = new HashMap<>();
HashMap<String, Integer> hashMap2 = new HashMap<>();
String[] cur;
for (String s : split1) {
cur = s.split(",");
hashMap1.put(cur[0],Integer.parseInt(cur[1]));
}
HashMap<String,List<String>> result = new HashMap<>();
String classNum;
for (String s : split2){
cur = s.split(",");
hashMap2.put(cur[0],Integer.parseInt(cur[1]));
if (hashMap1.containsKey(cur[0])){
classNum = cur[0].substring(0,5);
if(!result.containsKey(classNum)){
List<String> stuList = new ArrayList<>();
stuList.add(cur[0]);
result.put(classNum,stuList);
}else {
result.get(classNum).add(cur[0]);
}
}
}
if(result.isEmpty()){
System.out.println("NULL");
}
List<String> classList = new ArrayList<>(result.keySet());
//班级编号小的先输出
Collections.sort(classList);
for (String cla : classList) {
//输出班级编号
System.out.println(cla);
//根据班级编号获取学生列表
List<String> stuList = result.get(cla);
//按照学号升序
Collections.sort(stuList);
//按照两门选修课成绩和的降序
Collections.sort(stuList,
((o1, o2) -> (hashMap1.get(o2)+hashMap2.get(o2))-(hashMap1.get(o1)+hashMap2.get(o1))));
//注意,每一次输出学生学号都要新建一个sj,否则包含之前sj的结果导致输出错误.
StringJoiner sj = new StringJoiner(";");
for (String stu : stuList) {
sj.add(stu);
}
//输出学生学号
System.out.println(sj);
}
}
}
C++
“`C++
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
unordered_map<string, int> buildDict(const vector<string>& lst) {
unordered_map<string, int> dic;
for (const string& item : lst) {
stringstream ss(item);
string num, gradeStr;
getline(ss, num, ',');
getline(ss, gradeStr, ',');
int grade = stoi(gradeStr);
dic[num] = grade;
}
return dic;
}
int main() {
string course1, course2;
getline(cin, course1);
getline(cin, course2);
<pre><code>stringstream ss1(course1), ss2(course2);
vector<string> lst1, lst2;
string token;
while (getline(ss1, token, ';')) {
lst1.push_back(token);
}
while (getline(ss2, token, ';')) {
lst2.push_back(token);
}
unordered_map<string, int> dic1 = buildDict(lst1);
unordered_map<string, int> dic2 = buildDict(lst2);
unordered_map<string, vector<string>> result;
for (const auto& entry : dic2) {
if (dic1.find(entry.first) != dic1.end()) {
string classNum = entry.first.substr(0, 5);
result[classNum].push_back(entry.first);
}
}
if (result.empty()) {
cout << "NULL" << endl;
} else {
vector<string> classList;
for (const auto& entry : result) {
classList.push_back(entry.first);
}
sort(classList.begin(), classList.end());
for (const string& cls : classList) {
cout << cls << endl;
vector<string> stuList = result[cls];
sort(stuList.begin(), stuList.end(), [&](const string& a, const string& b) {
int sumA = dic1[a] + dic2[a];
int sumB = dic1[b] + dic2[b];
if (sumA != sumB) {
return sumA > sumB;
}
return a < b;
});
for (size_t i = 0; i < stuList.size(); ++i) {
cout << stuList[i];
if (i != stuList.size() – 1) {
cout << ";";
}
}
cout << endl;
}
}
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(NlogN)
。排序所需的时间复杂度。
空间复杂度:O(N)
。哈希表所占的额外空间。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)