贝壳找房 笔试8.13
第一题：模拟
class Solution: def FarmerNN(self , n , m ): #m=m-1 a,b = (m-1)//(n-1),(m-1)%(n-1) res = [0]*n res [0] = 1 + a//2 res[-1] = (a+1)//2 for i in range(1,n-1): res[i] = a if a%2==0: for i in range(1,1+b): res[i]+=1 else: for i in range(n-2,max(-1,n-2-b),-1): res[i]+=1 return res # write code here
第二题：模拟
class Solution: def NS_String(self , s , k ): book = set(sorted(list(set(s)))[:k]) res = "" for c in s: if c not in book: res+=c return res第三题：
class Solution:
def section(self , a , t ):
record = {}
res = 0
last = -1
for i in range(len(a)):
v = t^a[i]
l = max(record.get(v,-1),last)
if i-l>=2:
res +=(i-l-1)
#res+=((i-l)*(i-l-1)//2)
record[a[i]] = i
last = max(last,l)
return res 第四题：求相同的子树class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
import sys
sys.setrecursionlimit(1000000)
class Solution:
def maxSubTree(self , root :TreeNode):
def change(root:TreeNode):
if root is None:
return
if root.left is None and root.right is None:
root.val = '0'
elif root.left is None:
root.val = '1'
elif root.right is None:
root.val= '2'
else:
root.val= '3'
change(root.left)
change(root.right)
change(root)
def check(p:TreeNode,q:TreeNode):
if p is None and q is None:
return True
if p is None or q is None:
return False
res = check(p.left,q.left) and check(p.right,q.right)
return res
record = {}
self.res = 0
def get_result(p:TreeNode):
if p is None:
return ""
l,r = get_result(p.left),get_result(p.right)
key = l+p.val+r
if key in record:
# self.res = max(self.res,len(key))
if self.res<len(key):
for q in record[key]:
if check(p,q):
self.res = len(key)
else:
record[key] = []
record[key].append(p)
return key
get_result(root)
return self.res
