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

目录

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

引入

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

例如我们要求 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;
    }
}

以上就是Java数据结构之快速幂的实现的详细内容，更多关于Java快速幂的资料请关注我们其它相关文章！