291. Word Pattern II （Medium）
Given a pattern and a string s, return true if s matches the pattern.
A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
def helper(pattern,s,dic1,dic2):
if not s: return not pattern
if not pattern: return not s
key = pattern[0]
res=False
for i in range(1,len(s)+1):
dic1_copy=dic1.copy()
dic2_copy=dic2.copy()
s_val = s[:i]
#print(key,s_val)
if key in dic1_copy and dic1_copy[key]!=s_val:
res=res or False
continue
else:
dic1_copy[key]=s_val
if s_val in dic2_copy and dic2_copy[s_val]!=key:
res=res or False
continue
else:
dic2_copy[s_val]=key
s_rest = s[i:]
res = res or helper(pattern[1:],s_rest,dic1_copy,dic2_copy)
#if res:
# print(pattern,s)
return res
return helper(pattern,s,dict(),dict())
#MY ANSWER
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
def bt(p,s, a2b,b2a):
#print(p,s,a2b,b2a)
if not p and not s: return True
if not p: return not s
res = False
a = p[0]
a_rest = p[1:]
a2b_copy=a2b.copy()
b2a_copy=b2a.copy()
for i in range(1,len(s)+1):
b = s[:i]
print(b)
b_rest = s[i:]
if a in a2b and a2b[a]!=b:
continue
if b in b2a and b2a[b]!=a:
continue
a2b_copy[a] = b
b2a_copy[b] = a
res = res or bt(a_rest,b_rest,a2b_copy,b2a_copy)
return res
return bt(pattern,s,dict(),dict())
#MYANSWER
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
res = False
def bt(p, s, a2b,b2a):
nonlocal res
if not p:
res = not s
return
p0 = p[0]
prest = p[1:]
for i in range(1,len(s)+1):
s0=s[:i]
srest = s[i:]
#case alreay meet
if p0 in a2b and a2b[p0]==s0 and s0 in b2a and b2a[s0]==p0:
bt(prest,srest,a2b,b2a)
#case not meet
elif p0 not in a2b:
if s0 in b2a and b2a[s0]!=p0:
continue
a2b[p0] = s0
b2a[s0]=p0
bt(prest,srest,a2b,b2a)
del a2b[p0]
del b2a[s0]
bt(pattern,s,dict(),dict())
return res
知道使用backtracking，但是得小心 dic1 dic2 copy问题，以及res = res or False， 既然当前s[:i] 已经是False了就skip，所以用cotinue。
292. Nim Game （Easy）
You are playing the following Nim Game with your friend:
Initially, there is a heap of stones on the table.
You and your friend will alternate taking turns, and you go first.
On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
The one who removes the last stone is the winner.
class Solution:
def canWinNim(self, n: int) -> bool:
# dp [0] [1] [2] [3] [4] [5]
# True True True True False
dp = [False] * (n+1)
if n<=3: return True
dp[0]=True
dp[1]=True
dp[2]=True
dp[3]=True
for nn in range(2,n+1):
for i_select in [1,2,3]:
dp[nn] = dp[nn] or (not dp[nn-i_select])
#print(dp)
return dp[n]
class Solution:
def canWinNim(self, n: int) -> bool:
# 只要对方等于4个 对方必然输。
# 我先开始，如何让对方等于4个
# n=4 我输
# n=5 我选1
# n=6 我选2
# n=7 我选3
# n=8 我选1 不行 我选2 不行 我选3 还是不行
# n=9 选1
# n=10 选2
# n=11 选3
# n=12 都不行
return not n%4==0
用dp写了一个答案，但time limit exceeded。 逐渐发现规律。。。就是是否被4整除。
293. Flip Game （Easy）
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].
class Solution:
def generatePossibleNextMoves(self, currentState: str) -> List[str]:
res= []
for i in range(len(currentState)-1):
if currentState[i]=='+' and currentState[i+1]=='+':
res.append(currentState[:i]+'--'+currentState[i+2:])
return res
class Solution:
def generatePossibleNextMoves(self, currentState: str) -> List[str]:
res = []
for i in range(1,len(currentState)):
if currentState[i]=='+' and currentState[i-1]=='+':
res.append(currentState[:i-1]+'--'+currentState[i+1:])
return res
294. Flip Game II (Medium)
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return true if the starting player can guarantee a win, and false otherwise.
class Solution:
def canWin(self, currentState: str) -> bool:
return any(currentState[i:i+2] == '++' and not self.canWin(currentState[:i] + '--' + currentState[i+2:]) for i in range(len(currentState)))
#ANSWER
class Solution(object):
_memo = {}
def canWin(self, s):
memo = self._memo
if s not in memo:
memo[s] = any(s[i:i+2] == '++' and not self.canWin(s[:i] + '--' + s[i+2:])
for i in range(len(s)))
return memo[s]
#ANSWER
class Solution(object):
def canWin(self, s):
memo = {}
def can(s):
if s not in memo:
memo[s] = any(s[i:i+2] == '++' and not can(s[:i] + '--' + s[i+2:])
for i in range(len(s)))
return memo[s]
return can(s)
#ANSWER
class Solution:
def canWin(self, currentState: str) -> bool:
res = False
for i in range(1,len(currentState)):
if currentState[i-1:i+1]=='++':
res = res or not self.canWin(currentState[:i-1]+'--'+currentState[i+1:])
return res
295. Find Median from Data Stream （Hard）
from heapq import *
class MedianFinder:
def __init__(self):
self.small = [] # the smaller half of the list, max heap (invert min-heap)
self.large = [] # the larger half of the list, min heap
def addNum(self, num):
if len(self.small) == len(self.large):
heappush(self.large, -heappushpop(self.small, -num))
else:
heappush(self.small, -heappushpop(self.large, num))
def findMedian(self):
if len(self.small) == len(self.large):
return float(self.large[0] - self.small[0]) / 2.0
else:
return float(self.large[0])
最简单方法的是sort， 复杂点的比如答案，用了min heap。 思路： small 保存较小的，large保存较大的， 由于需要small的最大元素，minheap头是最小元素，所以push到small要反向。 large能最多比small多存一个元素。 heappushpop同时 push一个元素取出一个元素。TimeCoplex O(logn).
296. Best Meeting Point （Hard）
Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.
The total travel distance is the sum of the distances between the houses of the friends and the meeting point.
The distance is calculated using Manhattan Distance
class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
X = []
Y = []
for r in range(m):
for c in range(n):
if grid[r][c]==1:
X.append(r)
Y.append(c)
X.sort()
Y.sort()
R = X[len(X)//2]
C = Y[len(Y)//2]
def mindis1d(xs,o):
dis = 0
for x in xs:
dis += abs(x-o)
return dis
return mindis1d(X,R)+mindis1d(Y,C)
第一想法多次BFS。。。一次cost mn 最差情况有mn个1， 所以最差有O（mmnn）。 不可行。 答案思路：1）分解成2个1d的问题，最小值点出现在median位置。 O(mnlogmn) 2）只要不sort，时间复杂度还能降低到O(mn) 。 拉出来行和列分别遍历即可。
297. Serialize and Deserialize Binary Tree （Hard）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
res = []
def pre(root):
if not root:
res.append('@')
return
res.append(root.val)
pre(root.left)
pre(root.right)
pre(root)
return '#'.join(map(str,res))
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = data.split('#')
def pre(data):
cur = data.pop(0)
if cur!='@':
root = TreeNode(int(cur))
root.left = pre(data)
root.right = pre(data)
return root
else:
return None
return pre(data)
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
有个什么儿子兄弟表示法，但忘记了。。。这个题目只用了preorder。 但要注意递归时候，传入data必须是list，这样随着递归list本身会变化，要是str会出错。
298. Binary Tree Longest Consecutive Sequence （Medium）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
res=[0]
def pre(root,parent, length):
if not root:
return
if parent and root.val==parent.val+1:
length+=1
else:
length=1
res[0]=max(res[0],length)
pre(root.left,root,length)
pre(root.right,root,length)
pre(root,None,0)
return res[0]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
res = 0
if not root: return res
def helper(node,c):
nonlocal res
res = max(res,c)
if not node:
return
if node.left:
if node.val+1==node.left.val:
helper(node.left,c+1)
else:
helper(node.left,1)
if node.right:
if node.val+1==node.right.val:
helper(node.right,c+1)
else:
helper(node.right,1)
helper(root,1)
return res
299. Bulls and Cows （Medium）
class Solution:
def getHint(self, secret: str, guess: str) -> str:
A = 0
B = 0
dicA= collections.defaultdict(int)
dicB= collections.defaultdict(int)
for a,b in zip(secret,guess):
if a==b:
A+=1
else:
dicA[a]+=1
dicB[b]+=1
for b in dicB:
if b in dicA:
B+= min(dicA[b],dicB[b])
return str(A)+'A'+str(B)+'B'
300. Longest Increasing Subsequence (Medium)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# dp[i] means the LIS till ith number including i
# dp[i] = max(dp[i],dp[j]+1) j<i and nums[j]<nums[i]
if not nums: return 0
if len(nums)==1: return 1
dp = [1]*len(nums)
for i in range(1,len(nums)):
for j in range(i):
if nums[j]<nums[i]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
res =[]
while nums:
cur = nums.pop(0)
idx =bisect.bisect_left(res,cur)
if len(res)==idx:
res.append(cur)
else:
res[idx]=cur
return len(res)
classical DP problem O(n^2) binary search method, O(nlogn)