771 · 二阶阶乘

给定一个数n，返回该数的二阶阶乘。在数学中，正整数的二阶阶乘表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。

def doubleFactorial(self, n):# Write your code hereres_odd, res_even = 1, 1for i in range(n, 0, -1):if n & 1 == 1 and i & 1 == 1:res_odd *= ielif n & 1 == 0 and i & 1 == 0:res_even *= ireturn res_odd if n & 1 == 1 else res_even

下面是官方答案，太妙了

def doubleFactorial(self, n):if n <= 2:return nreturn n * self.doubleFactorial(n - 2)

还有一个比较好的答案：

def doubleFactorial(self, n):# Write your code hereres = 1for i in range(n, -1, -2):if i != 0:res *= ireturn res

只要肯多想一步，代码量就会骤减。

495 · 实现栈

实现一个栈，可以使用除了栈之外的数据结构

class Stack:"""@param: x: An integer@return: nothing"""def __init__(self):self.stack = []def push(self, x):# write your code hereself.stack.append(x)"""@return: nothing"""def pop(self):# write your code hereself.stack.pop()"""@return: An integer"""def top(self):# write your code herereturn self.stack[-1]"""@return: True if the stack is empty"""def isEmpty(self):# write your code hereprint(self.stack)return False if self.stack else True

492 · 队列维护

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

class MyQueue:def __init__(self):self.before_head = self.tail = ListNode(-1)"""@param: item: An integer@return: nothing"""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.before_head.next is None:return -1res_val = self.before_head.next.valself.before_head = self.before_head.nextreturn res_val

423 · 有效的括号序列

class Solution:"""@param s: A string@return: whether the string is a valid parentheses"""def isValidParentheses(self, s):# write your code hereif not s: return Truestack = []for ch in s:if ch == '(' or ch == '[' or ch =='{':stack.append(ch)elif len(stack) == 0:return Falseelif ch == ')' and stack[-1] == '(' or \ch == ']' and stack[-1] == '[' or \ch == '}' and stack[-1] == '{' :stack.pop()else:return Falsereturn not stack

对比下昨天写的：

def isValidParentheses(self, s):# write your code hereif not s: return Truestack = []for i, ch in enumerate(s):if ch == '(' or ch == "[" or ch == '{':stack.append(ch)else:if not stack:return Falseelif (ch == ')' and stack[-1] == '(') or \(ch == ']' and stack[-1] == '[') or \(ch == '}' and stack[-1] == '{'):stack.pop()else:return Falsereturn not stack

在这里插入代码片

263 · 小括号匹配

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

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

class Solution:"""@param string: A string@return: whether the string is a valid parentheses"""def matchParentheses(self, string):# write your code hereif not string: return Truestack = []for ch in string:if ch == '(':stack.append(ch)else:if not stack:return Falseelif ch == ')' and stack[-1] == '(':stack.pop()return not stack

官方的答案，有点像摩尔voting：

def matchParentheses(self, string):matched = 0for parenthese in string:if parenthese == '(':matched += 1else:matched -= 1if matched < 0:return Falsereturn matched == 0