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)^ax = 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矩阵的行数 = commonint 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’;
文章图片
文章图片
文章图片
文章图片
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数据结构之快速幂的实现的详细内容,更多关于Java快速幂的资料请关注脚本之家其它相关文章!
推荐阅读
- JavaScript字符串分割处理的方法总结
- Java超详细教你写一个学籍管理系统案例
- 数据结构|数据结构之并查集(含代码实现)
- web前端技术Mongoose详解
- 《深入理解Java虚拟机》第3版学习笔记,涵盖全书精华,请查收!
- java|如何写出让同事无法维护的代码()
- javascript|一个超级简单的浮动Select
- 高级前端工程之路|《代码规范》如何写出干净的代码(二)函数与方法
- Java基础|改善代码质量的编程规范
- java|云原生爱好者周刊(服务网格的困境与破局)