1、有序队列（10分）
题目内容：
一开始给出了一个由小写字母组成的字符串 S。我们规定每次移动中，选择最左侧的字母，将其从原位置移除，并加到字符串的末尾。这样的移动可以执行任意多次
返回我们移动之后可以拥有的最小字符串（注：在Python3中，字符串的大小可用不等号比较）。
输入格式:
S。S为仅含有小写字母的字符串，长度不超过100000。
输出格式：
一个与S等长的字符串。
输入样例：
"cba"
输出样例：
acb
代码模板(建议复制粘贴使用)：
def func(S):
# your code here
return output
S = eval(input())
print(func(S))
时间限制：500ms内存限制：32000kb
代码1
解题思路：用本章学的队列，依次循环比较字符串大小
但队列时间复杂度大，用例4未通过
class Queues:
# 队列，为了不与自带函数Queue重复，用此名
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def func(S):
string = Queues()
minstr = S # 初始最小为S，若小则替换
n = 0
for letter in S:
string.enqueue(letter)
while n < string.size()-1:
string.enqueue(string.dequeue())
midstr = ''.join(string.items)[::-1]
if minstr > midstr:
minstr = midstr
n += 1
return minstr
S = eval(input())
print(func(S))
代码2
解题思路：直接切片重组字符串，进行比较大小
def func(S):
minstr = S # 初始最小为S，若小则替换
for i in range(len(S)):
S = S[1:]+S[0]
if S < minstr:
minstr = S
return minstr
S = eval(input())
print(func(S))
2、最近的请求次数（10分）
题目内容：
计算每个事件发生之时，往前算10000毫秒内有多少个事件发生，包含当事件；也即对于列表中的每个元素k，算出整个列表中有多少个元素介于k-10000和k（两端均含）之间。
输入格式:
一个已排序列表mylist，所有元素为非负整数，记录各个请求的发生时间，单位为毫秒。
输出格式：
一个与mylist等长的列表。
输入样例：
[0,10,100,1000,10000,20000,100000]
输出样例：
[1,2,3,4,5,2,1]
代码模板(建议复制粘贴使用)：
def func(mylist):
# your code here
return output
mylist = eval(input())
print(func(mylist))
时间限制：500ms内存限制：32000kb
解题思路：
队列，先入队的第一个元素进行计算，然后再加入新的元素入队，
同时循环判断队首元素-队尾元素是否大于10000
若大于，除去队尾元素；否则返回队列长度
此处存在坑：若存在相同元素，需要计入后面相同元素的个数
代码：
def func(mylist):
"""
队列，先入队的第一个元素进行计算，然后再加入新的元素入队，
同时循环判断队首元素-队尾元素是否大于10000
若大于，除去队尾元素；否则返回队列长度
坑：若存在相同元素，需要计入后面相同元素的个数
"""
q = Queues()
n = 0
newlist = []
output = []
for num in mylist:
q.enqueue(num)
while n<len(mylist):
first = q.dequeue()
newlist.append(first)
while newlist[-1] - newlist[0]>10000:
newlist.pop(0)
sum = 0
for i in reversed(q.items): #队列翻转，若第一个不是，直接退出
if i == newlist[-1]:
sum += 1
else:
break
output.append(len(newlist)+sum)
n += 1
return output
mylist = eval(input())
print(func(mylist))
3、基数排序（10分）
题目内容：
实现一个基数排序算法，用于10进制的正整数从小到大的排序。
思路是保持10个队列(队列0、队列1......队列9、队列main)，开始，所有的数都在main队列，没有排序。
第一趟将所有的数根据其10进制个位(09)，放入相应的队列09，全放好后，按照FIFO的顺序，将每个队列的数合并排到main队列。
第二趟再从main队列队首取数，根据其十位的数值，放入相应队列0~9，全放好后，仍然按照FIFO的顺序，将每个队列的数合并排到main队列。
第三趟放百位，再合并；第四趟放千位，再合并。
直到最多的位数放完，合并完，这样main队列里就是排好序的数列了。
输入格式:
一个列表mylist，其中mylist包含一些需要排序的正整数，正整数互不相同且均不超过100000，且个数在1至1000之间。
输出格式：
一个与mylist等长的列表。
输入样例：
[8, 91, 34, 22, 65, 30, 4, 55, 18]
输出样例：
[4, 8, 18, 22, 30, 34, 55, 65, 91]
代码模板(建议复制粘贴使用)：
def func(mylist):
# your code here
return output
mylist = eval(input())
print(func(mylist))
def func(mylist):
i = 0 #初始为个位排序
n = 1 #最小是1位数
max_num = max(mylist)
while max_num > 10 ** n: # 最大数是几位数
n += 1
while i < n:
bucket = {} #构建桶
for x in range(10):
bucket.setdefault(x, []) #每个桶都设置为空
for x in mylist: #每位数进行排序
radix = int(x/(10**i)%10) #基数位
bucket[radix].append(x) #元素放入对应基数位桶中
j = 0
for k in range(10):
if len(bucket[k]) != 0:
for y in bucket[k]:
mylist[j] = y
j += 1
i += 1
return mylist
mylist = eval(input())
print(func(mylist))
第3个用例没有通过，暂时没有找到原因
打印流程：
1、创建打印队列对象
a 时间按照秒的单位流逝
按照概率生成打印作业，加入打印队列
如果打印机空闲，且队列不空，则取出队首作业
打印，记录此作业等待时间
如果打印机忙，则按照打印速度进行1秒打印
如果当前作业打印完成，则打印机进入空闲
b 时间用尽， 开始统计平均等待时间
c 作业的等待时间
生成作业时，记录生成的时间戳
开始打印时，当前时间减去生成时间即可
d 作业的打印时间
生成作业时，记录作业的页数
开始打印时，页数除以打印速度即可
代码
import random
class Printer:
"""
打印机初始状态、打印时间流逝、工作状态、新任务
"""
def __init__(self, ppm):
# 初始化，打印速度、当前任务、任务倒计时
self.pagerate = ppm
self.currentTask = None
self.timeRemaining = 0
def tick(self):
# 打印1s
if self.currentTask != None:
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0:
self.currentTask = None
def busy(self):
# 打印忙
if self.currentTask != None:
return True
else:
return False
def startNext(self, newtask):
# 新作业共需要的时间
self.currentTask = newtask
self.timeRemaining = newtask.getPages()\
* 60/self.pagerate
class Task:
"""
打印任务 生成此任务时间，页数1-20随机
"""
def __init__(self, time):
self.timestamp = time
self.pages = random.randrange(1, 21)
def getStamp(self):
return self.timestamp
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime - self.timestamp
def newPrintTask():
# 1/180的概率生成任务
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
def simulation(numSeconds, pagesPerMinute):
# 打印模式，每min多少页
labprinter = Printer(pagesPerMinute)
printQueue = []
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
printQueue.insert(0, task)
if (not labprinter.busy()) and printQueue:
nexttask = printQueue.pop()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
averageWait = sum(waitingtimes)/len(waitingtimes)
print("Average Wait %6.2f secs %3d tasks remaining." %(averageWait, len(printQueue)))
for i in range(10):
simulation(3600, 10)
双端队列
“回文词”指正读和反读都一样的词
判断是否是回文词
代码
def palchecker(astring):
chardeque = []
for ch in astring:
chardeque.append(ch)
stillEqual = True
while len(chardeque) > 1 and stillEqual:
first = chardeque.pop()
last = chardeque.pop(0)
if first != last:
stillEqual = False
return stillEqual
print(palchecker("lsdkdsl"))
网友评论