零、写在前面
这是打卡的第十五天，其中最后一道题之前有写过，今天再次进行一个优化，主要知识点在
《算法零基础100讲》(第15讲) 二分快速幂
https://blog.csdn.net/WhereIsHeroFrom/article/details/121134510
一、主要知识点
1.二分快速幂
主要利用到的思想就是如下的样子，非常便于理解，
#define ll long long ll f(ll a, ll b, ll c) { if (b == 0) return 1 % c; //0次幂是1 ll v = f(a*a % c, b/2, c); //二分运算 if (b % 2) v = v * a % c; return v; }
2.二分快速幂的非递归实现(补充知识点)
其实使用递归肯定是可以的，但是，为了优化空间复杂度以及常数级别的时间复杂度，我们可以考虑这个非递归实现。这两个思想其实是一个从前往后，但是递归返回的时候是从1开始往回传值，最终得到结果的。为了方便理解，我换了一种方式大家看一下这个动画加深一下理解，希望大家可以熟练寻用。
int kuaisumi(int a, int k){ int ans = 1; a %= mod; while(k){ if(k&1) ans = (ans*a)%mod;//如果当前位为1 则乘a a = (a * a) % mod; //a变成之前的平方 k>>= 1; //k右移一位 } return ans; }
二、课后习题
50.Pow(x,n)
50. Pow(x, n)
https://leetcode-cn.com/problems/powx-n/
求一个数字的n次方，但是不能直接硬算，会超时。
主要思想
其实就是用之前的二分快速幂的非递归实现，只不过这里不需要取模，所以把取模干掉就好了。
但是，这题有个大坑，给的数字是int的边界，在转换成正数的时候会超出范围，所以，我们需要使用unsigned int进行变量的转换吸收。具体看代码把。
double myPow(double x, int n){ double y = 1; //保存结果 unsigned m; //接受n的转换结果 if(n < 0){ //如果n<0 就把x变成1/x n变 -n 统一运算 x = 1/x; m = -(unsigned int)n; } else m = n; while(m){ //非递归二分快速幂 if(m&1 == 1) y *= x; x *= x; m >>= 1; } return y; }
结果分析
还是可以的。
其实递归实现也可以 我放一个做参考
double f(double a,unsigned int n) { if (n == 0) return 1; double v = f(a*a , n/2); if (n % 2) v = v * a ; return v; } double myPow(double x, int n){ double y = 1; unsigned m; //if(x == 1) return y; if(n < 0){ x = 1/x; m = -(unsigned int)n; } else m = n; y = f(x,m); return y; }
372.超级次方
372. 超级次方
https://leetcode-cn.com/problems/super-pow/
主要思想
主要问题其实是出现在数据的及时取余，我们这里用的是下面的递推式，就很好做运算了。
int mod = 1337; int kuaisumi(int a, int k){//快速幂的实现 int ans = 1; a %= mod; while(k){ if(k&1) ans = (ans*a)%mod; a = (a * a) % mod; k>>= 1; } return ans; } int superPow(int a, int* b, int bSize){ if(!bSize) return 1;//如果没数据返回1 int ans ; ans = kuaisumi(a,b[bSize - 1])*kuaisumi(superPow(a,b,bSize - 1),10);//递归调用 return ans%mod; }
结果分析
凑合凑合。
1808.好因子的最大数目
1808. 好因子的最大数目
https://leetcode-cn.com/problems/maximize-number-of-nice-divisors/
这个已经做过了，题解在，说真的，这个不看血亏。你能感受到数学的魅力是多么的强大
[解题报告]《算法零基础100讲》(第10讲) 因子分解和枚举(下)_XingleiGao的博客-CSDN博客
零、写在前面这是打卡的第十天，由于今天的第二题有一定的难度，需要我花费比较大的篇幅做题解，这是第二篇，主要讲解第三题。我增加了一道题作为这道题的第一步辅助理解。上一篇在[解题报告]《算法零基础100讲》(第10讲) 因子分解和枚举(上)https://blog.csdn.net/qq_17593855/article/details/121052656一、预备知识⚠这部分不是特别难，只要你能理解，你就可以很容易的写这道题整数拆分给定一个正整数n，...
https://blog.csdn.net/qq_17593855/article/details/121053105
但是。今天做个优化，就是把它优化成非递归实现，代码如下：
int mod = 1000000007; long long kuaisumi(long long a, int k){ long long ans = 1; while(k){ if(k&1) ans = (ans * a) % mod; a = (a * a) % mod; k >>= 1; } return ans; } int maxNiceDivisors(int primeFactors){ if(primeFactors == 1) return 1; if(primeFactors % 3 == 0) return kuaisumi(3,primeFactors/3); else if(primeFactors % 3 == 1) return (kuaisumi(3,primeFactors / 3 - 1)*4)%mod; else return (kuaisumi(3,primeFactors/3)*2)%mod; }
就很完美0.0
三、今日总结
看到今天打卡人数骤减，不知道是太难了还是怎样，希望我的题解能给大家点思路，大家都要坚持下去呀
