Shopee 8.2笔试

class Solution:
    def divide(self, n, k) :
        dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
        dp[0][0]=1
        for i in range(1,k+1):
            for j in range(0,n+1):
                if j-i>=0:
                    dp[i][j] = dp[i][j-i]+dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[k][n]-dp[k-1][n]


print(Solution().divide(7,3))

class Solution:
    def GetXMLValue(self, inxml, path) :
        tree = {}
        
        def dfs(root,txml:str):
            if len(txml)==0:
                return
            if txml.startswith('</'):
                idx = 2
                while idx<len(txml) and txml[idx]!='>':
                    idx+=1
                dfs(root,txml[idx+1:])
                return
            if txml.startswith('<'):
                idx = 1
                while idx<len(txml) and txml[idx]!='>':
                    idx+=1
                root[txml[1:idx]]={}
                dfs(root[txml[1:idx]],txml[idx+1:])
                return
            idx = 0
            while idx<len(txml) and txml[idx]!='<':
                idx+=1
            root['key__spx'] = txml[:idx]

            dfs(root,txml[idx:])
        # 构建树
        dfs(tree,inxml)
        res = ""
        if len(path)==0:
            return res
        paths = path.split('.')
        def find(root,tpaths):
            if len(tpaths)==0:
                if 'key__spx' in root:
                    return root['key__spx']
                else:
                    return ""
            if tpaths[0] in root:
                return find(root[tpaths[0]],tpaths[1:])
            else:
                return ""
        # 判断path是否在树上
        return find(tree,paths)
print(Solution().GetXMLValue("<people><name>shopee</name></people>","people.name"))
print(Solution().GetXMLValue("<people><name>shopee</name></people>","people.age"))