队列 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 · 队列维护

按链表实现队列。支持以下基本方法：

1. enqueue(item).将新元素放入队列中。
2. 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 hereself.tail.next = ListNode(item)self.tail = self.tail.next"""@return: An integer"""def dequeue(self):# write your code hereif self.beforehead.next is None:return -1head_val = self.beforehead.next.valself.beforehead = self.beforehead.nextreturn 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 collectionsclass ZigzagIterator2:"""@param: vecs: a list of 1d vectors"""def __init__(self, vecs):# do intialization if necessaryself.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 herevec_iter, vec_len = self.queue.popleft()value = next(vec_iter)vec_len -= 1if vec_len > 0:self.queue.append([vec_iter, vec_len])return value"""@return: True if has next"""def hasNext(self):# write your code hereif 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 herearr = path.split('/')stack = []for i in arr:if i == '..':if stack:stack.pop()elif i == '' or i == '.':continueelse:stack.append(i)if not stack: return '/'string = ''while stack:string = '/' + stack.pop() + stringreturn string

575 · 字符串解码

给出一个表达式 s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。


看了老师的讲解思路写出来的代码：

class Solution:"""@param s: an expression includes numbers, letters and brackets@return: a string"""def expressionExpand(self, s):# write your code herestack = []number = 0for ch in s:if ch.isdigit():number = number * 10 + int(ch)elif ch == '[':stack.append(number)number = 0elif 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)

⚠️注意，老师说不要被代码，你要去记录的是一个题目的解题过程。当你可以理解这个过程了，代码转化就很容易了。看到一道题，可以马上想到解题思路。