腾讯音乐秋招笔试编程三道题（2021-08-26）

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

文章目录

• 第一道：修建二叉树（100%）
• • 题目描述
  • 参考代码：
• 第二道： 尽可能大的数（100%）
• • 题目描述
  • 参考代码
• 第三道：方案数量（100%）
• • 题目描述
  • 参考代码

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

题目描述

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

参考代码：

public TreeNode pruneLeaves (TreeNode root) {// write code hereif (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

函数传入一个下标从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 heredp = 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】关注更多新鲜好文和互联网大厂的笔经面经。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！