【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试【DP】2023C-分班【欧弟算法】全网注释最详细分类最全的华为OD真题题解
题目描述与示例
题目描述
幼儿园两个班的小朋友在排队时混在了一起,每位小朋友都知道自己是否与前面一位小朋友是否同班,请你帮忙把同班的小朋友找出来。小朋友的编号为整数,与前一位小朋友同班用Y
表示,不同班用N
表示。
输入描述
输入为空格分开的小朋友编号和是否同班标志。
比如: 6/N
2/Y
3/N
4/Y
,表示共4
位小朋友,2
和6
同班, 3
和2
不同班,4
和3
同班。
其中,小朋友总数不超过999
,每个小朋友编号大于0
,小于等于999
。不考虑输入格式错误问题。
输出描述
输出为两行,每一行记录一个班小朋友的编号,编号用空格分开。
且:
- 编号需要按照大小升序排列,分班记录中第一个编号小的排在第一行;
- 若只有一个班的小朋友,第二行为空行;
- 若输入不符合要求,则直接输出字符串
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班。
我们考虑动态规划三部曲:
dp
数组的含义是什么?
dp
数组是一个长度为n
的一维列表,dp[i]
是布尔变量True
或者False
。如果dp[i] = True
表示第i
个小朋友分在1班dp[i] = False
表示第i
个小朋友分在2班
- 动态转移方程是什么?
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]
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, class1
print(" ".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,分到class2
class1.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,分到 class2
if (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,分到 class2
if (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
了解更多
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!