第一题:找平衡点,略
第二题: 数字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"))
全部评论
(4) 回帖