数据结构与算法数据结构与算法Python版版——第四周作业第四周作业
1有序队列（10分）
题目内容：
一开始给出了一个由小写字母组成的字符串 S。我们规定每次移动中，选择最左侧的字母，将其从原位置移除，并加到字符串的末尾。这样的
移动可以执行任意多次
返回我们移动之后可以拥有的最小字符串（注：在Python3中，字符串的大小可用不等号比较）。
输入格式:
S。S为仅含有小写字母的字符串，长度不超过100000。
输出格式：
一个与S等长的字符串。
输入样例：
“cba”
输出样例：
acb
分析：题目规定 “每次移动中，选择最左侧的字母，将其从原位置移除，并加到字符串的末尾”，这样的操作可以让人联想到 队列的属性：
FIFO。
解题思路：
1.先定义队列的类（注意根据题目要求定义：列表左侧为队首（出队），列表右侧为队尾（进队））
2.将目前的字符串设置为最小字符串
3.利用队列对字符串进行变形操作，将每次变形后的字符串，与当前最小字符串比较，如果比当前最小字符串小，则替换最小字符串。
4.利用count计数，总共迭代len(S)-1次，将所有元素都排进队尾一次，形成的字符串全部比较一次。
class Queue(list):
def isEmpty(self):
return self==[] def enqueue(self,item):
self.append(item)
def dequeue(self):
return self.pop(0)
def peek(self):
return self(-1)
def size(self):
return len(self)
def func(S):
q=Queue()
count=0
min_str=S #将当前的字符串设置为最小字符串
for c in S: #字符串中的所有元素进队
q.enqueue(c)
while count< q.size()-1: #总共迭代变换len(S)-1次
q.enqueue(q.dequeue()) #将队列最左侧的字符 从原位置移动到队列最右（末尾）
new_str="".join(q)
if new_str < min_str: #与当前最小字符串比较，如果比当前最小字符串小，则替换之
min_str = new_str
count+=1 #迭代一次，计数器+1
return min_str
S = eval(input())
print(func(S))
上面这种做法用到了队列的类，但是测试用例4因为运行时间超出，没有通过。
我在CSDN里面查了别人的作业，人家用的字符串切片的方法，优化了运行时间，还是同样的思路，只是把字符串直接当成队列来操作。
def func(S):
min_str=S
for i in range(len(S)):
S=S[1:]+S[0] if S < min_str: #与当前最小字符串比较，如果比当前最小字符串小，则替换之
min_str = S
return min_str
S = eval(input())
print(func(S))
测试样例全部通过。
2最近的请求次数（10分）
题目内容：
计算每个事件发生之时，往前算10000毫秒内有多少个事件发生，包含当事件；也即对于列表中的每个元素k，算出整个列表中有多少个元素介
于k-10000和k（两端均含）之间。
输入格式:
评论0