Python每日一练:小艺读书醉酒的狱卒非降序数组(详解快排)
文章目录
- 前言
- 一、小艺读书
- 二、醉酒的狱卒
- 三、非降序数组
- 总结
前言
今天这个非降序数组,阅读解理小学水平,说起来都是泪啊。我折腾了一天都没搞定,从冒泡写到快速排序。换了几种都还不行,我又给快排加上插入排序。结果还是不能全过!我以为题目有问题,我就用了sort测试,还真能过的!证明我排序代码写得烂…郁闷好半天,我决定去偷看测试数据。才发现这数据本身就是有序的,怪不得难度系数只有中…然后就用一分钟搞定。
提示:以下是本篇文章正文内容,下面案例可供参考
一、小艺读书
题目描述:
书是人类进步的阶梯。 小艺每周因为工作的原因会选择性的每天多读几页或者少读几页。 小艺想知道一本n页的书她会在周几读完。
输入描述:
第一行输入n(1<=n<=1000); 第二行输入7个整数,分别表示周一~周日的读书页数p(0<=p<=1000)。(不考虑7个整数都为0的情况)
输出答案:(1-7)
代码如下(示例):
class Solution:def __init__(self) -> None:passdef solution(self, n, pages):result = None# TODO: 请在此编写代码pi = 0while True:n = n-pages[pi%7]pi += 1if n <= 0:result = pi%7breakreturn result
非常之简单,因为前面有个+=1,所以后面的结果不用加1。需要注意的是,有可能一周读不完,要多循环一下,嗯~我还知道只算一周只能过40。
二、醉酒的狱卒
题目描述:
某监狱有一个由n个牢房组成的大厅,每个牢房紧挨着。每个牢房里都有一个囚犯,每个牢房都是锁着的。 一天晚上,狱卒感到无聊,决定玩一个游戏。在第一轮,他喝了一杯威士忌,然后跑下大厅,打开每个牢房的锁。在第二轮比赛中,他喝了一杯威士忌,然后跑下大厅,锁上每隔一个的牢房的锁(牢房2、4、6…)。在第三轮比赛中,他喝了一杯威士忌,然后跑下大厅。他每隔三个牢房(第3、6、9号牢房)就去一次。如果牢房被锁上了,他就把它打开;如果牢房门打开了,他就锁上牢房。他重复n轮,喝最后一杯,然后昏倒。 一些囚犯(可能为零号)意识到他们的牢房被解锁且狱卒丧失了行动能力。他们就可以立即逃跑。现在根据牢房数量,确定有多少囚犯越狱。
输入描述:
第一行输入包含一个正整数t。表示有t行数据,下面每一行都包含一个介于5和100之间(含5和100)的整数,即轮数n
输出描述:
对于每一行,必须打印出监狱有n个牢房时越狱的囚犯人数
代码如下(示例):
class Solution:def __init__(self) -> None:passdef solution(self, t, vector):result = []# TODO: 请在此编写代码for v in vector:v = int(v)rooms = []rooms = [False for _ in range(v+1)]for N in range(1, v+1):for i in range(1, v+1):if i*N <= v:rooms[i*N] = not rooms[i*N]result.append(sum(rooms))result = [str(x) for x in result]return result
虽然描述很长,但还真不难,就是描述中有个地方误导人,说有0号牢房,实际上是没有的!外循环是不同的牢房数、内循环是不同的波次。其实是同一个数,先定义了一个全False的列表,然后根据牢房号不停的翻转状态即可。最后用了sum统计True值的个数,就是可以逃跑的牢房数了。
三、非降序数组
这题太误导人了,我怎么看都是要求排序!所以我优化又优化了几波排序算法,采用了快速排序加尾数插入排序的办法。可惜也不能100分。虽然这测试数据有确实过份,长的一个列表约有十万个数。
不过写都写出来了,就在这记录一下,其实也挺不容易的了!
代码如下(不能全过的排序法示例):
def qmid(arr, left, right):# 取左、中、右的中值作为基数, 并对此三数排序center = (left+right)//2if arr[center] < arr[left]:arr[center], arr[left] = arr[left], arr[center]if arr[right] < arr[left]:arr[right], arr[left] = arr[left], arr[right]if arr[right] < arr[center]:arr[right], arr[center] = arr[center], arr[right]# 将基数放在right-1位置arr[right-1], arr[center] = arr[center], arr[right-1]pivot = arr[right-1]return pivotdef insert_sort(arr):n = arr.__len__()i, j = 1, 0while i < n:curr = arr[i] # 待排的数j = i - 1while j >= 0 and curr < arr[j]:arr[j+1] = arr[j] #以前面的比较j -= 1arr[j+1] = curr #插入暂时正确的位置i += 1def qsort(arr, left, right):if left+10 <= right:pivot = qmid(arr, left, right)i, j = left-1, right-1-1while True:while arr[i] < pivot:i += 1while arr[j] > pivot:j -= 1if i < j:arr[i], arr[j] = arr[j], arr[i]else:breakarr[i], arr[right-1] = arr[right-1], arr[i]qsort(arr, left, i-1)qsort(arr, i+1, right)else:insert_sort(arr)
qmid函数是用来计算快排的基准数的,很多人喜欢取值第一个或最后一个,对于无序列表(数组)来说确实也没大问题,但很明显如果有序的数组就会让复杂度变成最差的n^2情况,所以这里采用了首尾中间三个数来比较取值,并顺手把这三个数排了序。尽量争取做到左右各半这种最好的情况。
第二个insert_sort函数是插入排序,它的作用是在快排分割成小于10个数的列表时,直接用插入排序来干了,对于基本有序的一个数组,插入排序的速度是很快的。其基本思想是:从第1个开始与它前面的数比较,小的就和前面的交换,大了就下一个,如此循环一次完成。因为经过前面的快排,数组是基本有序的,所以很快。
第三个函数就是快速排序的主体了,它其实了是冒泡排序的改良。基本思想是选取一个数作为中间值pivot,把比pivot小的放左边,比pivot大的放右边。然后把数组以pivot为界分成左右两半,递归再进行。这应该是已知的公认最快排序方法了。可惜水平不够,写出的过不了100分,有机会应该学习一下自带的排序是怎么写的。
好了,最后我又去参考了别人的思路,才发现这题压根不是让人重排序,给出的数组本身就是有序的,只要合并就行了。那么我们要考虑的就是二个数组哪个小的放前面,大的放后面的事。这就简单了,一个个比较好了:以下是100分代码,很简单
class Solution:def __init__(self) -> None:passdef solution(self, n, m, num1, num2):result = []# TODO: 请在此编写代码i, j = 0, 0while i<n and j<m:if num1[i] < num2[j]:result.append(num1[i])i += 1else:result.append(num2[j])j += 1if i<n:result += num1[i:]if j<m:result += num2[j:]result = [str(x) for x in result]return result
思路就是逐个比较前面的元素,小的先放入result,再比较下一个,当比较完一个数组后,剩余的直接全加入就行了。
总结
其实最后这题还是挺有意思的,我把最大的那个测试用例给记下来了,准备再想想怎么用排序的办法过关,明明系统自带的sort函数能过的嘛~
相关文章:

Python每日一练:小艺读书醉酒的狱卒非降序数组(详解快排)
文章目录 前言一、小艺读书二、醉酒的狱卒三、非降序数组总结 前言 今天这个非降序数组,阅读解理小学水平,说起来都是泪啊。我折腾了一天都没搞定,从冒泡写到快速排序。换了几种都还不行,我又给快排加上插入排序。结果还是不能全…...

手麻系统源码,PHP手术麻醉临床信息系统源码,手术前管理模块功能
手麻系统源码,PHP手术麻醉临床信息系统源码,手术前管理模块功能 术前管理模块主要有手术排班、手术申请单、手术通知单、手术知情同意书、输血血液同意书、术前查房记录、术前访视、风险评估、手术计划等功能。 功能: 手术排班:…...
AUTOSAR - ComM - 学习一 :基础知识+配置
目录 1、概述 1.1、总览 1.2、功能描述 1.3、依赖关系 2、功能SPEC 2.1、PNC...
手把手教你搭建ROS阿克曼转向小车之(增量式PID代码实现)
在上一篇文章中我们已经成功的把编码器的反馈值给计算出来,这篇文章将会讲解怎么使用反馈回来的速度值进行PID计算,从而闭环控制电机的速度。 PID算法介绍 1.开环控制系统 开环控制系统(open-loop control system)是指被控对象的输出(被控制量)对控制器…...

C语言函数大全-- t 开头的函数
C语言函数大全 本篇介绍C语言函数大全-- t 开头的函数 1. tan,tanf,tanl 1.1 函数说明 函数声明函数功能double tan(double x)计算 以弧度 x 为单位的角度的正切值(double)float tanf(float x)计算 以弧度 x 为单位的角度的正…...
安卓系统APP稳定性测试分析的研究报告
目录 第一章:概念 第二章:重要性 第三章:意义和作用 第四章:行业现状 第五章:常见测试方法和工具 第六章:实际测试场景 第七章:测试方案 第八章:测试方法 第九章࿱…...

【Java基础】集合
一、集合概述 为了方便对多个对象进行存储和操作,集合是一种Java容器,可以动态地把多个对象引用放入容器中 数组存储的特点 一旦初始化后,长度不可改变,元素类型不可改变提供的方法很少,对于添加、删除、获取实际元…...

【Android入门到项目实战-- 9.1】—— 传感器的使用教程
目录 传感器的定义 三大类型传感器 1、运动传感器 2、环境传感器 3、位置传感器 传感器开发框架 1、SensorManager 2、Sensor 3、SensorEvent 4、SensorEventListener 一、使用传感器开发步骤 1、获取传感器信息 1)、获取传感器管理器 2)、获取设备的传感器对象列…...

yolov8 浅记
目录 Pre: 1. YOLOv8 概述 2. 模型结构设计 3. Loss 计算 4.训练数据增强 5. 训练策略 6、部署推理 End Pre: yolo系列发布时间: 先贴一下yolo各系列的发布时间(说出来很丢人,我以为 yolox是 最新的): yoloX 2…...

前端009_类别模块_修改功能
第九章 1、需求分析2、Mock添加查询数据3、Mock修改数据4、Api调用回显数据5、提交修改后的数据6、效果1、需求分析 需求分析 当点击 编辑 按钮后,弹出编辑窗口,并查询出分类相关信息进行渲染。修改后点击 确定 提交修改后的数据。 2、Mock添加查询数据 请求URL: /article/…...
2022级吉林大学面向对象第一次上机测试
【注:解答全部为本人所写,仅供同学们学习时参考使用,请勿照搬抄袭!】 1、 1)略 2)如果main,f1,g1,g2或更多的函数之间有更为复杂的调用关系,头文件一般按怎样的规律写呢? 一般情况下…...

计算机体系结构总结:内存一致性模型 Memory consistency Model
存储一致性是为了保证多线程背景下的访存顺序,多线程的语句是可以交错执行,使得顺序不同产生不同的执行结果。 下面P2的输出结果可能是什么? P1, P2两个线程的语句是可以交叉执行的,比如1a, 2a, 2b, 1b;一个线程内的语…...
高速列车运行控制系统(CTCS)介绍
1、CTCS功能 安全防护 在任何情况下防止列车无行车许可运行防止列车超速运行防止列车超过进路允许速度防止列车超过线路结构规定的速度防止列车超过机车车辆构造速度防止列车超过临时限速及紧急限速防止列车超过铁路有关运行设备的限速防止列车溜逸 人机界面 以字符、数字及…...
C#“System.Threading.ThreadStateException”类型的未经处理的异常
备忘 最近做一个功能,从主界面进入另一个界面时,数据量较大,处理信息较多,程序宕机。而且点击程序还会提示程序无响应。不得已用另一个线程显示界面。但在界面中使用控件时,报错:“System.Threading.Thread…...
为什么要交叉编译?
一、什么是交叉编译、为什么要交叉编译 1、什么是交叉编译? 交叉编译:是在一个平台上生成另一个平台上的可执行代码。比如我们在 x86 平台上,编写程序并编译成能运行在 ARM 平台的程序,编译得到的程序在 x86 平台上是不能运行的…...

java版本电子招标采购系统源码—企业战略布局下的采购
智慧寻源 多策略、多场景寻源,多种看板让寻源过程全程可监控,根据不同采购场景,采取不同寻源策略, 实现采购寻源线上化管控;同时支持公域和私域寻源。 询价比价 全程线上询比价,信息公开透明࿰…...

【MATLAB数据处理实用案例详解(17)】——利用概念神经网络实现柴油机故障诊断
目录 一、问题描述二、利用概念神经网络实现柴油机故障诊断原理三、算法步骤3.1 定义样本3.2 样本归一化3.3 创建网络模型3.4 测试3.5 显示结果 四、运行结果五、完整代码 一、问题描述 柴油机的结构较为复杂,工作状况非常恶劣,因此发生故障的可能性较大…...
神奇字符串、密钥格式化----2023/5/6
神奇字符串----2023/5/6 神奇字符串 s 仅由 ‘1’ 和 ‘2’ 组成,并需要遵守下面的规则: 神奇字符串 s 的神奇之处在于,串联字符串中 ‘1’ 和 ‘2’ 的连续出现次数可以生成该字符串。 s 的前几个元素是 s “1221121221221121122……” 。…...

STM32F4_十进制和BCD码的转换
目录 前言 1. BCD码 2. BCD码和十进制转换的算法 前言 最近在学习STM32单片机(不仅仅是32)的RTC实时时钟系统的过程中,需要配置时钟的时间、日期;这些都需要实现BCD码和十进制之间进行转换。这里和大家一起学习BCD码和十进制之…...
random — 伪随机数生成器(史上总结最全)
目的:实现几种类型的伪随机数生成器。 random 模块基于 Mersenne Twister 算法提供了一个快速的伪随机数生成器。Mersenne Twister 最初开发用于为蒙特卡洛模拟器生成输入,可生成具有分布均匀,大周期的数字,使其可以广泛用于各种…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...