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 最初开发用于为蒙特卡洛模拟器生成输入,可生成具有分布均匀,大周期的数字,使其可以广泛用于各种…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...