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

来源：jb51　　时间：2022/3/29 11:46:41　　对本文有异议

引入

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

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

具体方法

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

要计算的是 xⁿ，把 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;
    }
}