腾讯音乐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.
#腾讯音乐娱乐笔试#