西安网站备案,esp8266做网站,手机在线做ppt的网站有哪些问题,巴中做网站公司文章目录 前言一、小艺读书二、醉酒的狱卒三、非降序数组总结 前言
今天这个非降序数组#xff0c;阅读解理小学水平#xff0c;说起来都是泪啊。我折腾了一天都没搞定#xff0c;从冒泡写到快速排序。换了几种都还不行#xff0c;我又给快排加上插入排序。结果还是不能全… 文章目录 前言一、小艺读书二、醉酒的狱卒三、非降序数组总结 前言
今天这个非降序数组阅读解理小学水平说起来都是泪啊。我折腾了一天都没搞定从冒泡写到快速排序。换了几种都还不行我又给快排加上插入排序。结果还是不能全过我以为题目有问题我就用了sort测试还真能过的证明我排序代码写得烂…郁闷好半天我决定去偷看测试数据。才发现这数据本身就是有序的怪不得难度系数只有中…然后就用一分钟搞定。 提示以下是本篇文章正文内容下面案例可供参考
一、小艺读书
题目描述 书是人类进步的阶梯。 小艺每周因为工作的原因会选择性的每天多读几页或者少读几页。 小艺想知道一本n页的书她会在周几读完。
输入描述 第一行输入n(1n1000) 第二行输入7个整数分别表示周一~周日的读书页数p(0p1000)。不考虑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(v1)]for N in range(1, v1):for i in range(1, v1):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 (leftright)//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[j1] arr[j] #以前面的比较j - 1arr[j1] curr #插入暂时正确的位置i 1def qsort(arr, left, right):if left10 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, i1, 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 in and jm:if num1[i] num2[j]:result.append(num1[i])i 1else:result.append(num2[j])j 1if in:result num1[i:]if jm:result num2[j:]result [str(x) for x in result]return result思路就是逐个比较前面的元素小的先放入result再比较下一个当比较完一个数组后剩余的直接全加入就行了。 总结
其实最后这题还是挺有意思的我把最大的那个测试用例给记下来了准备再想想怎么用排序的办法过关明明系统自带的sort函数能过的嘛~
