【限时免费】20天拿下华为OD笔试之【哈希表】2023Q2B-选修课【欧弟算法】全网注释最详细分类最全的华为OD真题题解

本文主要是介绍【限时免费】20天拿下华为OD笔试之【哈希表】2023Q2B-选修课【欧弟算法】全网注释最详细分类最全的华为OD真题题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目描述与示例
    • 题目描述
    • 输入
    • 输出
    • 示例一
      • 输入
      • 输出
      • 说明
    • 示例二
      • 输入
      • 输出
      • 说明
  • 解题思路
  • 代码
    • Python
    • Java
    • C++
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述

现有两门选修课,每门选修课都有一部分学生选修,每个学生都有选修课的成绩,需要你找出同时选修了两门选修课的学生,先按照班级进行划分,班级编号小的先输出,每个班级按照两门选修课成绩和的降序排序,成绩相同时按照学生的学号升序排序。

输入

第一行为第一门选修课学生的成绩,第二行为第二门选修课学生的成绩,每行数据中学生之间以英文分号分隔,每个学生的学号和成绩以英文逗号分隔,学生学号的格式为 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

说明

同时选修了两门选修课的学生 012020210120200801203088,这三个学生两门选修课的成绩和分别为 1501501850120202101202008 属于 01202 班的学生,按照成绩和降序,成绩相同时按学号升序输出的结果为 01202008;0120202101203088 属于 01203 班的学生,按照成绩和降序,成绩相同时按学号升序输出的结果为 0120308801202 的班级编号小于 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):# 初始化一个空哈希表dicdic = dict()# 遍历lst中的每一个字符串元素itemfor item in lst:# item中用","隔开学号和成绩num, grade = item.split(",")# 以学号num为key,成绩int(grade)为value,存入哈希表dic中dic[num] = int(grade)# 哈希表dic构建完毕,返回dicreturn 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++

#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);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;
}

时空复杂度

时间复杂度:O(NlogN)。排序所需的时间复杂度。

空间复杂度:O(N)。哈希表所占的额外空间。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

这篇关于【限时免费】20天拿下华为OD笔试之【哈希表】2023Q2B-选修课【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/435098

相关文章

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

售价599元起! 华为路由器X1/Pro发布 配置与区别一览

《售价599元起!华为路由器X1/Pro发布配置与区别一览》华为路由器X1/Pro发布,有朋友留言问华为路由X1和X1Pro怎么选择,关于这个问题,本期图文将对这二款路由器做了期参数对比,大家看... 华为路由 X1 系列已经正式发布并开启预售,将在 4 月 25 日 10:08 正式开售,两款产品分别为华