腾讯音乐笔试4/13（Java版）

刚刚根据牛客两位大佬的思路，进行的复盘，现在进行写一下我的思路，以及学习到的知识，供大家参考。

先说一下自己当时写的过程，第一题暴力直接0%，第二题理解题目花了半个小时，最后还是只过了5%，最后一题打卡题。

/*
    小红定义一个数组为“好数组”,当且仅当该数组满足以下条件:
        1.数组仅由0.1,2三种元素组成。
        2.数组相邻的元素不相等。例如:[2.1,2,0.1]是好数组。
    小红定义一个数组的“陡峭值”为该数组相邻元素的差的绝对值之和。
        例如，[2,1.2,0,1]的陡峭值为|2-1|+|1-2|+|2-0|+|0-1|=5。
    小红想知道，长度为n的所有好数组的陡峭值之和是多少?由于答案过大，请对10^9＋7取模。
    数据范围:2<n<10^9
    示例：
        输入:2 输出:8
        说明:共有[0,1],[1,0],[0,2],[2,0],[1,2],[2,1]这六个好数组。陡模值之和为1+1+2+2+1+1=8。
*/
//思路：观察法(虽然很扯,确实是这样) 递推式: (n-1)*2^(n+1) {n>=2} 再通过快速幂求解(类型为 long)
//注意：int类型最大值约等于 5*10^9  注意base，power也要用 long类型
public class test01 {
    public static final int Mod = (int)Math.pow(10,9)+7;
    //base 底数,power 指数
    public long doGet(long base,long power){
        long result = 1;
        while (power > 0) {
            if (power % 2 == 0) {
                //如果指数为偶数
                power = power / 2;//把指数缩小为一半
                base = base * base % Mod;//底数变大成原来的平方
            } else {
                //如果指数为奇数
                power = power - 1;//把指数减去1，使其变成一个偶数
                result = result * base % Mod;//此时记得要把指数为奇数时分离出来的底数的一次方收集好
                power = power / 2;//此时指数为偶数，可以继续执行操作
                base = base * base % Mod;
            }
        }
        return result;
    }
    public int fun(int n){
        long res = doGet(2,n+1);
        return (int)((n-1)*res%Mod);
    }
    public static void main(String[] args) {
        test01 t = new test01();
        System.out.println(t.fun(1000000000));
    }
}
/*
    什么是快速幂： 快速幂就是用来解决快速 求大幂的解法 比如：2^1000000000000
    公式：(A*B)%C = (A%C*B%C)%C (加法和加法同样适用)
    关键点: 我们平常求幂都是通过 将A循环n次,这样效率太低,我们可以用二分的思想 如：3^10 = (3*3)^5
    例子 :  3^10 = (3*3)^5   5无法平分 将其拆分成 4+1  原式= (3*3)^4 * (3*3)
           原式=(9*9)^2 * 9 = (81*81) * 9 = 6561 * 9
           关键: 最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积
 */

/*
    大致意思：给你一棵树，树上有权值。让你把每一个结点子树的乘积末尾0的个数作为其价值
            然后将每一个结点最后权值改为价值
    如：[2,5,10,#,#,4,5] ->[3,0,2,#,#,0,0]
 */
//关键点：(1) 一个树的子树包括本身  (2) 统计子树中2和5的个数
/*
    详细思路：主要是 要将乘法运算转换成加法运算，因为10肯定是2*5得来的统计一共有多少个2和5
    然后通过后序遍历得到结果
 */
public class test02 {
    public TreeNode valueOfTree(TreeNode root) {
        dfs(root);
        return root;
    }
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0,0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int[] cur = cal(node.val);
        int n2 = cur[0] + l[0] + r[0];
        int n5 = cur[1] + l[1] + r[1];
        node.val = Math.min(n2, n5);
        return new int[]{n2,n5};
    }
    //末尾0的数量与因子2和5的数量关系
    private int[] cal(int num) {
        int n2 = 0, n5 = 0;
        while (num % 2 == 0) {
            num /= 2;
            n2 += 1;
        }
        while (num % 5 == 0) {
            num /= 5;
            n5 += 1;
        }
        return new int[]{n2,n5};
    }
}

总的来说，知道思路还是很简单的，很可惜当时没想出来。我太菜了。