Java数据结构之快速幂的实现

Java数据结构之快速幂的实现

目录引入具体方法代码实现题目矩阵快速幂斐波那契数列第 N 个泰波那契数统计元音字母序列的数目

引入

快速幂是用来解决求幂运算的高效方式。

例如我们要求 x 的 90 次方，一般的方法可以通过一个循环，每次乘一个 x，循环 90 次之后就可以得到答案，时间复杂度为 O(n)，效率较低。而通过快速幂，我们可以在 O(log(n)) 的时间复杂度内完成该运算。

具体方法

我们可以通过二进制的视角来看待幂运算。

要计算的是 xn，把 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 rQsJkFVbZses;

}

}

矩阵快速幂

斐波那契数列

解：找到一种递推关系，满足矩阵乘法。

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快速幂的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。