Java數(shù)據(jù)結(jié)構(gòu)之快速冪的實(shí)現(xiàn)
引入
快速冪是用來解決求冪運(yùn)算的高效方式。
例如我們要求 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ì)算的是 xn，把 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)文章！
相關(guān)文章
這篇文章主要介紹了java多線程編程實(shí)例，分享了幾則多線程的實(shí)例代碼，具有一定參考價(jià)值，加深多線程編程的理解還是很有幫助的，需要的朋友可以參考下2021-07-07
Mysql存儲(chǔ)java對(duì)象實(shí)例詳解
這篇文章主要介紹了Mysql存儲(chǔ)java對(duì)象實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2016-11-11
Kafka 網(wǎng)絡(luò)中斷和網(wǎng)絡(luò)分區(qū)4種場(chǎng)景分析
這篇文章主要介紹了Kafka 網(wǎng)絡(luò)中斷和網(wǎng)絡(luò)分區(qū)4種場(chǎng)景分析2007-02-02
這篇文章主要介紹了分享JVM 的四種引用方式，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-07-07
這篇文章主要為大家詳細(xì)介紹了Java中Get和Post用法的相關(guān)資料，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Java有一定的幫助，需要的可以參考一下2022-11-11
這篇文章主要介紹了Java annotation元注解原理實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
這篇文章主要給大家介紹了關(guān)于Java如何使用Calendar類獲取某一日期的前N天,我們可以使用Java中的Calendar類來獲取前n天的時(shí)間,文中給出了詳細(xì)的代碼示例,需要的朋友可以參考下2023-08-08
SpringAOP+RabbitMQ+WebSocket實(shí)戰(zhàn)詳解
這篇文章主要介紹了SpringAOP+RabbitMQ+WebSocket實(shí)戰(zhàn)詳解，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-11-11
SpringBoot實(shí)現(xiàn)返回值數(shù)據(jù)脫敏的步驟詳解
這篇文章主要給大家介紹一下SpringBoot實(shí)現(xiàn)返回值數(shù)據(jù)脫敏的步驟，文章通過代碼示例介紹的非常詳細(xì)，具有一定的參考價(jià)值,需要的朋友可以參考下2023-07-07
利用logback filter過濾某個(gè)類 屏蔽某個(gè)類
這篇文章主要介紹了利用logback filter過濾某個(gè)類 屏蔽某個(gè)類的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07