引入
快速幂是用来解决求幂运算的高效方式。
例如我们要求x的90次方，一般的方法可以通过一个循环，每次乘一个x，循环90次之后就可以得到答案，时间复杂度为O(n)，效率较低。而通过快速幂，我们可以在O(log(n))的时间复杂度内完成该运算。
具体方法
我们可以通过二进制的视角来看待幂运算。
要计算的是x n ，把n以二进制的形式展开。
所以，只需要使用一个循环求n的二进制的每一位，每次一循环中，如果该二进制位为0，则不需要乘；如果该二进制位为1，则需要乘x。且每一次循环中都执行x *= x，可以一次获取x的不同幂次。
代码实现
public static double getPower(double x, int n) {
if(x == 0) return 0;
if(n < 0) { // x^(-a) = (1/x)^a
x = 1/x;
n = -n;
}
double res = 1.0;
while(n > 0) {
if((n & 1) == 1) {
res *= x;
}
x *= x;
n >>= 1;
}
return res;
}
题目
Pow(x, n)题目内容如下
实现pow(x, n)，即计算 x 的 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
实现代码
class Solution {
public double myPow(double x, int n) {
long exp = n; // 特殊处理：补码表示的负数最小值的相反数超过 Integer 表示范围，故提高数据表示范围
if(x == 0.0) return 0.0;
if(n < 0) {
x = 1/x;
exp = -exp;
}
double res = 1.0;
while(exp > 0) {
if((exp & 1) == 1) res *= x;
x *= x;
exp >>= 1;
}
return res;
}
}
矩阵快速幂
斐波那契数列
解：找到一种递推关系，满足矩阵乘法。
f(n) = f(n - 1) + f(n - 2)，将其依赖的状态存成列向量
目标值 f(n) 所在矩阵为：
下面关键就是找到这两个矩阵直接满足的一个关系，知道系数矩阵mat
则令
我们就成功找到了系数矩阵。
下面可以求得递推关系式：
对于mat可以通过快速幂求得结果。
class Solution {
int mod = (int)1e9+7;
public int fib(int n) {
if(n <= 1) return n;
long[][] mat = new long[][]{
{1, 1},
{1, 0}
};
long[][] ans = new long[][]{
{1},
{0}
};
int count = n - 1;
while(count > 0) {
if((count & 1) == 1) ans = mul(mat, ans); // 注意矩阵乘法顺序，不满足交换律
mat = mul(mat, mat);
count >>= 1;
}
return (int)(ans[0][0] % mod);
}
public long[][] mul(long[][] a, long[][] b) {
// 矩阵乘法，新矩阵的行数 = a的行数rowa，列数 = b的列数colb
// a矩阵的列数 = b矩阵的行数 = common
int rowa = a.length, colb = b[0].length, common = b.length;
long[][] ans = new long[rowa][colb];
for (int i = 0; i < rowa; i++) {
for (int j = 0; j < colb; j++) {
for (int k = 0; k < common; k++) {
ans[i][j] += a[i][k] * b[k][j];
ans[i][j] %= mod;
}
}
}
return ans;
}
}
第 N 个泰波那契数
解：
对于mat的幂运算可以使用快速幂
class Solution {
public int tribonacci(int n) {
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int[][] mat = new int[][]{
{1, 1, 1},
{1, 0, 0},
{0, 1, 0}
};
int[][] ans = new int[][]{
{1},
{1},
{0}
};
int count = n - 2;
while(count > 0) {
if((count & 1) == 1) ans = mul(mat, ans);
mat = mul(mat, mat);
count >>= 1;
}
return ans[0][0];
}
public int[][] mul(int[][] a, int[][] b) {
int rowa = a.length;
int colb = b[0].length;
int common = b.length;
int[][] ans = new int[rowa][colb];
for(int i = 0; i < rowa; i++) {
for(int j = 0; j < colb; j++) {
for(int k = 0; k < common; k++) {
ans[i][j] += a[i][k] * b[k][j];
}
}
}
return ans;
}
}
统计元音字母序列的数目
提示：1 <= n <= 2 * 10^4
解：题目中给定的字符的下一个字符的规则如下：
字符串中的每个字符都应当是小写元音字母 （‘a’,‘e’,‘i’,‘o’,‘u’）；
每个元音 ‘a’ 后面都只能跟着 ‘e’； 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘a’； 每个元音 ‘i’ 后面不能再跟着另一个 ‘i’； 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’； 每个元音 ‘u’ 后面只能跟着 ‘a’；以上等价于每个字符的前一个字符的规则如下：
元音字母 ‘a’ 前面只能跟着 ‘e’,‘i’,‘u’； 元音字母 ‘e’ 前面只能跟着 ‘a’,‘i’； 每个元音 ‘i’ 前面只能跟着 ‘e’,‘o’； 每个元音 ‘o’ 前面只能跟着 ‘i’； 每个元音 ‘u’ 前面只能跟着 ‘o’,‘i’；我们设 f[i][j] 代表当前长度为 i 且以字符 j 为结尾的字符串的数目，其中在此 j=0,1,2,3,4 分别代表元音字母 ‘a’,‘e’,‘i’,‘o’,‘u’
class Solution {
long mod = 1_000_000_007;
public int countVowelPermutation(int n) {
long[][] mat =
{
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 0}
};
long[][] ans = {
{1},{1},{1},{1},{1}
};
int count = n - 1;
while(count > 0) {
if((count & 1) == 1) ans = mul(mat, ans);
mat = mul(mat, mat);
count >>= 1;
}
long res = 0;
for(int i = 0; i < 5; i++) {
res += ans[i][0];
}
return (int)(res % mod);
}
public long[][] mul(long[][] a, long[][] b) {
int rowa = a.length;
int colb = b[0].length;
int common = b.length;
long[][] ans = new long[rowa][colb];
for(int i = 0; i < rowa; i++) {
for(int j = 0; j < colb; j++) {
for(int k = 0; k < common; k++) {
ans[i][j] += a[i][k] * b[k][j];
ans[i][j] %= mod;
}
}
}
return ans;
}
}
以上就是Java数据结构之快速幂的实现的详细内容，更多关于Java快速幂的资料请关注其它相关文章！
原文链接：https://HdhCmsTestcnblogs测试数据/gonghr/p/15815126.html