做电商哪几个设计网站比较好,做网站的像素是多少,网站做一个多少钱,网站装修怎么做文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出 示例二输入输出 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
幼儿园两个班的小朋友在排队时混在了一起#xff0c;每位小朋友都知道自己是否与前… 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出 示例二输入输出 解题思路代码PythonJavaC时空复杂度 华为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, 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) {ListInteger childrenList new ArrayList();ListString 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];}}// 构建表示两个班级的列表ListInteger class1 new ArrayList();ListInteger 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)) {ListInteger 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 algorithmusing namespace std;int main() {vectorint childrenList;vectorstring 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 班vectorbool 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];}}// 构建表示两个班级的列表vectorint 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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
