9月8号腾讯音乐后端笔试

 class Solution {
    // 第一题

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 返回满足题意的最小操作数
     *
     * @param str string字符串 给定字符串
     * @return int整型
     */
    public int minOperations(String str) {
        // write code here
        char[] arr = str.toCharArray();
        int[] map = new int[128];
        int n = arr.length;
        int count = 26;
        for (int i = 0; i < n; i++) {
            if (map[arr[i] - 'a'] == 0) {
                count--;
            }
            map[arr[i] - 'a']++;
        }
        int res = 0;
        for (int i = 'a'; i <= 'z'; i++) {
            if (map[i - 'a'] >= 2) {
                while (count > 0 && map[i - 'a'] > 2) {
                    map[i - 'a'] -= 2;
                    count--;
                    res++;
                }
            }
        }

        if (count > 0) {
            for (int i = 0; i < 128; i++) {
                res += (map[i]) / 2;
            }
        } else {
            for (int i = 0; i < 128; i++) {
                if (map[i] != 0) {
                    res += map[i] - 1;
                }
            }
        }
        return res;
    }

    // 第二题

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param preOrder int整型ArrayList
     * @param inOrder  int整型ArrayList
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> getBinaryTrees(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
        // write code here
        return buildTree(preOrder, 0, preOrder.size() - 1,
                inOrder, 0, inOrder.size() - 1);

    }

    ArrayList<TreeNode> buildTree(ArrayList<Integer> preOrder, int preStart, int preEnd,
                                  ArrayList<Integer> inOrder, int inStart, int inEnd) {
        ArrayList<TreeNode> res = new ArrayList<>();
        if (preStart > preEnd || inStart > inEnd) {
            res.add(null);
            return res;
        }
        int rootVal = preOrder.get(preStart);
        ArrayList<Integer> indexs = new ArrayList<>();
        for (int i = inStart; i <= inEnd; i++) {
            if (inOrder.get(i) == rootVal) {
                indexs.add(i);
            }
        }
        for (Integer index : indexs) {
            ArrayList<TreeNode> lefts = buildTree(preOrder, preStart + 1, preStart + index - inStart,
                    inOrder, inStart, index - 1);
            ArrayList<TreeNode> rights = buildTree(preOrder, preStart + index - inStart + 1, preEnd,
                    inOrder, index + 1, inEnd);
            for (TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    TreeNode root = new TreeNode(rootVal);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }

    // 第三题

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param tree TreeNode类
     * @return int整型
     */
    public int getTreeSum(TreeNode tree) {
        // write code here
        return (int) (traverse(tree) % ((Math.pow(10, 9) + 7)));
    }

    long traverse(TreeNode root) {
        if (root == null) return 0;
        long leftVal = traverse(root.left);
        long rightVal = traverse(root.right);
        return 1 + Math.max(leftVal, rightVal) * 2;
    }
    
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}