当前位置: 首页 > news >正文

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每日一练:小艺读书醉酒的狱卒非降序数组(详解快排)

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

手麻系统源码,PHP手术麻醉临床信息系统源码,手术前管理模块功能

手麻系统源码&#xff0c;PHP手术麻醉临床信息系统源码&#xff0c;手术前管理模块功能 术前管理模块主要有手术排班、手术申请单、手术通知单、手术知情同意书、输血血液同意书、术前查房记录、术前访视、风险评估、手术计划等功能。 功能&#xff1a; 手术排班&#xff1a;…...

AUTOSAR - ComM - 学习一 :基础知识+配置

目录 1、概述 1.1、总览 1.2、功能描述 1.3、依赖关系 2、功能SPEC 2.1、PNC...

手把手教你搭建ROS阿克曼转向小车之(增量式PID代码实现)

在上一篇文章中我们已经成功的把编码器的反馈值给计算出来&#xff0c;这篇文章将会讲解怎么使用反馈回来的速度值进行PID计算&#xff0c;从而闭环控制电机的速度。 PID算法介绍 1.开环控制系统 开环控制系统(open-loop control system)是指被控对象的输出(被控制量)对控制器…...

C语言函数大全-- t 开头的函数

C语言函数大全 本篇介绍C语言函数大全-- t 开头的函数 1. tan&#xff0c;tanf&#xff0c;tanl 1.1 函数说明 函数声明函数功能double tan(double x)计算 以弧度 x 为单位的角度的正切值&#xff08;double&#xff09;float tanf(float x)计算 以弧度 x 为单位的角度的正…...

安卓系统APP稳定性测试分析的研究报告

目录 第一章&#xff1a;概念 第二章&#xff1a;重要性 第三章&#xff1a;意义和作用 第四章&#xff1a;行业现状 第五章&#xff1a;常见测试方法和工具 第六章&#xff1a;实际测试场景 第七章&#xff1a;测试方案 第八章&#xff1a;测试方法 第九章&#xff1…...

【Java基础】集合

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

【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系列发布时间&#xff1a; 先贴一下yolo各系列的发布时间&#xff08;说出来很丢人&#xff0c;我以为 yolox是 最新的&#xff09;&#xff1a; yoloX 2…...

前端009_类别模块_修改功能

第九章 1、需求分析2、Mock添加查询数据3、Mock修改数据4、Api调用回显数据5、提交修改后的数据6、效果1、需求分析 需求分析 当点击 编辑 按钮后,弹出编辑窗口,并查询出分类相关信息进行渲染。修改后点击 确定 提交修改后的数据。 2、Mock添加查询数据 请求URL: /article/…...

2022级吉林大学面向对象第一次上机测试

【注&#xff1a;解答全部为本人所写&#xff0c;仅供同学们学习时参考使用&#xff0c;请勿照搬抄袭&#xff01;】 1、 1&#xff09;略 2&#xff09;如果main,f1,g1,g2或更多的函数之间有更为复杂的调用关系&#xff0c;头文件一般按怎样的规律写呢&#xff1f; 一般情况下…...

计算机体系结构总结:内存一致性模型 Memory consistency Model

存储一致性是为了保证多线程背景下的访存顺序&#xff0c;多线程的语句是可以交错执行&#xff0c;使得顺序不同产生不同的执行结果。 下面P2的输出结果可能是什么&#xff1f; P1, P2两个线程的语句是可以交叉执行的&#xff0c;比如1a, 2a, 2b, 1b&#xff1b;一个线程内的语…...

高速列车运行控制系统(CTCS)介绍

1、CTCS功能 安全防护 在任何情况下防止列车无行车许可运行防止列车超速运行防止列车超过进路允许速度防止列车超过线路结构规定的速度防止列车超过机车车辆构造速度防止列车超过临时限速及紧急限速防止列车超过铁路有关运行设备的限速防止列车溜逸 人机界面 以字符、数字及…...

C#“System.Threading.ThreadStateException”类型的未经处理的异常

备忘 最近做一个功能&#xff0c;从主界面进入另一个界面时&#xff0c;数据量较大&#xff0c;处理信息较多&#xff0c;程序宕机。而且点击程序还会提示程序无响应。不得已用另一个线程显示界面。但在界面中使用控件时&#xff0c;报错&#xff1a;“System.Threading.Thread…...

为什么要交叉编译?

一、什么是交叉编译、为什么要交叉编译 1、什么是交叉编译&#xff1f; 交叉编译&#xff1a;是在一个平台上生成另一个平台上的可执行代码。比如我们在 x86 平台上&#xff0c;编写程序并编译成能运行在 ARM 平台的程序&#xff0c;编译得到的程序在 x86 平台上是不能运行的…...

java版本电子招标采购系统源码—企业战略布局下的采购

​ 智慧寻源 多策略、多场景寻源&#xff0c;多种看板让寻源过程全程可监控&#xff0c;根据不同采购场景&#xff0c;采取不同寻源策略&#xff0c; 实现采购寻源线上化管控&#xff1b;同时支持公域和私域寻源。 询价比价 全程线上询比价&#xff0c;信息公开透明&#xff0…...

【MATLAB数据处理实用案例详解(17)】——利用概念神经网络实现柴油机故障诊断

目录 一、问题描述二、利用概念神经网络实现柴油机故障诊断原理三、算法步骤3.1 定义样本3.2 样本归一化3.3 创建网络模型3.4 测试3.5 显示结果 四、运行结果五、完整代码 一、问题描述 柴油机的结构较为复杂&#xff0c;工作状况非常恶劣&#xff0c;因此发生故障的可能性较大…...

神奇字符串、密钥格式化----2023/5/6

神奇字符串----2023/5/6 神奇字符串 s 仅由 ‘1’ 和 ‘2’ 组成&#xff0c;并需要遵守下面的规则&#xff1a; 神奇字符串 s 的神奇之处在于&#xff0c;串联字符串中 ‘1’ 和 ‘2’ 的连续出现次数可以生成该字符串。 s 的前几个元素是 s “1221121221221121122……” 。…...

STM32F4_十进制和BCD码的转换

目录 前言 1. BCD码 2. BCD码和十进制转换的算法 前言 最近在学习STM32单片机&#xff08;不仅仅是32&#xff09;的RTC实时时钟系统的过程中&#xff0c;需要配置时钟的时间、日期&#xff1b;这些都需要实现BCD码和十进制之间进行转换。这里和大家一起学习BCD码和十进制之…...

random — 伪随机数生成器(史上总结最全)

目的&#xff1a;实现几种类型的伪随机数生成器。 random 模块基于 Mersenne Twister 算法提供了一个快速的伪随机数生成器。Mersenne Twister 最初开发用于为蒙特卡洛模拟器生成输入&#xff0c;可生成具有分布均匀&#xff0c;大周期的数字&#xff0c;使其可以广泛用于各种…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...