数据结构与算法数据结构与算法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（两端均含）之间。
输入格式:
下载后可阅读完整内容，剩余5页未读，立即下载
weixin_38548589
- 粉丝: 7
- 资源: 909
我的内容管理
展开
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆：CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析：财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合：快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计：自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南：解决兼容性与Office冲突
- MFC实现学生信息管理系统：登录与数据库操作
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
