9.8 腾讯音乐笔试

第一题：在字符串中每次删除两个相同的字母可以增加一个任意字母，问最少多少次操作可以使得整个字符串的所有字母都只出现一次

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回满足题意的最小操作数
     * @param str string字符串 给定字符串
     * @return int整型
     */
    public int minOperations (String str) {
        // write code here
        int[] cnt = new int[26];
        int n = str.length();
        for(int i=0;i<n;++i){
            int x = str.charAt(i) - 'a';
            cnt[x]++;
        }
        int ans = 0;
        for(;;){
            int tot1 = 0;
            int tot2 = 0;
            for(int i=0;i<26;++i){
                tot1 += cnt[i] / 2;
                cnt[i] %= 2;
                tot2 += cnt[i];
            }
            ans += tot1;
            if(tot1 + tot2 <= 26) break;
            tot1 -= 26 - tot2;
            for(int i=0;i<26;++i){
                if(cnt[i] == 0) cnt[i] = 1;
            }
            while(true){
                boolean flag = true;
                for(int i=0;i<26;++i){
                    if(tot1 > 0) {
                        cnt[i]++;
                        tot1--;
                    }else {
                        flag = false;
                        break;
                    }
                }
                if(!flag) break;
            }
        }
        return ans;
        
    }
}

第二题：根据给定的先序和中序能构造出的所有二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型ArrayList 
     * @param inOrder int整型ArrayList 
     * @return TreeNode类ArrayList
     */
    ArrayList<TreeNode> ans = new ArrayList<>();
    int n;
    
    ArrayList<TreeNode> dfs(ArrayList<Integer>pre,int l1,int r1,ArrayList<Integer>in,int l2,int r2){
        if(l1 > r1 || l2 > r2) return null;
        int rt = pre.get(l1);
        ArrayList<TreeNode> res = new ArrayList<>();
        for(int i=l2;i<=r2;++i){
            if(rt == in.get(i)){
                int lnum = i - l2;
                int rnum = r2 - i;
                ArrayList<TreeNode> list1 = dfs(pre,l1+1,l1+lnum,in,l2,i-1);
                ArrayList<TreeNode> list2 = dfs(pre,l1+lnum+1,r1,in,i+1,r2);
                if(list1 == null && list2 != null){
                    int n2 = list2.size();
                    for(int j=0;j<n2;++j){
                        TreeNode u = new TreeNode(rt);
                        u.right = list2.get(j);
                        res.add(u);
                    }
                }else if(list1 != null && list2 == null){
                    int n1 = list1.size();
                    for(int j=0;j<n1;++j){
                        TreeNode u = new TreeNode(rt);
                        u.left = list1.get(j);
                        res.add(u);
                    }
                }else if(list1 == null && list2 == null){
                    TreeNode u = new TreeNode(rt);
                    res.add(u);
                }else{
                    int n1 = list1.size();
                    int n2 = list2.size();
                    for(int k=0;k<n1;++k){
                        for(int j=0;j<n2;++j){
                            TreeNode u = new TreeNode(rt);
                            u.left = list1.get(k);
                            u.right = list2.get(j);
                            res.add(u);
                        }
                    }
                }
                
            }
        }
        return res;
    }
    
    public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> pre, ArrayList<Integer> in) {
        // write code here
        n = pre.size();
        ans = dfs(pre,0,n-1,in,0,n-1);
        return ans;
    }
}

第三题：二叉树的每个结点只有0个子结点或者2个子结点，要求给每个结点填入正整数，且左右子树的和相等，问整棵树最小的和是多少（答案要对1e9+7取模）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tree TreeNode类 
     * @return int整型
     */
    final long mod = (int)(1e9 + 7);
    
    long dfs(TreeNode u){
        if(u.left == null && u.right == null) return 0;
        long res = 0;
        long num1 = dfs(u.left);
        long num2 = dfs(u.right);
        res = 2L * (Math.max(num1,num2) + 1L);
        return res;
    }
    
    public int getTreeSum (TreeNode tree) {
        // write code here
        long ans = dfs(tree);
        ans++;
        ans %= mod;
        return (int)ans;
    }
}

#腾讯音乐2023秋招笔试心得体会#