文章目录
队列 Queue
deque注意发音，它是两端都可以进出的数据结构。如果将deque当作queue来用，需要做一些限制，一头只能进，另一头只能出。昨天学的Queue也是可以的，get是出，put是进。
出队和得到队头元素的区别在于：出队后元素就不在队列里了。而得到队头元素，只是peek一下地址，元素依然还在。
from queue import Queue
q = Queue()
for i in range(10):
q.put(i)
while not q.empty():
print(q.get(), end=" ")
print()
print(q.qsize())
492 · 队列维护
按链表实现队列。支持以下基本方法：
- enqueue(item).将新元素放入队列中。
- dequeue(). 将第一个元素移出队列，返回它。
夏天老师讲的比三疯老师讲的更通俗易懂，特别好理解了。看来每个人的思路不一样，导致代码完全不同，而且难易程度也完全不同。
class MyQueue:
"""
@param: item: An integer
@return: nothing
"""
def __init__(self):
self.beforehead = self.tail = ListNode(-1)
def enqueue(self, item):
# write your code here
self.tail.next = ListNode(item)
self.tail = self.tail.next
"""
@return: An integer
"""
def dequeue(self):
# write your code here
if self.beforehead.next is None:
return -1
head_val = self.beforehead.next.val
self.beforehead = self.beforehead.next
return head_val
541 · 左旋右旋迭代器 II
在本题中，你将得到一个列表vecs，其中包括 k 个一维向量。
你的任务是通过 next 函数一个个地返回向量中的元素，按照 vecs[0][0], vecs[1][0]… vecs[k - 1][0], vecs[0][1], vecs[1][1]… vecs[k - 1][1], vecs[0][2], vecs[1][2]… vecs[k - 1][2]… 的顺序进行迭代。
想了半天，不会写，看了老师的讲解，写出来的
import collections
class ZigzagIterator2:
"""
@param: vecs: a list of 1d vectors
"""
def __init__(self, vecs):
# do intialization if necessary
self.queue = collections.deque()
for vec in vecs:
if len(vec) > 0:
self.queue.append([iter(vec), len(vec)])
"""
@return: An integer
"""
def _next(self):
# write your code here
vec_iter, vec_len = self.queue.popleft()
value = next(vec_iter)
vec_len -= 1
if vec_len > 0:
self.queue.append([vec_iter, vec_len])
return value
"""
@return: True if has next
"""
def hasNext(self):
# write your code here
if self.queue:
return True
# Your ZigzagIterator2 object will be instantiated and called as such:
# solution, result = ZigzagIterator2(vecs), []
# while solution.hasNext(): result.append(solution.next())
# Output result
栈
421 · 简化路径
给定一个文件的绝对路径(Unix-style)，请进行路径简化。
Unix中, . 表示当前目录, … 表示父目录。
结果必须以 / 开头，并且两个目录名之间有且只有一个 /。最后一个目录名(如果存在)后不能出现 / 。你需要保证结果是正确表示路径的最短的字符串。
这题是直接听的老师的讲解，如果让我自己做，我想不到怎么做。
class Solution:
"""
@param path: the original path
@return: the simplified path
"""
def simplifyPath(self, path):
# write your code here
arr = path.split('/')
stack = []
for i in arr:
if i == '..':
if stack:
stack.pop()
elif i == '' or i == '.':
continue
else:
stack.append(i)
if not stack: return '/'
string = ''
while stack:
string = '/' + stack.pop() + string
return string
575 · 字符串解码
给出一个表达式 s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。
看了老师的讲解思路写出来的代码：
class Solution:
"""
@param s: an expression includes numbers, letters and brackets
@return: a string
"""
def expressionExpand(self, s):
# write your code here
stack = []
number = 0
for ch in s:
if ch.isdigit():
number = number * 10 + int(ch)
elif ch == '[':
stack.append(number)
number = 0
elif ch == ']':
strs = []
while stack and not isinstance(stack[-1], int):
strs.append(stack.pop())
strs.reverse()
repeat = stack.pop()
for _ in range(repeat):
stack.append("".join(strs))
else:
stack.append(ch)
strs = []
while stack:
strs.append(stack.pop())
strs.reverse()
return ''.join(strs)
⚠️注意，老师说不要被代码，你要去记录的是一个题目的解题过程。当你可以理解这个过程了，代码转化就很容易了。看到一道题，可以马上想到解题思路。