記第一次筆試
今天筆者參加了某大廠的筆試，第一題大致題目是這樣的：
有一個整數(shù)n ( 1<=n<=1000000000)，最多有n個人組成隊列，并從中選取一位當(dāng)隊長，求共可以組成多少隊伍（其中隊長不同視為不同的隊伍比如( 1（隊長）, 2 )和(1,2（隊長）) ）表示不同的兩個隊伍。輸出最多有多少個隊伍對1000000007取模；
示例
輸入
2
輸出
4
分析隊伍數(shù)分別為
(1) (2) (1,2) (1,2)其中斜體表示隊長
我剛開始是這樣分析的
若n = 3 時，隊伍數(shù)就是
（1）（2）（3）（12）（12）（13）（13）（23）（23）（123）（123）（123）
于是我得出了一個結(jié)論：
三個選一個隊長的選擇只有一種
三個選兩個隊長的選擇有兩種
三個選三個隊長的選擇有三種
總數(shù)也就是 = 三個選一個 * 1 + 三個選兩個 * 2 + 三個選三個 * 3
也就是
那么得出通項公式
問題就變成了求
因為
接下來我開始研究階乘，最后終于把代碼寫好了，開開心心的填上去一運行，通過了0%的測試用例，我打開了IDEA進行調(diào)試發(fā)現(xiàn)當(dāng)你= 100 是 拋出了 by/zero 的異常，原來當(dāng)n很大時整數(shù)溢出最后導(dǎo)致階乘結(jié)果為0，我將int改成了long，BigDecimal 還是存在問題，后來我轉(zhuǎn)換思路看看能不能舉例找出通項
n = 1 result = 1
n = 2 result = 4
n = 3 result = 12
n = 4 result = 32
n = 5 result = 80
...
果不其然我找到了規(guī)律
這樣問題轉(zhuǎn)換成了求2^(n-1)，我想起了位運算求2的冪次方，經(jīng)過了一頓操作之后，我提交上去還是提示通過了0%的示例，同樣當(dāng)n足夠大時還是溢出了。。。。不一會時間到了，我還沒有來的及看第二題就結(jié)束了。
交卷之后我看了牛客網(wǎng)的帖子，有大牛說用快速冪就出來了，我去百度了一下什么是快速冪
https://blog.csdn.net/qq_40693171/article/details/84196079
首先要知道 （a * b）%c=（a%c）（b%c）*
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO 自動生成的方法存根
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
long b = sc.nextLong();
long c = 1000000007;
long a = 2;
long res = 1;
a %= c;
for (; b != 0; b /= 2) {
if (b % 2 == 1)
res = (res * a) % c;
a = (a * a) % c;
}
System.out.println(res);
}
}
}
后來我套了模板
import java.util.Scanner;
public class Alibaba {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
System.out.println(fun2(x));
}
final static int M=1000000007;
private static long fun1(int n){
if(n==0) return 1;
if(n==1) return 2;
long ans=1;
long base=2;
while(n!=0){
if((n&1)==1) ans=((ans%M)*(base%M))%M;
base=((base%M)*(base%M))%M;
n>>=1;
}
return ans%M;
}
//n*2^(n-1) % 1000000007
private static int fun2(int n){
return (int) (((n%M)*(fun1(n-1)%M))%M);
}
}
調(diào)試未發(fā)現(xiàn)問題
通過這次筆試真的發(fā)現(xiàn)了自己與其他人差距甚大
coding everyday,everyday coding
