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)題目內(nèi)容如下

實現(xiàn) pow(x, n) ，即計算 x 的 n 次冪函數(shù)（即，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

實現(xiàn)代碼

class Solution {
    public double myPow(double x, int n) {
        long exp = n;              // 特殊處理：補碼表示的負數(shù)最小值的相反數(shù)超過 Integer 表示范圍，故提高數(shù)據(jù)表示范圍
        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;
    }
}

矩陣快速冪

斐波那契數(shù)列

解：找到一種遞推關(guān)系，滿足矩陣乘法。

f(n) = f(n - 1) + f(n - 2)，將其依賴的狀態(tài)存成列向量

目標(biāo)值 f(n) 所在矩陣為：

下面關(guān)鍵就是找到這兩個矩陣直接滿足的一個關(guān)系，知道系數(shù)矩陣 mat

則令

我們就成功找到了系數(shù)矩陣。

下面可以求得遞推關(guān)系式：

對于 mat 可以通過快速冪求得結(jié)果。

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) {
        // 矩陣乘法，新矩陣的行數(shù) = a的行數(shù)rowa，列數(shù) = b的列數(shù)colb
        // a矩陣的列數(shù) = b矩陣的行數(shù) = 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 個泰波那契數(shù)

解：

對于 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;
    }
}

統(tǒng)計元音字母序列的數(shù)目

提示：1 <= n <= 2 * 10^4

解：題目中給定的字符的下一個字符的規(guī)則如下：

字符串中的每個字符都應(yīng)當(dāng)是小寫元音字母（‘a’,‘e’,‘i’,‘o’,‘u’）；

每個元音 ‘a’ 后面都只能跟著 ‘e’；
每個元音 ‘e’ 后面只能跟著 ‘a’ 或者是 ‘a’；
每個元音 ‘i’ 后面不能再跟著另一個 ‘i’；
每個元音 ‘o’ 后面只能跟著 ‘i’ 或者是 ‘u’；
每個元音 ‘u’ 后面只能跟著 ‘a’；

以上等價于每個字符的前一個字符的規(guī)則如下：

元音字母 ‘a’ 前面只能跟著 ‘e’,‘i’,‘u’；
元音字母 ‘e’ 前面只能跟著 ‘a’,‘i’；
每個元音 ‘i’ 前面只能跟著 ‘e’,‘o’；
每個元音 ‘o’ 前面只能跟著 ‘i’；
每個元音 ‘u’ 前面只能跟著 ‘o’,‘i’；

我們設(shè) f[i][j] 代表當(dāng)前長度為 i 且以字符 j 為結(jié)尾的字符串的數(shù)目，其中在此 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數(shù)據(jù)結(jié)構(gòu)之快速冪的實現(xiàn)的詳細內(nèi)容，更多關(guān)于Java快速冪的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: