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: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: 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.