数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序设计一个队列，将最近使用的元素移动到队列的末尾
假设，我们需要设计一个队列，将最近使用的元素移动到队列的末尾。该队列将初始化为整数1到n。现在我们需要构建一个函数，以便在每次调用该函数时，将输入位置的数值移动到队列的末尾。我们将多次调用该函数，并且该函数在执行移动任务的同时将返回当前位于队列末尾的数值。
因此，如果队列初始化为值n=5，或者它包含从1到5的值；并且执行移动操作的位置分别为5、2、3和1，则输出将为5、2、4、1。
为了解决这个问题，我们将遵循以下步骤：
- i := 数组索引中位置-1，其中值k可以插入到右侧以保持排序顺序
- x := 从data[i]中删除（k - index[i]）个元素
- 对于ii从i+1到index的大小，执行以下操作
- index[ii] := index[ii] - 1
- 如果data的最后一个元素的大小>= nn，则
- 在列表data的末尾插入一个新列表
- 在列表index的末尾插入n
- 在data的末尾插入x
- 如果data[i]为空，则
- 从data中删除第i个元素
- 从index中删除第i个元素
- 返回x
示例
让我们看看以下实现以获得更好的理解：
from bisect import bisect_right from math import sqrt class TestQueue: def __init__(self, n): self.n = n self.nn = int(sqrt(n)) self.data = [] self.index = [] for i in range(1, n+1): ii = (i-1)//self.nn if ii == len(self.data): self.data.append([]) self.index.append(i) self.data[-1].append(i) def solve(self, k): i = bisect_right(self.index, k)-1 x = self.data[i].pop(k - self.index[i]) for ii in range(i+1, len(self.index)): self.index[ii] -= 1 if len(self.data[-1]) >= self.nn: self.data.append([]) self.index.append(self.n) self.data[-1].append(x) if not self.data[i]: self.data.pop(i) self.index.pop(i) return x queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
输入
queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
输出
5 2 4 1
更新于：2021年10月7日
431 次浏览
广告