Leetcode 算法面试冲刺 栈与队列 理论 下(十九)

文章目录

队列 Queue

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
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(). 将第一个元素移出队列,返回它。

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
夏天老师讲的比三疯老师讲的更通俗易懂,特别好理解了。看来每个人的思路不一样,导致代码完全不同,而且难易程度也完全不同。

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]… 的顺序进行迭代。
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
想了半天,不会写,看了老师的讲解,写出来的

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

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)

421 · 简化路径

给定一个文件的绝对路径(Unix-style),请进行路径简化。

Unix中, . 表示当前目录, … 表示父目录。

结果必须以 / 开头,并且两个目录名之间有且只有一个 /。最后一个目录名(如果存在)后不能出现 / 。你需要保证结果是正确表示路径的最短的字符串。

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
这题是直接听的老师的讲解,如果让我自己做,我想不到怎么做。

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

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)

575 · 字符串解码

给出一个表达式 s,此表达式包括数字,字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式),请将这个表达式展开成一个字符串。
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
看了老师的讲解思路写出来的代码:

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)
            

Leetcode 算法面试冲刺 栈与队列 理论 下(十九)
⚠️注意,老师说不要被代码,你要去记录的是一个题目的解题过程。当你可以理解这个过程了,代码转化就很容易了。看到一道题,可以马上想到解题思路。

上一篇:python月份的加减


下一篇:洛谷 P1335 / UOJ #123 - [NOI2013] 小Q的修炼(提交答案题)