腾讯音乐 9.8笔试
第一题：去除重复字符的最小操作次数：
第二题：从有重复数字的前序和中序遍历序列构造所有可能的二叉树
第三题：新平衡二叉树的最小权值和
class Solution: def getMinCount(self, str: str) -> int: n = len(str) dic = collections.Counter(str) ans = 0 # 记录去除原始字符串中的重复元素的操作次数 for value in dic.values(): ans += value // 2 # 剩下的字符串如果超过26个字母，则每多一个就需要一次操作 ans += max(0, n - ans - 26) return ans def getBinaryTrees(self , preOrder: List[int], inOrder: List[int]) -> List[TreeNode]: # write code here if not preOrder or not inOrder: return [None] ans = [] for i in range(len(inOrder)): if inOrder[i] == preOrder[0]: # 所有的左右子树组合得到所有可能的树 for left in self.getBinaryTrees(preOrder[1:i + 1], inOrder[:i]): for right in self.getBinaryTrees(preOrder[i + 1:], inOrder[i + 1:]): root = TreeNode(preOrder[0]) root.left = left root.right = right ans.append(root) return ans def getValueSum(self, tree: TreeNode) -> int: # 返回以node为根节点的新平衡数的最小权值和 def dfs(node): if not node: return 0 if not node.left and not node.right: self.ans += 1 self.ans %= mod return 1 left = dfs(node.left) right = dfs(node.right) # 如果不平衡，那么左右子树中权值较小的子树的权值需补充abs(left - right) # 每次总是假设该节点的权值为1，所以需加1 self.ans += abs(left - right) + 1 self.ans %= mod # 返回该节点的最小权值之和 return left + right + abs(left - right) + 1 mod = int(1e9 + 7) self.ans = 0 dfs(tree) return self.ans
