前言

题目难度中等偏上，比较灵活，所以需要大家仔细推导，特别第二题的数学公式。第三题要注意到300，所以可以用一些比较暴力一点的dp。

第一题

小红拿到了一个正整数n，她每次操作可以删除该正整数的一个数位。小红想知道自己最少操作多少次可以使得n是5的倍数?

注:删除所有数位后正整数会变成0，所以一定有解。

数据范围:1<=n<=10^9

示例1

输入

52

输出

1

说明

只需要操作1次，删除2即可

思路与代码

从后往前遍历读取到第一个可以被5整除的数即可。

public int fun (int n) {
    // write code here
    String s=String.valueOf(n);
    int res=0;
    int x=s.length()-1;
    while(x>=0){
        if((s.charAt(x)-'0')%5==0)
            break;
        else
            x=x-1;
        res++;
    }
    return res;
}

第二题

小红拿到了n个二叉树，她准备把这些二又树拼接起来。

拼接的方式是:选择一个二叉树a的一个叶子，将二叉树b的根作为该叶子的左儿子或者右儿子。这样就把a和b拼接起来了。

小红希望最终将这n个二叉树拼接成一个二叉树，需要满足最终二又树的高度尽可能大。小红想知道，有多少种不同的拼接方式?由于答案可能过大，请对10^9+7取模。

数据范围:

所有二叉树的节点数量之和不超过200000。

每个二叉树至少有一个节点

每个节点的权值随机。

1<=n<=200000

示例1

输入

[{1,#,2},{3.4.5}]

输出

6

说明

将第二个二叉树接到第一个的权值为2的叶子上面，共有2种方式。

将第一个二叉树接到第二个的权值为4的叶子或者权值为5的叶子上面，共有4种方式。

思路与代码

显然应该把根节点接在另外一棵树最深的节点上。

假设一棵树有x个这样的节点，另一颗有y个。

那么把第二棵树接在第一棵树的下面有2* x种方案。现在有n棵树，第i棵树有ai个这样的节点。考虑第一棵树在最底下的情形，此时剩下的n-1棵树的上下排列共有n-1 ！种，对于任意一种上下排列，通过改变每棵树的根节点对接的叶结点，共有（2* a2）* （2* a3）*...* (2* an)种。令total = 2* a1* 2* a2* ... * 2* an。 ans = total * （n-1）！（1/（2 a1）+...+ 1/(2* an))

private int findML(TreeNode tree) {
    if (tree == null) return 0;
    if (tree.left == null && tree.right == null) {
        return 1;
    }
    return Math.max(findML(tree.left),
            findML(tree.right)) + 1;
}
public int findMN(TreeNode tree, int maxLength, int length) {
    if (tree == null) return 0;
    if (tree.left == null && tree.right == null && length == maxLength) {
        return 1;
    }
    return findMN(tree.left, maxLength, length + 1) + findMN(tree.right,
            maxLength, length + 1);
}
int mod = 1000000007;
public long call(long c){
    long res=1;
    int modj=mod-2;
    while(modj>0){
        if((modj&1)>0)res=res*c%mod;
        c=c*c%mod;
        modj>>=1;
    }
    return res;
}
public int cntOfMethods (TreeNode[] trees) {
    int[] nums=new int[trees.length];
    for (int i = 0; i < trees.length; i++) {
        int x = findMN(trees[i], findML(trees[i]), 1);
        nums[i]=x;
    }
    long sum=1,res=0;;
    for(int i=1;i<trees.length;i++){
        sum=sum*i%mod;
    }
    for(int i=0;i<trees.length;i++){
        sum=sum*2*nums[i]%mod;
    }
    for(int i=0;i<trees.length;i++){
        res=(res+sum*call(2*nums[i])%mod)%mod;
    }
    return (int) res;
}

第三题

小红拿到了一个空字符串s。她有以下两种操作:

1.将任意一个字母添加在s的末尾。

2.选择s的一个长度不小于2的连续子串，复制下来添加到s的末尾

小红希望用空串s生成一个给定的字符串t，她想知道有多少种不同的生成方式？由于答案可能过大，请对10^9+ 7取模。

数据范围:

字符串t仅包含小写字母，且长度不超过300.

示例1

输入

"ababa"

输出

3

思路与代码

暴力枚举

Dp[i]表示凑成t的长度i的前缀的方案数。

一种方案是直接添加一个任意字符；

另外的方案就是通过复制一个子串， 暴力枚举子串长度为j，  判断（0，i-j-1）这个子串里面有没有（i-j，i）这个子串, 如果有dp i 加上 dp （i-j）, 这个判断用了第三层循环来判断.

public int cntOfMethod (String t) {
    // write code here
    int[] dp=new int[t.length()+1];
    int mod=1000000007;
    dp[1]=1;
    dp[2]=1;
    for(int i=3;i<=t.length();i++){
        dp[i]=(dp[i]+dp[i-1])%mod;
        for(int j=2;j<=i/2;j++){
            for(int k=1;k+j-1<=i-j;k++){
                if(t.substring(k-1,k+j-1).equals(t.substring(i-j,i)))
                    dp[i]=(dp[i-j]+dp[i])%mod;
            }
        }
    }
    return dp[t.length()];
}