資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告