腾讯音乐9.8笔试
1道问答题（10分）+3道编程题（3*30分）
问答题：设计一个直播间，完全不会
编程题：1+0+1
1.给定只包含小写字母的字符串，每次可以选择两个相同的字符进行消除，然后再末尾加上一个任意小写字母。问最少多少次操作可以使字符串内各字符都不同？
解法：贪心。肯定优先加上没出现的字符。如果都满了，那就都放在同一字符上消除。具体来说，先进行一遍消除，使得26个位置尽可能满。如果剩余字符超过26，对多余处进行消除。
2.给定 前序遍历数组，中序遍历数组。数组中可能存在重复元素，请给出所有可能二叉树。
考试的时候没写出来，下面是看到别人分享的代码。自己还是太菜了
public ArrayList<TreeNode> getBinaryTrees(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
int n = preOrder.size();
return createTree(preOrder, inOrder, 0, n - 1, 0, n - 1);
}
private ArrayList<TreeNode> createTree(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder, int pl, int ph, int il, int ih) {
if (pl > ph) {
return new ArrayList<>();
}
ArrayList<TreeNode> res = new ArrayList<>();
for (int i = il; i <= ih; i++) {
if (preOrder.get(pl).equals(inOrder.get(i))) {
int leftNum = i - il;
ArrayList<TreeNode> leftChildes = createTree(preOrder, inOrder, pl + 1, pl + leftNum, il, i- 1);
ArrayList<TreeNode> rightChildes = createTree(preOrder, inOrder, pl + leftNum + 1, ph, i + 1, ih);
for (TreeNode leftChild : leftChildes) {
for (TreeNode rightChild : rightChildes) {
TreeNode p = new TreeNode(preOrder.get(pl));
p.left = leftChild;
p.right = rightChild;
res.add(p);
}
}
}
}
return res;
} 3. 给定某二叉树，其节点要么没有子节点，要么就是两个子节点。给每个节点赋正整数的值，使得一个节点，它的左右两边节点和相等。求最小的节点总和。
解法：后序遍历，return Math.max(left, right) + 1。尽可能赋最小的1.
#腾讯音乐娱乐笔试#
速腾聚创二面26人在聊