目錄

一.快速冪

1.問題的引入

2.快速冪的介紹

3.核心思想

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

?2.猴子碰撞的方法數(shù)

1.題目描述

2.問題分析

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

---

一.快速冪

1.問題的引入

問題:求解num的n次冪,結(jié)果需要求余+7

對(duì)于這個(gè)問題我們可能就是直接調(diào)用函數(shù)pow(a,b)來直接求解a的b次冪問題,但是如果求解的結(jié)果很大,超過的double的數(shù)值范圍,我們要求對(duì)最終的結(jié)果求余+7,我們?nèi)绻苯诱{(diào)用pow()函數(shù)的話,求解出來的數(shù)已經(jīng)超出了double的最大范圍,根本無法求出,這個(gè)時(shí)候我們是否可以考慮在求解的過程中每一次的結(jié)果都求余+7,而不是只在最終的結(jié)果求余+7這樣最終的結(jié)果肯定是小于+7,一定不會(huì)超出最大的范圍.

2.快速冪的介紹

快速冪:快速冪就是快速算底數(shù)的n次冪。其時(shí)間復(fù)雜度為 O(log?N),與樸素的O(N)相比效率有了極大的提高。

3.核心思想

例如計(jì)算,10的二進(jìn)制為1010,相當(dāng)于求解次方

=3*3*3*3*3*3*3*3*3*3

=(3*3)*(3*3*3*3*3*3*3*3)

=*

相當(dāng)于我們每次對(duì)10的二進(jìn)制的每一個(gè)位置求權(quán)(如果是二進(jìn)制這個(gè)位是1),則乘以當(dāng)前的疊加的數(shù),

例如進(jìn)行求余的步驟 :

定義變量ans保存的結(jié)果?? 1010位10的二進(jìn)制表達(dá)方式

1010的第一位為0,這個(gè)時(shí)候num=num*num=;??? 二進(jìn)制形式為:

1010的第二位為0,這個(gè)時(shí)候求權(quán)為1,ans=ans*num=? num=num*num=;二進(jìn)制形式為:

1010的第三位為0,這個(gè)時(shí)候num=num*num=; 二進(jìn)制形式為:

1010的第四位為1,這個(gè)時(shí)候求權(quán)為1,ans=ans*num=*? num=num*num=;

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

1.求余+7的版本,返回?cái)?shù)據(jù)類型為int的結(jié)果

    public int quickPow(long num,int n){long ans=1;long mod=1000000007;while(n!=0){if((n&1)==1)ans=(ans*num)%mod;num = num * num % mod;n>>=1;}return (int)(ans%mod);}

?2.不求余的版本,返回?cái)?shù)據(jù)類型為long的結(jié)果

    public long quickPow(long num,int n){long ans=1;while(n!=0){if((n&1)==1)ans=ans*num;num = num * num;n>>=1;}return ans;}

?2.猴子碰撞的方法數(shù)

1.題目描述

現(xiàn)在有一個(gè)正凸多邊形，其上共有 n 個(gè)頂點(diǎn)。頂點(diǎn)按順時(shí)針方向從 0 到 n - 1 依次編號(hào)。每個(gè)頂點(diǎn)上 正好有一只猴子 。下圖中是一個(gè) 6 個(gè)頂點(diǎn)的凸多邊形。

?

每個(gè)猴子同時(shí)移動(dòng)到相鄰的頂點(diǎn)。頂點(diǎn) i 的相鄰頂點(diǎn)可以是：

• 順時(shí)針方向的頂點(diǎn) (i + 1) % n ，或
• 逆時(shí)針方向的頂點(diǎn) (i - 1 + n) % n 。

如果移動(dòng)后至少有兩個(gè)猴子位于同一頂點(diǎn)，則會(huì)發(fā)生 碰撞 。

返回猴子至少發(fā)生 一次碰撞 的移動(dòng)方法數(shù)。由于答案可能非常大，請(qǐng)返回對(duì) 109+7 取余后的結(jié)果。

注意，每只猴子只能移動(dòng)一次。

力扣: 力扣

2.問題分析

正難則反,題目問的是至少發(fā)生一次碰撞的移動(dòng)次數(shù),我們不妨把問題轉(zhuǎn)換為求解猴子一次都不碰撞的次數(shù),猴子一共有2的n次冪中跳躍的方式,求中有兩種是一次都不碰撞的,一種是猴子全部順時(shí)針進(jìn)行跳躍,一種是猴子逆時(shí)針進(jìn)行跳躍,所以猴子至少發(fā)生一次碰撞的次數(shù)=猴子總共的移動(dòng)次數(shù)-2

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

    public int monkeyMove(int n) {long ans=1,a=2;long mod=1000000007;while(n!=0){if((n&1)==1)ans=(ans*a)%mod;a = a * a % mod;n>>=1;}return (int)((ans+mod-2)%mod);}

?

?