Java資料結構之快速冪的實現

2022-03-29 13:04:33

引入

快速冪是用來解決求冪運算的高效方式。

例如我們要求 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快速冪的資料請關注it145.com其它相關文章！