首页 > 贝壳找房 笔试8.13
头像
石郎
编辑于 2021-08-14 00:23
+ 关注

贝壳找房 笔试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

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐