Leetcode刷题复习|Leetcode 刷题必须Review 十七 Lintcode（423 492 541 421 575）算法|职场和发展|leetcode

文章目录

423 · 有效的括号序列
492 · 队列维护
541 · 左旋右旋迭代器 II
421 · 简化路径
575 · 字符串解码

423 · 有效的括号序列给定一个字符串所表示的括号序列，包含以下字符： ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’，判定是否是有效的括号序列。
括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。

Leetcode刷题复习|Leetcode 刷题必须Review 十七 Lintcode（423 492 541 421 575）

文章图片

def isValidParentheses(self, s): # write your code here if not s: return True stack = [] for i in s: if i == '(' or i == '[' or i == '{': stack.append(i) else: if not stack: return False ele = stack.pop() if (i == ')' and ele == '(') or (i == ']' and ele == '[') or (i == '}' and ele == '{'): continue else: return False return not stack

492 · 队列维护 【Leetcode刷题复习|Leetcode 刷题必须Review 十七 Lintcode（423 492 541 421 575）】按链表实现队列。支持以下基本方法：
enqueue(item).将新元素放入队列中。
dequeue(). 将第一个元素移出队列，返回它。

文章图片

看了之前写的改了一下

class MyQueue: """ @param: item: An integer @return: nothing """ def __init__(self): self.queue = Nonedef enqueue(self, item): # write your code here if not self.queue: self.queue = ListNode(item) self.dummy = ListNode(-1, self.queue)else: self.queue.next = ListNode(item) self.queue = self.queue.next""" @return: An integer """ def dequeue(self): # write your code here print(self.dummy.next.val) res = self.dummy.next.val self.dummy = self.dummy.next return res

下面是我之前写的：

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]… 的顺序进行迭代。

文章图片

没写出来。

from collections import deque class ZigzagIterator2: """ @param: vecs: a list of 1d vectors """ def __init__(self, vecs): # do intialization if necessary max_col = max([len(vec) for vec in vecs]) self.queue = deque() for j in range(max_col): for i in range(len(vecs)): try: self.queue.append(vecs[i][j]) except IndexError: pass""" @return: An integer """ def _next(self): # write your code here self.queue.popleft()""" @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

看了之前写的，果然忘记了

import collectionsclass 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 = https://www.it610.com/article/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 simplify_path(self, path: str) -> str: # write your code here stack = [] li = path.split('/') for i in li: if i.isalnum(): stack.append(i) elif i == ".": continue elif i == "..": if stack: stack.pop() return "/" + "/".join(stack)

文章图片

文章图片

下面是官方答案：

def simplifyPath(self, path): path = path.split('/') stack = [] for i in path: if i == '..': if len(stack): stack.pop() elif i != '.' and i != '': stack.append(i) return '/' + '/'.join(stack)

按照答案，改了下代码：

def simplify_path(self, path: str) -> str: # write your code here stack = [] li = path.split('/') for i in li: if i == "..": if stack: stack.pop() elif i != "." and i != "": stack.append(i) return '/' + '/'.join(stack)

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

文章图片

不会。直接看之前写的吧。
下面是之前写的。看了半天才想起来怎么做的。

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)

又自己写了一遍。学习了方法isinstance

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)ss = [] while stack: ss.append(stack.pop()) ss.reverse() return ''.join(ss)