1. 列表的定義
先進(jìn)先出（FIFO）
2. 用法
類代碼如下：
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
3. 算法運(yùn)用
① 約瑟夫環(huán)
劍指offer62
def __init__(self):
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 is_empty(self):
return self.items == []
# num為傳遞的次數(shù)，每隔一個(gè)人就是傳遞1次
class Solution:
def lastRemaining(self, n: int, num = 2) -> int:
lst = Queue()
for i in range(n):
lst.enqueue(i)
while lst.size() >1:
for i in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
return lst.dequeue()
先按頭消去，每隔一個(gè)消去；再從第二個(gè)每隔一個(gè)消去
【1,2,3,4,5,6】→【2,4,6】→【2,6】→【6】
這種方法代碼如下：
class Queue:
def __init__(self):
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 is_empty(self):
return self.items == []
# num為傳遞的次數(shù)，每隔一個(gè)人就是傳遞1次
class Solution:
def lastRemaining(self, n: int, num = 1) -> int:
lst = Queue()
flag = 0
for i in range(1, n+1):
lst.enqueue(i)
mark = lst.size() % 2
while lst.size() // 2 > 0:
if flag == 0:
lst.dequeue()
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 1
if mark == 0:
lst.enqueue(lst.dequeue())
else:
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 0
if mark == 0:
lst.enqueue(lst.dequeue())
return lst.dequeue()
LeetCode 390. 消除游戲
#采用隊(duì)列和棧的思想，不過雖然超時(shí)，但是是正確的。
class Queue:
def __init__(self):
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 is_empty(self):
return self.items == []
# num為傳遞的次數(shù)，每隔一個(gè)人就是傳遞1次
class Solution:
def lastRemaining(self, n: int, num = 1) -> int:
lst = Queue()
flag = 0
for i in range(1, n+1):
lst.enqueue(i)
while lst.size() // 2 > 0:
mark = lst.size() % 2
if flag == 0:
lst.dequeue()
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 1
if mark == 0:
lst.enqueue(lst.dequeue())
else:
lst.items.pop(0)
for i in range(lst.size()//2):
for j in range(num):
lst.items.append(lst.items.pop(0))
lst.items.pop(0)
flag = 0
if mark == 0:
lst.items.append(lst.items.pop(0))
return lst.dequeue()
4 雙向隊(duì)列
兩邊可以加?xùn)|西與減東西
image.png
python有雙向隊(duì)列的庫，可以直接導(dǎo)入：
from collections import deque
image.png
題目：
- LeetCode 239：雙向隊(duì)列
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
from collections import deque
queue = deque()
for i in range(len(nums)):
if queue and queue[0] < i-k+1:
queue.popleft()
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
if i >= k-1:
res.append(nums[queue[0]])
return res
- Leetcode 9. Palindrome Number
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
if x == 0:
return True
res = deque()
for i in str(x):
res.append(i)
mark = True
while len(res) > 1 and mark is True:
if res.pop() != res.popleft():
mark = False
return mark
