【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试【DP】2023C-分班【欧弟算法】全网注释最详细分类最全的华为OD真题题解

2023-12-15 01:52
文章标签 java 算法 c++ 全网 笔试 dp 三种 华为 py 真题 注释 20 题解 最全 od 分班 拿下 欧弟 od2023c 2023c

本文主要是介绍【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试【DP】2023C-分班【欧弟算法】全网注释最详细分类最全的华为OD真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

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

题目描述与示例

题目描述

幼儿园两个班的小朋友在排队时混在了一起，每位小朋友都知道自己是否与前面一位小朋友是否同班，请你帮忙把同班的小朋友找出来。小朋友的编号为整数，与前一位小朋友同班用Y表示，不同班用N表示。

输入描述

输入为空格分开的小朋友编号和是否同班标志。

比如: 6/N 2/Y 3/N 4/Y，表示共4位小朋友，2和6同班， 3和2不同班，4和3同班。

其中，小朋友总数不超过999，每个小朋友编号大于0，小于等于999。不考虑输入格式错误问题。

输出描述

输出为两行，每一行记录一个班小朋友的编号，编号用空格分开。

且:

  1. 编号需要按照大小升序排列，分班记录中第一个编号小的排在第一行；
  2. 若只有一个班的小朋友，第二行为空行；
  3. 若输入不符合要求，则直接输出字符串ERROR。

示例一

输入

6/N
2/Y
3/N
4/Y

输出

2 6
3 4

示例二

输入

2/N
3/Y
4/Y

输出

2 3 4

解题思路

每一个小朋友在哪个班，只跟其前一个小朋友在哪个班有关系。换句话说，考虑第i个小朋友的分班，我们只需要关心第i-1个小朋友在哪个班，而不需要关心第i-1个小朋友为什么会分配到这个班。这是一种典型的dp思路。

由于一共只有两个班，为了方便起见，我们分为1班和2班，同时默认第0个小朋友位于1班。

我们考虑动态规划三部曲：

  1. dp数组的含义是什么？
  • dp数组是一个长度为n的一维列表，dp[i]是布尔变量True或者False。如果
    • dp[i] = True表示第i个小朋友分在1班
    • dp[i] = False表示第i个小朋友分在2班
  1. 动态转移方程是什么？
  • dp[i]只跟dp[i-1]以及YN_lst[i]有关系。若
    • 第i个小朋友和第i-1个小朋友同班，即YN_lst[i] == "Y"，那么dp[i] = dp[i-1]
    • 第i个小朋友和第i-1个小朋友不同班，即YN_lst[i] == "N"，那么dp[i] = not dp[i-1]
if YN_lst[i] == "Y":dp[i] = dp[i-1]
elif YN_lst[i] == "N":dp[i] = not dp[i-1]
  1. dp数组如何初始化？
  • 默认第0个小朋友是在1班，故dp[0] = True

做完dp过程之后，还需要依据题目要求，对两个班的小朋友进行排序和输出。其过程如下

class1, class2 = list(), list()
for i in range(n):class1.append(children_lst[i]) if dp[i] else class2.append(children_lst[i])class1.sort()
class2.sort()
if len(class2) == 0:print(" ".join(map(str, class1)))print("")
else:if class1[0] > class2[0]:class1, class2 = class2, class1print(" ".join(map(str, class1)))print(" ".join(map(str, class2)))

代码

Python

# 题目：2023B-分班
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：DP
# 代码看不懂的地方，请直接在群上提问children_lst = list()
YN_lst = list()# 由于不知道输入行数，故使用try-except语句，结合while死循环进行输入
while True:# try语句，尝试执行以下语句try:# 进行输入s = input()# 如果s无法进行分割成两部分，则此处解包会出现报错，进入except语句child, ch = s.split("/")# 成功分割，则将小朋友编号记录在children_lst中# 是否与前一个小朋友同班的标记"Y"或"N"记录在YN_lst中children_lst.append(int(child))YN_lst.append(ch)# 如果出现错误，说明输入最后一行，退出死循环except:break# 获得小朋友的数目
n = len(children_lst)# 构建长度为n的dp数组，dp[i]的取值为True和False
# True表示第i个小朋友在1班，False表示第i个小朋友在2班
dp = [None] * n
# 初始化dp[0]为True，表示默认分配第0个小朋友在1班
dp[0] = True# 遍历所有小朋友
for i in range(1, n):# 如果YN_lst[i]为"Y"，表示第i个小朋友和第i-1个小朋友同班# dp[i]和dp[i-1]取相同if YN_lst[i] == "Y":dp[i] = dp[i-1]# 如果YN_lst[i]为"N"，表示第i个小朋友和第i-1个小朋友不同班# dp[i]和dp[i-1]取相反elif YN_lst[i] == "N":dp[i] = not dp[i-1]# 构建表示两个班级的列表
class1, class2 = list(), list()
for i in range(n):# 如果dp[i]为True，分到class1，如果dp[i]为False，分到class2class1.append(children_lst[i]) if dp[i] else class2.append(children_lst[i])# 题目要求排序，故对class1和class2进行排序
class1.sort()
class2.sort()
# 如果class2长度为0，说明所有小朋友都在1班
# 输出1班的结果和一个空字符串
if len(class2) == 0:print(" ".join(map(str, class1)))print("")
else:# 两个班级之间的排序，以班级中编号最小的小朋友为准# 故如果发现2班编号最小的小朋友比1班编号最小的小朋友更小# 应该先输出2班，故对两者进行交换if class1[0] > class2[0]:class1, class2 = class2, class1# 先输出1班，再输出2班print(" ".join(map(str, class1)))print(" ".join(map(str, class2)))

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {List<Integer> childrenList = new ArrayList<>();List<String> ynList = new ArrayList<>();// 由于不知道输入行数，故使用 try-catch 语句，结合 while 死循环进行输入Scanner scanner = new Scanner(System.in);while (true) {// try 语句，尝试执行以下语句try {// 进行输入String s = scanner.nextLine();// 如果 s 无法进行分割成两部分，则此处解包会出现报错，进入 catch 语句String[] parts = s.split("/");int child = Integer.parseInt(parts[0]);String ch = parts[1];// 成功分割，则将小朋友编号记录在 childrenList 中// 是否与前一个小朋友同班的标记 "Y" 或 "N" 记录在 ynList 中childrenList.add(child);ynList.add(ch);}// 如果出现错误，说明输入最后一行，退出死循环catch (Exception e) {break;}}// 获得小朋友的数目int n = childrenList.size();// 构建长度为 n 的 dp 数组，dp[i] 的取值为 true 和 false// true 表示第 i 个小朋友在 1 班，false 表示第 i 个小朋友在 2 班boolean[] dp = new boolean[n];// 初始化 dp[0] 为 true，表示默认分配第 0 个小朋友在 1 班dp[0] = true;// 遍历所有小朋友for (int i = 1; i < n; i++) {// 如果 ynList[i] 为 "Y"，表示第 i 个小朋友和第 i-1 个小朋友同班// dp[i] 和 dp[i-1] 取相同if (ynList.get(i).equals("Y")) {dp[i] = dp[i - 1];}// 如果 ynList[i] 为 "N"，表示第 i 个小朋友和第 i-1 个小朋友不同班// dp[i] 和 dp[i-1] 取相反else if (ynList.get(i).equals("N")) {dp[i] = !dp[i - 1];}}// 构建表示两个班级的列表List<Integer> class1 = new ArrayList<>();List<Integer> class2 = new ArrayList<>();for (int i = 0; i < n; i++) {// 如果 dp[i] 为 true，分到 class1，如果 dp[i] 为 false，分到 class2if (dp[i]) {class1.add(childrenList.get(i));} else {class2.add(childrenList.get(i));}}// 题目要求排序，故对 class1 和 class2 进行排序class1.sort(Integer::compareTo);class2.sort(Integer::compareTo);// 如果 class2 长度为 0，说明所有小朋友都在 1 班// 输出 1 班的结果和一个空字符串if (class2.isEmpty()) {for (int child : class1) {System.out.print(child + " ");}System.out.println();System.out.println();} else {// 两个班级之间的排序，以班级中编号最小的小朋友为准// 故如果发现 2 班编号最小的小朋友比 1 班编号最小的小朋友更小// 应该先输出 2 班，故对两者进行交换if (class1.get(0) > class2.get(0)) {List<Integer> temp = class1;class1 = class2;class2 = temp;}// 先输出 1 班，再输出 2 班for (int child : class1) {System.out.print(child + " ");}System.out.println();for (int child : class2) {System.out.print(child + " ");}System.out.println();}}
}

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {vector<int> childrenList;vector<string> ynList;// 由于不知道输入行数，故使用 try-catch 语句，结合 while 死循环进行输入while (true) {// try 语句，尝试执行以下语句try {// 进行输入string s;getline(cin, s);// 如果 s 无法进行分割成两部分，则此处解包会出现报错，进入 catch 语句int pos = s.find('/');int child = stoi(s.substr(0, pos));string ch = s.substr(pos + 1);// 成功分割，则将小朋友编号记录在 childrenList 中// 是否与前一个小朋友同班的标记 "Y" 或 "N" 记录在 ynList 中childrenList.push_back(child);ynList.push_back(ch);}// 如果出现错误，说明输入最后一行，退出死循环catch (exception& e) {break;}}// 获得小朋友的数目int n = childrenList.size();// 构建长度为 n 的 dp 数组，dp[i] 的取值为 true 和 false// true 表示第 i 个小朋友在 1 班，false 表示第 i 个小朋友在 2 班vector<bool> dp(n);// 初始化 dp[0] 为 true，表示默认分配第 0 个小朋友在 1 班dp[0] = true;// 遍历所有小朋友for (int i = 1; i < n; i++) {// 如果 ynList[i] 为 "Y"，表示第 i 个小朋友和第 i-1 个小朋友同班// dp[i] 和 dp[i-1] 取相同if (ynList[i] == "Y") {dp[i] = dp[i - 1];}// 如果 ynList[i] 为 "N"，表示第 i 个小朋友和第 i-1 个小朋友不同班// dp[i] 和 dp[i-1] 取相反else if (ynList[i] == "N") {dp[i] = !dp[i - 1];}}// 构建表示两个班级的列表vector<int> class1, class2;for (int i = 0; i < n; i++) {// 如果 dp[i] 为 true，分到 class1，如果 dp[i] 为 false，分到 class2if (dp[i]) {class1.push_back(childrenList[i]);} else {class2.push_back(childrenList[i]);}}// 题目要求排序，故对 class1 和 class2 进行排序sort(class1.begin(), class1.end());sort(class2.begin(), class2.end());// 如果 class2 长度为 0，说明所有小朋友都在 1 班// 输出 1 班的结果和一个空行if (class2.empty()) {for (int child : class1) {cout << child << " ";}cout << endl << endl;} else {// 两个班级之间的排序，以班级中编号最小的小朋友为准// 故如果发现 2 班编号最小的小朋友比 1 班编号最小的小朋友更小// 应该先输出 2 班，故对两者进行交换if (class1[0] > class2[0]) {swap(class1, class2);}// 先输出 1 班，再输出 2 班for (int child : class1) {cout << child << " ";}cout << endl;for (int child : class2) {cout << child << " ";}cout << endl;}return 0;
}

时空复杂度

时间复杂度：O(xlogx + ylogy + N)。O(xlogx)和O(ylogy)是两个班级各自排序的时间复杂度，O(N)是dp过程的时间复杂度。

空间复杂度：O(N)。

x和y为两个班级的人数，N是总人数。

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

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

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

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

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

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

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

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

这篇关于【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试【DP】2023C-分班【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/494670。

相关文章

Spring WebClient从入门到精通

Spring WebClient从入门到精通

《SpringWebClient从入门到精通》本文详解SpringWebClient非阻塞响应式特性及优势,涵盖核心API、实战应用与性能优化,对比RestTemplate,为微服务通信提供高效解决... 目录一、WebClient 概述1.1 为什么选择 WebClient？1.2 WebClient 与
阅读更多...
Java.lang.InterruptedException被中止异常的原因及解决方案

Java.lang.InterruptedException被中止异常的原因及解决方案

《Java.lang.InterruptedException被中止异常的原因及解决方案》Java.lang.InterruptedException是线程被中断时抛出的异常,用于协作停止执行,常见于... 目录报错问题报错原因解决方法Java.lang.InterruptedException 是 Jav
阅读更多...
深入浅出SpringBoot WebSocket构建实时应用全面指南

深入浅出SpringBoot WebSocket构建实时应用全面指南

《深入浅出SpringBootWebSocket构建实时应用全面指南》WebSocket是一种在单个TCP连接上进行全双工通信的协议,这篇文章主要为大家详细介绍了SpringBoot如何集成WebS... 目录前言为什么需要 WebSocketWebSocket 是什么Spring Boot 如何简化 We
阅读更多...
java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)

java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)

《java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)》：本文主要介绍java中pdf模版填充表单踩坑的相关资料,OpenPDF、iText、PDFBox是三... 目录准备Pdf模版方法1：itextpdf7填充表单（1）加入依赖（2）代码（3）遇到的问题方法2：pd
阅读更多...
Java Stream流之GroupBy的用法及应用场景

Java Stream流之GroupBy的用法及应用场景

《JavaStream流之GroupBy的用法及应用场景》本教程将详细介绍如何在Java中使用Stream流的groupby方法,包括基本用法和一些常见的实际应用场景,感兴趣的朋友一起看看吧... 目录Java Stream流之GroupBy的用法1. 前言2. 基础概念什么是 GroupBy？Stream
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
SpringBoot监控API请求耗时的6中解决解决方案

SpringBoot监控API请求耗时的6中解决解决方案

《SpringBoot监控API请求耗时的6中解决解决方案》本文介绍SpringBoot中记录API请求耗时的6种方案,包括手动埋点、AOP切面、拦截器、Filter、事件监听、Micrometer+... 目录1. 简介2.实战案例2.1 手动记录2.2 自定义AOP记录2.3 拦截器技术2.4 使用Fi
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
最新Spring Security的基于内存用户认证方式

最新Spring Security的基于内存用户认证方式

《最新SpringSecurity的基于内存用户认证方式》本文讲解SpringSecurity内存认证配置,适用于开发、测试等场景,通过代码创建用户及权限管理,支持密码加密,虽简单但不持久化,生产环... 目录1. 前言2. 因何选择内存认证？3. 基础配置实战❶ 创建Spring Security配置文件
阅读更多...
Spring Security 单点登录与自动登录机制的实现原理

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录（SSO）与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录（SSO）1.2 自动登录（Remember Me）二、代码分析三、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2