例如我們要求 x 的 90 次方，一般的方法可以通過一個(gè)循環(huán)，每次乘一個(gè) x，循環(huán) 90 次之后就可以得到答案，時(shí)間復(fù)雜度為 O(n)，效率較低。而通過快速冪，我們可以在 O(log(n)) 的時(shí)間復(fù)雜度內(nèi)完成該運(yùn)算。

具體方法

我們可以通過二進(jìn)制的視角來看待冪運(yùn)算。

要計(jì)算的是 xⁿ，把 n 以二進(jìn)制的形式展開。

所以，只需要使用一個(gè)循環(huán)求 n 的二進(jìn)制的每一位，每次一循環(huán)中，如果該二進(jìn)制位為 0，則不需要乘；如果該二進(jìn)制位為 1，則需要乘 x。且每一次循環(huán)中都執(zhí)行 x *= x，可以一次獲取 x 的不同冪次。

代碼實(shí)現(xiàn)

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)題目?jī)?nèi)容如下

實(shí)現(xiàn) pow(x, n) ，即計(jì)算 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

實(shí)現(xiàn)代碼

class Solution {
    public double myPow(double x, int n) {
        long exp = n;              // 特殊處理：補(bǔ)碼表示的負(fù)數(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)鍵就是找到這兩個(gè)矩陣直接滿足的一個(gè)關(guān)系，知道系數(shù)矩陣 mat

則令

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

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

對(duì)于 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 個(gè)泰波那契數(shù)

解：

對(duì)于 mat 的冪運(yùn)算可以使用快速冪

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)計(jì)元音字母序列的數(shù)目

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

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

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

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

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

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

我們?cè)O(shè) f[i][j] 代表當(dāng)前長(zhǎ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)之快速冪的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java快速冪的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: