Shopee 8.2笔试
第一题：找平衡点，略
第二题： 数字n分成m份有多少种分发，主要m份不能为空。
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))
3. 解析xml，我用的是数去做的，先构建树，然后再在树上进行遍历：
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"))