423 · 有效的括号序列

给定一个字符串所表示的括号序列，包含以下字符： ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’， 判定是否是有效的括号序列。

括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。

def isValidParentheses(self, s):# write your code hereif not s: return Truestack = []for i in s:if i == '(' or i == '[' or i == '{':stack.append(i)else:if not stack: return Falseele = stack.pop()if (i == ')' and ele == '(') or (i == ']' and ele == '[') or (i == '}' and ele == '{'):continueelse:return Falsereturn not stack

492 · 队列维护

按链表实现队列。支持以下基本方法：
enqueue(item).将新元素放入队列中。
dequeue(). 将第一个元素移出队列，返回它。

看了之前写的改了一下

class MyQueue:"""@param: item: An integer@return: nothing"""def __init__(self):self.queue = Nonedef enqueue(self, item):# write your code hereif 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 hereprint(self.dummy.next.val)res = self.dummy.next.valself.dummy = self.dummy.nextreturn 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 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]… 的顺序进行迭代。

没写出来。

from collections import deque
class ZigzagIterator2:"""@param: vecs: a list of 1d vectors"""def __init__(self, vecs):# do intialization if necessarymax_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 hereself.queue.popleft()"""@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

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

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 simplify_path(self, path: str) -> str:# write your code herestack = []li = path.split('/')for i in li:if i.isalnum():stack.append(i)elif i == ".":continueelif 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 herestack = []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 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)

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

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