[数据结构与算法]腾讯音乐秋招笔试编程三道题（2021-08-26）

恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一道：修建二叉树（100%）

题目描述

牛牛有一棵有n个节点的二叉树，其根节点为root。牛牛想修剪掉当前二叉树的叶子节点，但是牛牛不能直接删除叶子节点。他只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉，牛牛想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。

参考代码：

public TreeNode pruneLeaves (TreeNode root) {
        // write code here
        if (condition(root)) return null;
        return curve(root);
    }

    private TreeNode curve(TreeNode root) {
        if(root == null) return null;
        if(condition(root.left))root.left = null;
        if(condition(root.right))root.right = null;
        pruneLeaves(root.left);
        pruneLeaves(root.right);
        return root;
    }

    private boolean condition(TreeNode root) {
        if (root == null) return true;
        if(root.left != null && root.left.left == null && root.left.right == null) return true;
        if(root.right != null && root.right.left == null && root.right.right == null) return true;
        return false;
    }
// 关注TechGuide！ 大厂笔经面经闪电速递！

第二道： 尽可能大的数（100%）

题目描述

牛牛有一个只由字符1’到’9’组成的长度为n的字符串s，现在牛牛可以截取其中一段长度为k的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123。

牛牛想让这个正整数尽可能的大，请你帮助牛牛计算该正整数。函数传入一个长度为n的字符串s和一个正整数k，请你返回答案。

输入：“321”，2
输出：32

参考代码

public static int maxValue (String s, int k) {
        int div=(int)Math.pow(10,k);
        int max=0;
        int cur=0;
        int right=0;
        while(right<k){
            cur=cur*10+s.charAt(right)-'0';
            right++;
        }
        max=cur;
        while(right<s.length()){
            cur=cur*10+s.charAt(right)-'0';
           //首先把第一个数去掉
            cur=cur%div;
            if(cur>max)
                max=cur;
            right++;
        }
        return max;
    }
// 关注TechGuide！ 大厂笔经面经闪电速递！

第三道：方案数量（100%）

题目描述

牛妹给了牛牛一个长度为n的下标从0开始的正整型数组a，粗心的牛牛不小心把其中的一些数字删除了。假如ai被删除了，则ai = 0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

a0 ≤ a1≤…≤an-1且对于所有的0≤i<n -1满足1≤ ai ≤k。

函数传入一个下标从0开始的数组a和一个正整数k，请返回合法的填充方案数对109＋7取模的值,保证不存在方案数为0的数据。

参考代码

public class TechGuide{
  public static void main(String[] args){
        Solution2 s = new Solution2();
        System.out.println(s.FillArray(new int[]{0,0,0,0,0,67,0,0},100));
    }
    int [][] dp;
    public int FillArray (int[] a, int k) {
        // write code here
        dp = new int[a.length+1][k+1];
        int left = 1;
        int right = 1;
        int len = 0;
        long ans = 1;
        for(int i=0;i<a.length;i++){
            if(a[i]==0){
                len++;
            }else{
                if(len!=0){
                    ans = ans*count(len,a[i]-left+1) %1000000007;
                }
                len = 0;
                left = a[i];
            }
        }
        if(len!=0){
            ans = ans*count(len,k-left+1) %1000000007;
        }
        return (int)ans;
    }
    public int count (int s,int p){
        if(dp[s][p] != 0) return dp[s][p];
        if(s==1) {
            dp[s][p] = p;
            return p;
        }
        if(p==1) {
            dp[s][p] = 1;
            return 1;
        }
        for(int k=1;k<=p;k++){
                dp[s][p] = (dp[s][p] + count(s-1,k)) %1000000007;
            }

        return dp[s][p];
    }
}
// 关注TechGuide！ 大厂笔经面经闪电速递！

恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。