数据结构与算法(Python版) | (7) 队列、列表OJ作业
OJ地址
1. 有序队列
def func(S):
min_str = S #记录最小的字符串
for i in range(len(S)): #遍历字符串的长度
S = S[-1] + S[:-1] #每次把最后一个字符放在第一个位置 并拼接上剩余的字符
if S < min_str: #字符串可以直接比较大小
min_str = S
return min_str
S = eval(input()) #输入是"abc" eval可以取出""内部的字符串 得到abc
print(func(S))
下面这种解法也可以，不过在某些样例下会超时：
class 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):
s1 = S #记录最小的字符串
num = len(S)
queue = Queue()
for i in reversed(range(num)): #输入字符串的 最后一个字符先入队
queue.enqueue(S[i])
i = 0
while i < num:
ch = queue.dequeue()
queue.enqueue(ch)
s2 = ''.join(queue.items)
if s2 < s1: #字符串可以直接比较大小
s1 = s2
i = i + 1
return s1
S = eval(input()) #输入是"abc" eval可以取出""内部的字符串 得到abc
print(func(S))
2. 最近的请求次数
def func(mylist):
newlist = [] #用列表 模拟队列
output = []
for i in range(len(mylist)):
newlist.append(mylist[i]) #右端作为队尾
while newlist[-1] - newlist[0] > 10000:
newlist.pop(0)
count = 0
for j in range(i+1,len(mylist)):
if mylist[j] == mylist[i]:
count = count + 1
else:
break
output.append(len(newlist)+count)
return output
mylist = eval(input()) #输入是 [1,2,3,...] eval()将字符串形式的[1,2,3...] 转换为列表形式
print(func(mylist))
3. 基数排序
def func(mylist):
#先处理个位数 有0-9十个队列，如果某个元素的个位数是i（i=0,...9）则加到相应的i队列中，每个队列按先进先出的顺序（从队首到队尾）连接起来
#再把 0-9十个队列 依次连接起来 （忽略空队列）；得到按个位数排序的结果。
#再对该结果，对十位数进行相同的处理...直到所有元素中的最大位数为止
#首先我们需要计算 列表中元素的最大位数
n = 1
while max(mylist)>= 10**n:
n = n + 1
for i in range(n): #依次遍历每一位 从个位开始
bucket = {}
for x in range(10): #每一位对应10个队列(0-9分别对应一个队列) 用列表来模拟队列
bucket.setdefault(x,[]) #把10个队列放在一个字典中
for item in mylist:
num = (item//(10**i))%10 #注意python中/是精确出发 返回浮点数；//是整除
bucket[num].append(item) #列表左端作为队首
#把每个队列串起来 得到按某一位排序后的结果
index = 0
for x in range(10):
if bucket[x] != []:
for y in bucket[x]:
mylist[index] = y
index = index + 1
return mylist
mylist = eval(input()) #输入是 [1,2,3,...] eval()将字符串形式的[1,2,3...] 转换为列表形式
print(func(mylist))
作者：CoreJT
