Skip to content

Friday, July 17th, 2020 🤔

class Solution:
def isValidBST(self, root: TreeNode) -> bool:

1. Recursion

Design a new helper function to help iterate left to right:
def helper(node, lower = float('-inf'), upper = float('inf')):
#‘inf’ means the infinite value
Approach:
As long as the left sub-tree is not None, and all the node.val in the left sub-tree is less than the root.val; if the right sub-tree is not none, then all the node.val in the right is bigger than the root.val.
class Solution: def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ def helper(node, lower = float('-inf'), upper = float('inf')): if not node: return True val = node.val if val <= lower or val >= upper: return False
if not helper(node.right, val, upper): return False if not helper(node.left, lower, val): return False return True
return helper(root)

2. In-order traversal

Approach:
Use a stack to store the nodes
class Solution: def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ stack, inorder = [], float('-inf') while stack or root: while root: stack.append(root) root = root.left root = stack.pop() # 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树 if root.val <= inorder: return False inorder = root.val root = root.right
return True

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"Output: 2Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"Output: 4Explanation: The longest valid parentheses substring is "()()"

1. DP

1. if s ended with ‘(’
return 0
2. if s ended with ‘)’
2.1 if s[i-1] == ‘)’ : s[i-1 - dp[i-1]]
2.2 if s[i-1] == ')' and s[i-1-dp[i-1]] == '(' and i-1-dp[i-1]>=0:
def longestValidParentheses(self, s: str) -> int: # 状态:以该点结尾的最长有效括号的子串长度 dp = [0 for _ in range(len(s))] if len(s) < 2: return 0 if s[1] == ')' and s[0] == '(': dp[1] = 2 if len(s) == 2: return dp[1]
for i in range(2, len(s)): if s[i] == '(': ## 一种情况 dp[i] = 0 continue if s[i] == ')': ## 另一种情况 if s[i-1] == '(': ## 细分 dp[i] = dp[i-2] +2 if s[i-1] == ')' and s[i-1-dp[i-1]] == '(' and i-1-dp[i-1]>=0: ## only for python dp[i] = dp[i-1-dp[i-1]-1] + 2 + dp[i-1] print(dp) return max(dp)
2. Stack
def longestValidParentheses(self, s: str) -> int: # # 在刚才的方法上进行优化就好了,可以减少空间复杂度 # stack = [-1] indexing from the end # res = 0 # for i in range(len(s)): # if s[i] == '(': # stack.append(i) # continue # stack.pop() # if not stack: stack.append(i) # else: # # print(i, stack) # res = max(res, i - stack[-1]) # return res



# class Solution:# def isBalanced(self, root: TreeNode) -> bool:# def helper(root):# if root == None: return 0# if helper(root.left) == -1: return -1# if helper(root.right) == -1: return -1 # return max(helper(root.left), helper(root.right)) + 1 if abs(helper(root.left) - helper(root.right)) <= 1 else -1 # return helper(root) != -1
time limit exceeded!

class Solution: def isBalanced(self, root: TreeNode) -> bool: if not root: return True return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \ self.isBalanced(root.left) and self.isBalanced(root.right)
def depth(self, root): if not root: return 0 return max(self.depth(root.left), self.depth(root.right)) + 1
Passed !

class Solution: def constructArr(self, a: List[int]) -> List[int]: b, tmp = [1] * len(a), 1 for i in range(1, len(a)): b[i] = b[i - 1] * a[i - 1] # 下三角 for i in range(len(a) - 2, -1, -1): tmp *= a[i + 1] # 上三角 b[i] *= tmp # 下三角 * 上三角 return b
image.png

Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.