一.前言

又是在力扣被题折磨的一次，反反复复地提交，反反复复的不通过，不过还好了解到了快速幂的思想，这种方式能大幅提高程序的运行速度。

题目：我们称一个数字字符串是 好数字 当它满足（下标从 0  开始）偶数 下标处的数字为 偶数   且 奇数   下标处的数字为 质数  （2，3，5  或  7）。

  • 比方说，”2582”  是好数字，因为偶数下标处的数字（2  和  8）是偶数且奇数下标处的数字（5 和  2）为质数。但  “3245”  不是 好数字，因为  3  在偶数下标处但不是偶数。
    给你一个整数  n ，请你返回长度为  n  且为好数字的数字字符串   总数  。由于答案可能会很大，请你将它对  109 + 7  取余后返回  。

一个 数字字符串   是每一位都由  0  到 9  组成的字符串，且可能包含前导 0.(题目来源：LeetCode）

二.分析

这道题乍一看似乎挺简单，由于是让我们返回好数字的个数，对于偶数下标来说符合条件的无非就 0,2,4,6,8 这几个数字，而奇数下标只有 1,3,5,7 这四个数字。我们只需要计算每一位上符合条件的数字的个数之积，顶多再模上 1000000007 就是最终答案了。但是真的是这样的吗？

  • 敲完代码直接提交（自信加蔑视）
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int countGoodNumbers(long n) {
        double result = 0;
        if (n % 2 == 0){
            result = (Math.pow(4,n/2) * Math.pow(5,n/2)) % 1000000007;
        }else {
            result = (Math.pow(4,n/2) * Math.pow(5,n/2 + 1)) % 1000000007;
        }
        return (int) result;
    }
}

心想这不就完了吗，很难吗？但是最终结果就是它死活不让我过，卡在了 50：
迷茫啊...
我***，这哪有什么问题，这都不让过？离谱啊…… 思考一番无果我只能去翻翻源码，这一下又让我有了新的收获：

它是一个本地方法，也就是由 c/c++编写的方法，java 能拿来用，而这个 pow 方法返回四舍五入到最接近的 int 值的参数值，而 int 最多只能表示 2147483647（2 的 31 次方-1），但是代码里面的 5 的 50 次方早就超过了其最大值，因此这里已经溢出，错误也就随之产生了。

行，那我就换个方法，不用这个 pow 方法，我自己写一个能得到指数值的方法不就好了吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 说明：这里举个例子，想简单告诉一下大家这种循环计算时会非常耗时间
 */


public class Test {
    public static long normalCal(int power, int base) {
        long result = 1;
        for (int i = 0; i < power; i++) {
            result = result * base;
        }
        return result;
    }

    public static void main(String[] args) {
        long result = normalCal(30,5 );

        System.out.println(result);
    }
}

这里我们求的是 5 的 30 次方，那么就会执行 30 次循环。不难发现其时间复杂度为 O(N),其中 N 为指数。在我们这段代码中还好，要是我换成 5 的 100 次方呢？那么会有以下两个问题：

  • 1.假如真的是 5 的 200 次方，即使我们用 long 接收，结果也会溢出的，这又会回到前面的问题上去。
  • 2.就算我们想尽办法正确得到了这个结果，但这会花费大量的时间，这样提交上去肯定会超时，最终也会不成功。
    那么是否有一种二者问题都解决掉的方案呢？答案肯定是有的，这就是之前我们将要说到的快速幂思想。

三.快速幂思想

我们先来初步认识下快速幂，给定一个 2 的 12 次方式子让你计算，你拿到这个题后会怎么想呢？

  • 为了计算的简便，我们通常可以将 2 的 12 次方转换为 4 的 6 次方进而转成 16 的 4 次方…进行计算。

1.快速幂正好是这种思想，在计算机中 2 的 12 次方要循环 12 次，而我们通过将指数减半，底数平方的思想可以减少循环的次数，从而提高性能。就比如上述的 2 的 12 次方：我们通过快速幂的思想思考它是这样的：2 的 12 次方 -> 4 的 6 次方 -> 16 的 3 次方 -> 256 的 1 次方 乘以 16。前者循环了 12 次，而后者只需要循环 4 次，要是有更高指数计算，则能节省循环的次数也就不言而喻了。

那我们怎么解决因为计算出的值过大而溢出导致出错的问题呢？我们先来了解一下模的运算规律吧：
a). (a+b)%p=(a%p+b%p)%p
b). (a-b)%p=(a%p-b%p)%p
c). (a*b)%p=(a%p * b%p)%p 2.在这里只需要用到第三条结论，我们可以在计算过程中就开始不断取模，而不是等到最终结果出来之后再模运算，这样就能避免最终答案太大导致出错的问题了。

因此在进行幂运算时我们可以这样做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public long myAns(lon base, long index) {
    int k = 1000000007;
    long result = 1;
    while (index > 0) {//当指数减到1时跳出循环
        if (index % 2 == 1) {
            //奇数往这儿走，由于这里是奇数，指数减半会有余数，因此我们只需多乘以一个原来的result就行了
            index = index - 1;
            result = result * base % k;//乘上原来的底数
            base = base * base % k;//底数平方
        }else {
            //偶数来这里，这里就是正常的指数减半，底数平方
            index = index / 2;
            base = (base * base) % k;
        }
    //我们可以看到这种方式节约的循环次数是指数级的
    return result;
}

其实上面这个代码还能更精简一些，我们还能对它进行优化。
我们来看看整道题的全部代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    //优化后的代码，这个方法就是进行幂运算
    public long findMyResult(long base, long index) {
        long result = 1;
        while(index> 0){
            if(power % 2 == 1){
                result = result * base % 1000000007;
            }
            index = index / 2;//奇数除以2会舍去小数点后面的数，能自动实现减1操作
            base = base * base % 1000000007;
        }
        return result;
    }


    public int countGoodNumbers(long n) {
        if(n % 2 == 0){
            long result =  findMyResult(4,n/2) % 1000000007;
            result = (result * findMyResult(5,n/2)) % 1000000007;
            return (int) result;
        }else{
            long result = (findMyResult(4,n/2) % 1000000007);
            result = (result * findMyResult(5,n/2 + 1)) %  1000000007;
            return (int) result;
        }
    }
}

完 ~