记第一次笔试
今天笔者参加了某大厂的笔试，第一题大致题目是这样的：
有一个整数n ( 1<=n<=1000000000)，最多有n个人组成队列，并从中选取一位当队长，求共可以组成多少队伍（其中队长不同视为不同的队伍比如( 1（队长）, 2 )和(1,2（队长）) ）表示不同的两个队伍。输出最多有多少个队伍对1000000007取模；
示例
输入
2
输出
4
分析队伍数分别为
(1) (2) (1,2) (1,2)其中斜体表示队长
我刚开始是这样分析的
若n = 3 时，队伍数就是
（1）（2）（3）（12）（12）（13）（13）（23）（23）（123）（123）（123）
于是我得出了一个结论：
三个选一个队长的选择只有一种
三个选两个队长的选择有两种
三个选三个队长的选择有三种
总数也就是 = 三个选一个 * 1 + 三个选两个 * 2 + 三个选三个 * 3
也就是
那么得出通项公式
问题就变成了求
因为
接下来我开始研究阶乘，最后终于把代码写好了，开开心心的填上去一运行，通过了0%的测试用例，我打开了IDEA进行调试发现当你= 100 是 抛出了 by/zero 的异常，原来当n很大时整数溢出最后导致阶乘结果为0，我将int改成了long，BigDecimal 还是存在问题，后来我转换思路看看能不能举例找出通项
n = 1 result = 1
n = 2 result = 4
n = 3 result = 12
n = 4 result = 32
n = 5 result = 80
...
果不其然我找到了规律
这样问题转换成了求2^(n-1)，我想起了位运算求2的幂次方，经过了一顿操作之后，我提交上去还是提示通过了0%的示例，同样当n足够大时还是溢出了。。。。不一会时间到了，我还没有来的及看第二题就结束了。
交卷之后我看了牛客网的帖子，有大牛说用快速幂就出来了，我去百度了一下什么是快速幂
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);
}
}
调试未发现问题
通过这次笔试真的发现了自己与其他人差距甚大
coding everyday,everyday coding
