一.媒介
又是在力扣被题折磨的一次，反反复复地提交，反反复复的不通过，不外还好了解到了快速幂的头脑，这种方式能大幅进步步伐的运行速率。
标题：我们称一个数字字符串是 好数字 当它满意（下标从 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就是最终答案了。但是真的是如许的吗？
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方法，我自己写一个能得到指数值的方法不就好了吗？
/** * 阐明：这里举个例子，想简朴告诉一下各人这种循环盘算时会非常耗时间 */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.在这里只需要用到第三条结论，我们可以在盘算过程中就开始不绝取模，而不是比及最闭幕果出来之后再模运算，如许就能克制最终答案太大导致堕落的题目了。
因此在举行幂运算时我们可以如许做：
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;}实在上面这个代码还能更精简一些，我们还能对它举行优化。
我们来看看整道题的全部代码：
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; } }}完 ~ |
