sep 8
parentheses
20
# EASY
# use Stack
# scan the String s:
# append all left brackets {, (, [ to the stack
# if right brackets ],),} appear pop the stack and compare left and right
# Time O(N) Space O(N)
22
# MEDIUM
# combination == DFS
# base case:
# left brakets == n and right brakets == n
# recursion Rule:
# append left if left < n
# append right if left > right
# Time O(2^N) Space O(N)
32
# HARD
# asking for longest valid parenthese string.
# input ")()())" => 4 because s[1:4] is the longese valid substring
# dp[N] each index represents the number of valid parenthese at that place:
# scan the string:
# if string[i-1:i] == "()" means we found one => dp[i] = dp[i-2] + 2
# elif string[i-1] != "(" check s[i - dp[i-1] -1] and s[i] == "()"
# => dp[i] = dp[i-1] + dp[i - dp[i-1]-2] +2 eg."()((()))"
# ^ ^
# | |
# dp[i-dp[i-1]-2]
# Time O(N) Space O(N)
241
# MEDIUM
# this is like Word Break => DFS + Memoization
# define a lambda x,y: x {+,-,*} y
# scan the string s:
# break at operators "+-*" => left = s[:operator] right = s[operator+1:]
# recurse each left, right:
9月打卡第8天,6道题
Employee Free Time: 基本是跟meeting room一样,线扫,sort,或者heap都能解
Longest Word in Dictionary: 先sort按lexicographical排序,然后用一个hashset记录能从build的单词,然后判断
Maximum Length of Repeated Subarray: 经典的dp题,注意index
Find the Closest Palindrome: 把string拆成一半,然后末尾数加一减一和本身构造candidate,循环一次比较就行。还要注意考虑len +1 -1的情况。这两种情况就是999999和10001就行
Basic Calculator III: 有点长,两个stack,分别记录operator和num,然后写个function判断operator的优先级
Number of Atoms: stack解决,每次遇到(开一个新的cnt记录原子的个数就行。。