彻底搞懂基础算法，技巧与经验【终极版】
大家好，我是程序员蛟龙哥，昨年蓝桥勉强混进省二，哭了，这次俺一定省一，淦。今天就来全面梳理蓝桥的技巧，以及我的一点点经验教训，希望能帮你考场上多拿几分。
著名律师查理芒格曾经说过避免失败是成功的捷径
如果ACM大佬略过，所以每个人的状态不同，不是上来就能拿国奖的，找准自己定位，打牢基础才是重点，重点是一定不要盲目刷题，做完之后要思考为啥考的是这个数据结构。这组好像是有相似的特点，就能多余抽去剩下结构进行复用，后面也会总结常见的模板供你使用，全程干货，记得收藏点个赞啥的。
送你一朵小红花，必将好运🎁连连～
🎨 一 技巧篇
1 结果填空题
首先判断能不能借助日历、计算器、WPS、txt文本、Notepad++或者数学方法等工具进行快速解出来，最后再选择用Eclipse代码暴力破解。有的填空题可能是没有思路，可以尝试一下手算，算这算这有思路了呢。
2 代码填空题
这种一般是递归、找规律等，实在想不出来可以随便试，可以猜常见的数字哈哈。先通过多组数据样本填空测试输出结果是什么，尤其是方法返回的结果很重要。如果经过多组数据测试答案输出结果都正确，这样会大大地减少了读题、解题过程的时间，那这答案也差不多了是吧。
题目一定要看清楚了，我的建议是你在画板上边画边思考，完了千万不要漏了判定条件，最后是用例多测上几组，来验证自己是对的，这里呢我姐的可以用枚举子集的思想然后判断是否满足题意，注意基础题不要丢分了。
3编程题
敲代码之前先把所有题目和分数都大致过一遍，先选简单的再选分数很高但很有把握的写，再选难点题目，不按题号依次递进。
比较难的题目可以先在文本里写伪代码，把思路画在画板上搞清楚了边码边调试往往比上来直接撸代码来得高效。
如果知道题意写代码题，要判断时间复杂度和空间复杂度要不要超时，没得把握先别写，免得浪费时间。
有大量相同的代码块，不要犹豫直接CV。蓝桥杯考试时间虽然不短，但是题量很大。因此，时间的合理分配显得非常重要。
蓝桥杯答题的分数看的是你测试数据的通过率，所有务必把能过的都码上去，这里的意思如果想不出完美的AC方案的话，也可以先解决一小部分的数据规模，如果你实在不会这题，先暴力嘛，祈求一点点测试样例，反正比看空起好啦。
给你举个例子
JavaB组第10题要算乘积最大，好像你乍一看没什么好的想法，然后做到最后一题一般也没多少时间了嘛，为了抢分啊，不妨可以就想的简单点。这个题目无非就是给你一堆数字，数字能有什么呢，正负零。直接考虑全正或者全负的情况，这两种简单情况的代码写起来并不复杂吧？后台的测试样例里面不可能都是复杂情况的，一般测试样例也是有梯度的，从简单到难，从普遍情况到极端情况，所以即使你只写了针对简单情况的，你也能拿部分分数。再比如模拟赛第7题风险度量，一看这题心想“完了，我还没学过并查集”，那怎么办呢？注意看题目，有一句话叫“如果询问的两点不连通则输出-1”，这句话隐含意义就是后台至少有一组测试样例是不连通的。那与其空着不写，不如你就写个程序输出-1，假如后台有5组测试样例，你也拿到了1/5的分到手了吧。
这个比赛系统在你提交了代码之后是看不到结果的，所以不会告诉你是WA了还是有没有超时。通常题目提供的测试样例只有一两组，为了进一步验证自己代码的正确性，可以自己再找几组测试样例测试一下。
有同学想知道大概什么时候出省赛结果，我印象里结果出的挺快的，考后两三周的样子。
参考建议
可能有小伙伴担心校区不同，这个影响不大，记得我当时自己刚开始才加比赛的时候，我个人认为竞赛这种事，他是一个层次面上的比赛，虽然有少数上一层次和下一层次的人混在里面，但是大部分人还是水平相当的，不然比赛咋整你说是不是？而且由于蓝桥杯的坑点，提交之后你不知道自己的代码对错，还不能带算法模板这类纸质材料进去，所以就算有的同学编程比较拿手，也没有绝对的优势，当然很优秀的除外。做过真题的小伙伴也看得出来蓝桥杯的题目难度是有在逐年增加的，而且编程题的比例也在增加，我前面说做好填空题就行，但是现在有个别填空题也不那么好做，可是编程题也不会让你一个都做不了啊，所以再次总结一下就是，做好填空题，编程题竟可能多的拿分。说到真题的变化，还有一点想提的是，个人感觉蓝桥杯涉及的算法也在变多，省赛重基础算法，国赛重高级算法，虽然基础算法和高级算法这两个范围非常的广，但是有意统计一下里面出现的具体算法和频率，也可以知道基本上考的就那么几个，但是近年来也逐渐多了一些没有考过，我是说多了一些，不要紧张，还是占少数的，这里提这一点的原因是想让学有余力并且想拿大奖的同学，后期刷题的时候可以拓宽刷题的算法。
如何复习
1、初学编程的同学是这样的：
看到题目我有一点思路，但是我写不出来，去网上搜了题解，看了都能理解，可是我还是写不出来，这个问题我自己的学弟学妹们也问过我很多次，我自己当年开始时也是这样的。因为刚起步嘛，你此时的编程能力还不足以让你一个人来完成一道题，那不如就大大方方的借鉴别人的呗。先把你能想到的代码写下来，无论多少都先写下来，然后再去参考别人的代码继续写下去。如果看过之后忘记了或者自己卡住了，再回过头看一眼别人的，然后把自己的代码补全。千万不要自己死磕到底，或者完全抄别人的代码（就是屏幕一分为二，一边你的一边别人的，然后抄的得跟练打字似的）！当然也不能觉得这样做一遍，自己就都会了，信不信过几天你就忘了hhhhh 所以呢，过几天之后你还要回过头重复刷。起步的时候，刷题不在与题量多，而在于重复次数。刷个两三遍，差不多就能记牢了，这个时候你写的代码才完全是你的东西啦~
2、第一次参加的同学：
个人觉得蓝桥刚开始准备的时候，还是要先刷真题，了解了解情况。我在题解表格中也列出了每个题目涉及的算法，不难看出常考的算法有枚举（暴力）、递归、贪心、搜索（dfs和bfs）等基础算法，基础算法学起来也不难，多看看多做做就行了。如果时间有限，那么就只刷真题，多刷几遍。如果时间充足，那么刷完真题后，你也大致知道了蓝桥杯常考的算法和自己薄弱的算法，这个时候就可以去别的oj上练专题。
3、第二次参加的同学：
这就说的我，首先呢，不要觉得是第二次参加就希望大，这样真的真的很容易滑铁卢，好好准备还是需要的。可以先回顾一遍真题，省赛题不能满足你的话，也可以去刷国赛真题，或者去别的oj上刷题。由于是第二次参加，所以可以适当地让自己多学一些高级算法，当然基础算法也要巩固一下的，不能忘了本嘛~
4、第三次参加的同学：
你都是第三次参加了，是个成熟的选手啦，还要我给建议嘛？开玩笑的啦~ 一般第三次参加的同学都是大三生了，这个时候可能还要忙考研考公找工作之类的事情，所以准备时间可能并不是那么充裕，但是前两年的刷题经验应该也积累了不少了，不过就算没有太多时间，也有偶尔抽出一点时间做题，比如一天做个一两题这样的，状态和手感真的很重要！
🔑 二 如何混分篇
这种集中在结果填空与代码填空里面。这时你看能不能借助日历、计算器、WPS、txt文本、Notepad++或者数学方法等工具进行快速解出来，最后再选择用Eclipse代码暴力破解。
EXCEL用法
如果标题出现：第几天
2000年的1月1日，是那一年的第1天。
那么，2000年的5月4日，是那一年的第几天？
注意：需要提交的是一个整数，不要填写任何多余内容。
题解：
1、在EXCEL的两个格子上写上要的日期
2、点击C，在fx那里写上 =B1-A1
3、回车得答案，因为1/1是第一天，所以5/4是当年的第124+1 = 125天
4、而且还可以计算某天为星期几（省赛题目曾经出过）
计算器用法
标题：明码
汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。
16点阵的字库把每个汉字看成是 16x16 个像素信息。并把这些信息记录在字节中。
一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。
把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，
一共16行，布局是这样的
第1字节，第2字节 第3字节，第4字节 .... 第31字节, 第32字节
这题是给你一段多个汉字组成的信息，每个汉字用32个字节表示，这里给出了字节作为有符号整数的值。
题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形，从中看出题目的要求，并根据要求填写答案。
这段信息是（一共10个汉字）：
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4 4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64 16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128 0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0 2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0 1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0 0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0
注意：需要提交的是一个整数，不要填写任何多余内容。
题目大意是这样
上面一行数字的十进制转化为二进制，而且两个数字的二进制数为一行，最后一行数字组成的二进制数的1可以画成代表一个文字，一共10行，最后输出结果。
题解：
如果不会敲题目，这时候可以用计算器的十进制转二进制的方法。比如第一行为4 0两个数字，这时候用计算器算出
4的八个二进制为 00000010
0的八个二进制为 00000000
反正同一行变成一行
0000001000000000
2 如此类推可以得出第一个答案为，其中就是二进制的1空着的为二进制的0，这是我用程序输出第一个字的答案
3、最后的10个汉字是：九的九次方等于多少？
答案就输入：387420489
比赛注意事项
- 不要使用 package 语句
- 类的名称必须采用 Main 方式命名
- 提前设置好你常用代码模板
- 同时打开JDK1.6的API文档
Eclipse使用技巧
1,debug调试
F5: 跳入方法
F6: 向下逐行调试
F7：跳出方法
F8: 直接跳转到下一个端点
2，Ctrl+Q 跳回上一操作处
3，Ctrl+D 快速删除光标行
4，Ctrl+O 查看当前类的所有 方法
三 🏅 必需掌握的
1，输入：static Scannner sc = new Scanenr(System.in);
2、换行：sc.nextLine 整数sc.nextInt 小数sc.nextDouble
3、一维数组输出：java.util.Arrays.toString(A); (A为一维数组)
3、多维数组输出：java.util.Arrays.deepToString(B); (B为多维数组)
4、两数字交换： int temp=a1; a1=a2; a2=temp;
5、一维数组长度：int A[] = {1,2,3,4,5} A.length=5
6、二维数组长度：int[][] A = new int[3][4] A.length=3 A[0].length=4
7、数组长度总结：A.length 表示有多少行 A[i].length表示第行列有多少列
7、break和continue：break结束整个循环体，continue结束单个循环
8、基本数据类型转大数：Bigdecimal c = Bigdecimal.value(X);
9、强制转换：long b = (long)a;
10、字符串问题：String类型定义的是字符串，char[]定义的是字符数组
11、String转化为char：char[] c1 = s1.toCharArrays(s1);
12、字符串分割：分割的字符串必须用字符串数组存储String[] str = s.split("/");
13、强制结束进程：system.exit(0);
14、int和Integer：自动装箱:Integer.valueOf(int i)，自动拆箱:i.intValue()
15、对象类比较用equals，地址比较用==
16、定义integer类，-128~127存在缓存中，其他的需要创建一个新的Integer对象
17、定义数字变量，int比Integer快
18、定义当前时间：double startTime = System.currentTimeMillis();
19、声明boolean数组：Boolean Bool[] = new boolean[xx];
20、构造器：public 类名(){} (构造方法没有返回值， 构造方法：一般用于给对象赋初始值）
21、this关键字：(1)指代当前对象(2)指代当前类(3)指代构造方法(只能放在首行)
22、求最大公约数和最小公倍数时需要求绝对值：Math.abs();
23、java输出换行：System.out.print("\n"+......);
java字符串和字符数组的转换
（1）String字符串转化为字符数组：String->char[] char[] a1 = s1.toCharArrays();
（2）char[]字符数组转化为字符串：char[]->String String[] s1 = String.valueOf(a1);
（2）char[]字符数组转化为字符串：char[]->String String s1 = new String(a1);
（3）String查找字符串中的一个字符：char a = String.charAt(index);
（3）String查找字符串中的一个字符：char a = String.codePointAt(index);
（4）String字符串转换成大写：String up = s1.toUppercase();
（5）String字符串转化为小写：String low = s1.toLowercase();
（6）char字符转化成大写：String upch = a1.toString().toLowercase();
（7）char字符转化成小写：String lowch = a1.toString().toUppercase();
（8）String字符串替换：String rep = s1replace(oldChar, newChar);
（9）String字符串字符char的第一次索引：int a = s1.indexOf(String str);
（10）String字符串字符char的最后一次索引：int a = s1.lastIndexOf();
（11）String字符串的子字符串：String sub = s1.substring(beginIndex);
（11）String字符串的子字符串：String sub = s1.substring(beginIndex,endIndex);
（12）String字符串删掉最后一个字符：s = s.subString(0,s.length-1);
（13）二维数组克隆：
(1)copy = c.clone(); //直接复制全部
(2)System.arraycopy(c,0,copy,0,N); //最底层,复制c到copy，从0-N
(3)copy = Arrays.copyOf(c,N); //复制c到copy，复制的长度为N
(4)copy = Arrays.copyOfRange(c,0,N);//复制c到copy，从c的第0到N个复制
效率：System.arraycopy > Arrays.copyOf > for循环 > clone
1 这里想强调下大数类的用法
BigInteger类可以表示 long 型都无法表示的整型数据。大数类 BigInteger 不是基本数据类型，对于大数据的操作都是通过字符串来，因此不能用整型的"+"、"-"、"*"、"/" 来简单计算，他有自己运算方法。
使用大数类来操作数据前，需要先通过构造器创建一个BigInteger 对象。
BigInteger构造器
查看文档关于BigInteger的Java API
- valueOf
public static BigInteger valueOf(long val)
返回一个BigInteger, 其值等于指定 long 的值
BigInteger a = new BigInteger("666666666666666666666");
BigInteger b = BigInteger.valueOf(3);
得到大数类对象之后就可以进行运算。 ### 2 关于大数类四则运算 - 大数加法 ```java public BigInteger add(BigInteger val)
与整数的加法一样 不过返回值是BigInteger
a.add(b) //a加b
- 大数减法
public BigInteger subtract(BigInteger val)
与整数的减法一样 不过返回值是BigInteger ```java a.subtract(b) //a减b
- 大数乘法
public BigInteger multiply(BigInteger val)
与整数的乘法一样 不过返回值是BigInteger ```java a.multiply(b) //a乘以b
- 大数除法
public BigInteger divide(BigInteger val)
与整数除法一样 不过返回值是BigInteger
另外还要注意处理除数为零的异常ArithmeticException - if val is zero
- 其他常用方法
public BigInteger pow(int exponent)
返回当前大整数的exponent次方
public BigInteger abs()
返回当前大整数的绝对值
public String toString()
将当前大整数转换成十进制的字符串形式
这里举例子
package 大数类常用方法;
import java.math.BigInteger; /** * @author JohnnyLin * @version Creation Time：2020年6月12日 下午9:44:39 */ public class BigInteger的常用方法 { public static void main(String[] args) { BigInteger a=new BigInteger("666666666666666666666"); BigInteger b=BigInteger.valueOf(3); System.out.println(a.add(b)); //加法 666666666666666666669 System.out.println(a.subtract(b) );//减法 666666666666666666663 System.out.println(a.multiply(b));//乘法 199****999999999999998 System.out.println(a.divide(b));//除法 222222222222222222222 System.out.println(b.pow(5)); //b的五次方 243 System.out.println(b.subtract(a).abs());//b-a的绝对值 666666666666666666663 String s=b.toString(); //将b转为字符串类型 System.out.println(s); //3 } }
3 总结的小技巧
%.3f保留3位小数并四舍五入
&&的优先级要高与||和&&有点类似于*，||类似于+
if(1) if(b) x++; else //else默认和最近的一个if配对
if(fabs(m*my-n*ny)<0.000001)//浮点数判断相等，要近似判断，如果用==得不到结果。//fabs(float x)浮点数x的绝对值
质数：又叫素数，在大于1的自然数中，除了1和它本身以外不再有其他因数。
互质数：公因数只有1的两个非零自然数
同余定理，例如：1234%10
1234%10=(((1%10*10+2)%10*10+3)%10*10+4)%10
高次方数的尾数
规律：1-100中 凡是有因子5，尾数就增加一个零；有因子25，尾数就增加两个零。
100!有24个零，1000!有249个零。
int main() {
int i;
for(i=1; i<100; i++) {
if(i%2==0) //填空
printf("%d \n", i*i/2);
else
printf("%d \n", (i*i-1)/2);
}
printf("\n");
}
求数字下标规律：1,3,6,10,,,, 公式：i*(i+1)/2
唯一分解定理：
ll getfac(ll x)//唯一分解定理
{ ll ans=1;
for(int i=1;i<=cnt&&primel[i]*primel[i]<=x;i++) {
ll sum=0;
while(x%primel[i]==0) {
sum++;
x/=primel[i];
}
ans*=(sum+1);
} if(x>1) ans*=2;
returnans;
}
一年的12个月：1-12月
31,28/29、31、30、31、30、31、31、30、31、30、31
闰年： (year%4==0&&year%100!=0)||(year%400==0)
四 📖 常用代码模板
辗转相除法求最大公约数
int gcd(int a, intb) {
if (b == 0) return a;
else return gcd(b, a % b);
}
//最小公倍数
lcm(a,b)=(a*b)/gcd(a,b)
判断闰年
int is_leap_year(int year){
if(year%400==0||(year%100!=0&&year%4==0)){
return 1;
}
return 0;
暴力搜索：dfs。凑算式
#include<stdio.h>
int num[10];
int ans=0;
bool visit[10];
void solve(){
double sum = num[0]+(double)num[1]/num[2]+(double)(num[3]*100+num[4]*10+num[5])/(num[6]*100+num[7]*10+num[8]);
if(sum==10){
ans++;
}
void dfs(int index){
if(index==9){
solve();
return;
}
for(int i=1;i<10;i++){
if(!visit[i]){
visit[i]=true;
num[index]=i;
dfs(index+1);
visit[i]=false;
}
}
}
int main(){
dfs(0);
printf("%d\n",ans);
return 0;
}
}
快速排序
void swap(int a[],int i,int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[],int p,int r){
int i = p;
int j = r+1;
int x = a[p];
while(1){
while(i<r&&a[++i]<x);
while(a[--j]>x);
if(i>=j)break;
swap(a,i,j);
}
swap(a,p,j);
return j;
}
void quicksort(int a[],int p,int r){
if(p<r){
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main(){
int a[]={5,12,65,44,2,8,62,4,3,98,14,25};
int N=12;
quicksort(a,0,N-1);
for(int i = 0;i < N;i++){
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
判断括号是否合法
public static boolean isValid(String exp) {
if(exp==null||exp.equals("")) return true;
char e[]=exp.toCharArray();
Stack<Character> stack=new Stack<>();
for(int i=0;i<e.length;i++) {
if(e[i]=='<'||e[i]=='{'||e[i]=='('||e[i]=='[')//左括号则入栈
stack.push(e[i]);
else {
//取出栈顶左括号与现有右括号匹配
//取前要判断栈非空
if(!stack.isEmpty()) {
Character c=stack.peek();
stack.pop();
if(c=='<'&&e[i]=='>')continue;
if(c=='{'&&e[i]=='}')continue;
if(c=='('&&e[i]==')')continue;
if(c=='['&&e[i]==']')continue;
}
return false;
}
}
//若左右括号匹配 则栈为空返回真值
return stack.empty();
}
前缀和
static int a[]= {1,5,36,7,0,52,67,5};
//1 6 42 49 49 101 168 173
static int []preSum;
public static void prefixSum() {
int len=a.length;
preSum=new int[len];
preSum[0]=a[0];
for(int i=1;i<len;i++) {
preSum[i]=preSum[i-1]+a[i];//preSum[j]-preSum[i]查询(i,j)区间的区间和
}
}
区间树
使用前缀和可以O(1)操作查询区间和，O(n)操作更新。对于在计算过程中需要更新原数据的这种区间求和，可以使用区间树实现O(logn)更新，O(logn)查询。
class SegTree{
//左右子树
SegTree lson,rson;
//区间范围
int l,r;
int sum;
public SegTree(int l,int r) {
this.l=l;
this.r=r;
}
}
public class 线段树区间求和 {
static int [] a={1,5,36,7,0,52,67,5};
static int [] b=new int[a.length];;
static int [] ans;
static SegTree root;
/**
* @param l
* @param r
* @return 根据给定区间建立[l,r]范围的线段树
*/
public static SegTree buildsegTree(int l,int r) {
SegTree segTree=new SegTree(l, r);
if(l==r) {
segTree.sum=a[l];
return segTree;
}
int mid=(l+r)>>1;
SegTree lson=buildsegTree(l, mid);
SegTree rson=buildsegTree(mid+1, r);
segTree.lson=lson;
segTree.rson=rson;
segTree.sum=lson.sum+rson.sum;
return segTree;
}
/**
* @param tree
* @param x
* @param y
* @return 返回[x,y]区间和
*/
public static int query(SegTree tree,int x,int y) {
int l=tree.l;
int r=tree.r;
if(x<=l&&y>=r) return tree.sum;
int mid=(l+r)>>1;
int ans=0;
if(x<=mid) ans+=query(tree.lson, x, y);
if(y>mid) ans+=query(tree.rson, x, y);
return ans;
}
/**
* @param tree
* @param p 下标
* @param i 值
* 修改了原数据需要，需要更新线段树
* 时间复杂度：log(n)
*/
public static void update(SegTree tree,int p,int i) {
if(tree==null)//叶子结点的下一层了
return;
//更新节点的sum
tree.sum+=i;
int l=tree.l;
int r=tree.r;
int mid=(l+r)>>1;
if(p<=mid) update(tree.lson, p, i);
else update(tree.rson, p, i);
}
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
//建立与原数组长度相对的区间树
root=buildsegTree(0, a.length-1);
//1 6 42 49 49 101 168 173
//[i,j] {1,5,36,7,0,52,67,5}
System.out.println(query(root,3,6));//126
System.out.println(query(root,0,0));//0
System.out.println(query(root,0,2));//6
//修改a数值元素值
a[4]=11;
update(root, 4, 11);
System.out.println(query(root,3,6));//6
}
}
14 埃氏筛法(搜索n以内的所有素数)
int prime[MAX_N];//第i个素数
bool is_prime[MAX_N + 1];
//返回n以内素数的个数
int sieve(int n) {
int p = 0;
for (int i = 0; i <= n; i++)
is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if(is_prime[i]){
prime[p++] =i;
for(int j = 2*i; j <= n; j += i)
is_prime[j] = false;
}
}
returnp;
}
筛选法求素数
memset(vis,0,sizeof(vis));
for (int i=2;i<=n;i++) {
for (int j=i*2;j<=n;j+=i)
vis[j]=1;
}
升级版:素数定理 不超过x的素数个数近似(略超过) x/lnx;
int m=sqrt(n+0.5); memset(vis,0,sizeof(vis)); for (int i=2;i<=m;i++) if (!vis[i]) for (int j=i*i;j<=n;j+=i) vis[j]=1;
快速幂取模
long long quick_mod(long long a,long longb){
long long res=1;
while(b!=0){
if (b%2==1) res*=(a%n);
a=a*(a%n);
b/=2;
}
return res;
}
但是当数据量大于10^19时，long long会爆，所以利用快速乘法，原理类似，a*b就是b个a相加，将b表示为二进制：
int n;
long long mul(long long a,long longb){
long long res=0;
while(b!=0){
if(b%2==1) res=(res+a%n)%n;
a=(a%n+a%n)%n;
b/=2;
}
returnres;
}
long long quick_mod(long long a,long longb){
long long res=1;
while(b!=0){
if (b%2==1) res=mul(res,a)%n;
a=mul(a,a);
b/=2;
}
return res;
}
二分排序
/*nums[]指的是有序数组；low指的是数组下标0；high指的是数组下标n-1(n指的是数组长度)；target指的是要插入的目标元素*/
void sort(int nums[],int low,int high,inttarget) {
int n=high+1;//当low<=high一直循环折半查找，当low>high时结束循环
while(low<=high) {
int mid=(low+high)/2;//计算中间下标
if(nums[mid]>=target) { //如果大于等于要插入的元素，则high=mid-1
high=mid-1;
} else if(nums[mid]<target) {
low=mid+1;
}
} //然后将nums[high+1]之后的所有元素(包括nums[high+1])向后移动一个位置
for(int i=n; i>high+1; i--) {
nums[i]=nums[i-1];
}//然后将空出来的nums[high+1]赋为target值
nums[high+1]=target;
} 进制转换
#include "stdio.h"
int a[10000];
intmain() {
int r,n;
char d;
while(~scanf("%d%d",&n,&r)){
int e=n;
if(n<0)
n=-n;
int i=0,j;
while(n!=0) {
a[i]=n%r;
n=n/r;
i++;
}
for(j=i-1; j>=0; j--) {
if(e<0) {
if(j==i-1)
printf("-");
if(a[j]>9) {
d=a[j]-10+'A';
printf("%c",d);
} else
printf("%d",a[j]);
} else
{ if(a[j]>9) {
d=a[j]-10+'A';
printf("%c",d); }
else
printf("%d",a[j]);
}
}
printf("\n");
}
return 0;
}
不带重复元素的全排列
public class 全排列_不带重复元素的_抓 {
static int[]a= {1,2,3,4,5};
static boolean vis[]=new boolean[a.length];
static int ans;
public static void dfs(int m,String s) {
if(m==a.length) {
//s记录一个排列方案
System.out.println(s);
//ans记录排列方案数目
ans++;
return;
}
for(int i=0;i<a.length;i++) {
if(!vis[i]) {
vis[i]=true;
dfs(m+1,s+a[i]+" ");
vis[i]=false;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
dfs(0,"");
//A(5,5)=120
System.out.println(ans);
}
}
二进制压位
int ans=0;
for(int i = 0;i < (1<<14);i++){
int tot_1=0;
int tot_0=0;
int num = 2;
for(int j = 0;j < 14;j++){
if(i&(1<<j)){
tot_1++;
num = num*2;
}else{
tot_0++;
num=num-1;
}
}
if(tot_1==5&&tot_0==9&&num==1){
ans++;
}
} 背包
解决办法：声明一个大小为 m[n][c] 的二维数组，m[i][j] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，
(1). j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
m[i][j] = m[i-1][j]
(2). j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。
如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 跟(1)一样的
究竟是拿还是不拿，自然是比较这两种情况那种价值最大。
for(int i = 1;i <= N;i++){
for(int j = 0;j <= v;j++){
if(j>=w[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
完全背包问题
完全背包表示每个物品可以取无限次，只要加起来总容量不超过V就题目的88。
同样可以用f[i][j]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值。则其状态转移方程为
f[i][j] = max{f[i-1][j-k*weight[i]] + k*value[i]} ,其中(0 <= k <= j/weight[i])
for(int i = 1;i <= N;i++){
for(int j = c[i];j <= v;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+w[i]);
}
}
dp[N][v];
多重背包问题
多重背包它是每个物品有不同的个数限制，如第i个物品个数为num[i]。同样可以用f[i][j]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值，且每个物品数量不超多num[i]。则其状态转移方程为：
f[i][j] = max{f[i-1][j-k*weight[i]] + k*value[i]} ,其中要满足(0 <= k <= min{j/weight[i], num[i]})
五 ⛳ API熟记心中
输入
Scanner sc = new Scanner(new BufferedInputStream(System.in));//格式1
Scanner sc = new Scanner(System.in);//格式2
//在读入数据量大的情况下，格式1的速度会快些
//读数
int n = sc.nextInt();//读一个整数
double t = sc.nextDouble();//读一个浮点数
String s = sc.next();或String s = sc.nextLine();//读一个字符串
注意点：
in.next() 从缓冲区接收字符遇到空格后停止。
in.nextLine() 从缓冲区接收字符，并且接收空格，遇到换行才停止，并且会自动舍弃换行的。
//判断是否有下一个输入可以用
sc.hasNext()
sc.hasNextInt()
sc.hasNextDouble()
sc.hasnextLine()
输出
System.out.printf();//可使用格式控制符进行格式化输出。
//譬如，输出一个int类型变量 System.out.printf("%d", a);
System.out.print();//不能使用格式控制符进行格式化输出
System.out.println();//不能使用格式控制符进行格式化输出，仅仅是输出变量，但会自动输出一个换行
字符串
toCharArray()//字符串直接转字符数组
charAt(index)//获取字符串指定索引处字符
subString(begin, over)//字符串的截取方法（前闭后开）
contains() //字符串中是否含有某个字符
equals() //字符串比较相等
concat() //字符串连接
//字符串中按空格分成多个字符串 并放进数组
String s = "CSDN achieves 100 million technicians"
String[] srr = s.split(" ")//[CSDN achieves 100 million technicians]
类型转换
//一、String转为int int i = Integer.parseInt（s）； int i = Integer.valueOf(s) ; //记这个 //二、int转为String String s = Integer.toString(i); String s = String.valueOf(i); //记这个 String s = “” + i; //更改Integer为Double或者Float //更改parseInt为parseFloat（）或者parseDouble（）就能实现其他类型间的转换
BigInteger
int最大值：2147483647 2后面9个0
long最大值：9223372036854775807 9后面18个0
int 和 long放不下时，用BigInteger
BigInteger bi = new BigInteger("1234567890");
System.out.println(bi.pow(5)); // 286797186****71810723376143****672048294900000
常用方法：add()、subtract()、mutiply()、divide（） 例a.mutiply(b)
2.4 BigDecimal
BigDecimal可以表示一个任意大小且精度完全准确的浮点数。
BigDecimal bd = new BigDecimal("123.4567");
System.out.println(bd.multiply(bd)); // 15241.55677489
保留小数:
BigDecimal a = new BigDecimal("4.5635");
a = a.setScale(3, RoundingMode.HALF_UP); //保留3位小数，且四舍五入
Math
求最小值
Math.min(int a, int b) Math.min(float a, float b) Math.min(double a, double b) Math.min(long a, long b)
求最大值
Math.max(int a, int b) Math.max(float a, float b) Math.max(double a, double b) Math.max(long a, long b)
做一个
public class Main {
public static main(String[] args) {
int a = 10;
int b = 10;
System.out.println(Math.min(a, b));
System.out.println(Math.max(a, b));
}
}
求平方根
Math.sqrt(double a)
返回正确舍入的 double 值的平方根
求绝对值
Math.abs(double a) Math.abs(int b) Math.abs(float c) Math.abs(long d)
做一个
public class Main {
public static void main(String[] args) {
double a = -1.1314159;
System.out.println(Math.abs(a));
}
}
自定义比较器
java中想要比较自定义类，可以有两种自定义比较器的方法：一是通过实现Comparable接口的compareTo()方法来使得自定义对象可比来实现。二是通过实现Comparator接口的compare方法
第一种
可以通过实现Comparable接口的compareTo()方法来使得自定义对象可比来实现。
compareTo()方法，只有一个参数，返回值为int。返回值大于0表示对象大于参数对象；小于0表示对象小于参数对象；等于0表示两者相等。
record类重写compareTo方法，先按id比较 ，相同id则按ts比。
@Override
public int compareTo(record o) {
if(this.id==o.id)
return this.ts-o.ts;//若return o.ts-this.ts;则为降序
else
return this.id-o.id;
}
【调用】
声明的是record类数组则使用Arrays.sort()排序
record blog[]=new record[N]; Arrays.sort(blog);
若是集合类则使用Collections.sort()排序
List<record> blog=new ArraysList<record>; Collections.sort(blog);
【题目来源】
第九届蓝桥杯javaB组日志统计
自定义record类，record类存放每条记录的时间ts的评论id，通过实现Comparable的compareto方法，使得对于存放record类对象的数组blog排序时按自定义的排序规则排序，即：先按id比较，相同id则按ts比，升序输出。
【详细代码】
import java.util.Arrays; import java.util.Scanner; /** * @author JohnnyLin * @version Creation Time：2020年5月30日 下午2:48:40 * 类说明 */ public class t08_日志统计2 { //record类存放每条记录对应的时间和id //record实现comparable接口 以实现每条记录的排序 public static class record implements Comparable<record>{ int id,ts; record(int id,int ts){ this.id=id; this.ts=ts; } //重写compareTo方法 先按id比较 相同id则按ts比 @Override public int compareTo(record o) { if(this.id==o.id) return this.ts-o.ts; else return this.id-o.id; } } public static void main(String[] args) { Scanner reader=new Scanner(System.in); int N=reader.nextInt(); int D=reader.nextInt(); int K=reader.nextInt(); //声明一个存放每一条点赞记录的数组 record blog[]=new record[N]; boolean flag[]=new boolean[100000]; for(int i=0;i<N;i++) { int ts=reader.nextInt(); int id=reader.nextInt(); //每一个blog[i]对应存放一条记录 blog[i]=new record(id,ts); } Arrays.sort(blog); } }
【输入】
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
【输出】
排完序之后
1 0 1 9 1 10 3 100 3 100 10 0 10 10
第二种
- 通过实现Comparator接口的compare方法
- compare方法有两个参数，返回值与Comparable的compareTo()方法一样.
- Comparator接口一般不会被集合元素类所实现，而是单独实现或者匿名内部类方式实现。如上述类中，Comparator不直接在Edge类实现，因此Edge类结构未发生变化.
【声明即调用】
//声明列表 edgeList
List<Edge> edgeList=new ArrayList<Edge>()
略去往edgeList中加入元素的代码
//对edgeList按Edge的distance值排序
Collections.sort(edgeList, new Comparator<Edge>() {
public int compare(Edge o1, Edge o2) {
return o1.distance-o2.distance;//升序
}
});
详细代码
class Edge{
//两个顶点
private String start;
private String end;
//两个顶点距离
int distance;
public Edge(String a, String b, int d) {
start =a;
end =b;
distance=d;
}
public String getStart() {
return start;
}
public String getEnd() {
return end;
}
}
//声明列表 edgeList
List<Edge> edgeList=new ArrayList<Edge>()
//往列表添加元素代码省略
//对edgeList按Edge的distance值排序
Collections.sort(edgeList, new Comparator<Edge>() {
public int compare(Edge o1, Edge o2) {
return o1.distance-o2.distance;//升序
}
});
对数组排序
在做一些算法题时常常会需要对数组，自定义对象，集合进行排序，在 Java 中对数组提供了
Arrays(arr, new Comparator<Integer>()) {// arr是数组名，<>是待排序集合所包含的数据类型
public compare(int a, int b) {//待排序集合中的元素是什么数据类型，这里的两个函数参数就定义为什么数据类型
return a - b;//升序
//return b - a;//降序
//a - b>0 交换ab位置，反之不变，即返回值为正数时，交换数组中正在比较的
//两个元素的位置，返回值为负数时，则不交换
}
}
举例题
import java.io.*;
import java.util.*;
public class Main {
//输入输出模板
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedReader out = new BufferesWriter(new OutputStreamWriter(System.out));
static int n;
public static void main(String[] args) throws IOException {
public int compare(String a, String b) {
if(a.length() == b.length()) {//如果长度相等则直接比较字典序
return a.compareTo(b);
}
else {//长度长的一定大
return a.length()-b.length();
}
}
}
}
对集合进行排序
创建TreeeSet实例，对其从大到小排序。由于TreeSet是自动排序和去重的，默认是升序，我们重写比较器去构造一个降序的TreeSet, 之后添加数据就会自动排序
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) {
TreeSet<Integer> s = new TreeSet<>(new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a-b;
}
});
s.add(10);
}
} String
这个类包括的方法用在检索序列的单个字符，比较字符串，搜索字符串，提取字符串，还有创建字符串副本并把所有字符全部转换为大写或小写先看遍历，其有两种方式，第一种charAt()方法；第二种是先化成字符数组，再挨个遍历
charAt(int i); //返回索引i处的字符 length(); //返回字符串的长度 isEmpty(); //是否为空，当length()为0，则返回true
演示两个方法
toCharArray(); //返回字符串的字符数组
String s = "123456";
char[] str = new char[10];
s1 = s.toCharArray();
for(int i=0; i<str.length; i++) {
System.out.print(str[i] + " ");//输出1 2 3 4 5 6
}
charAt(int i); //返回索引i处的字符
String s = "123456";
for(int i=0; i<s.length(); i++) {
System.out.println(s.charAt(i) + " ");//输出1 2 3 4 5 6
}
String的比较
compareTo(String anotherString);//按字典顺序比较两个字符串compareToIgnoreCase(String anotherString)//按字典顺序且不区分大小写比较两个字符串equals(String anotherString);//判断两个字符串是否相等equalsIgnoreCase(String str);//同上，也不区分大小写。compareTo()和compareToIgnoreCase()方法的返回值：
a.compareTo(b)
如果a > b返回大于0的整数
如果a = b 返回0
如果a < b 返回小于0的整数
其实是返回a和b第一份不同字符的差值
String s = "datalong";
String s1 = "DATALONG";
int R = s.compareTo(s1);
int R1 =s1.compareToIgnoreCase(s);
boolean R2 = s.equals(s1);
boolean R3 = s.equalsIgnoreCase(s1);
System.out.println(R);
System.out.println(R1);
System.out.println(R2);
System.out.println(R3);
输出：
字符长切割再赋值操作：
static int year,month,day,Mon;
static Scanner sc = new Scanner(System.in);
static String str = sc.next();
String[] s = str.split("/");
year = Integer.valueOf(s[0]);
month = Integer.valueOf(s[1]);
day = Integer.valueOf(s[2]);
Calendar日期类
在蓝桥中有关于日期计算的问题，正好java的 Date类 和 Calendar类 提供一些对日期处理的一些方法。Date类大部分已经废弃了，所以详细说说Calendar类
Calendar类
是一个抽象类，它为特定瞬间与一组诸如YEAR，MONTH，DAY_OF_MONTH，HOUR等这种日历字段之间的转换提供了一些方法，并为操作日历字段（如获得下星期的日期）提供一些方法。
getInstance(); //返回一个默认时区和语言环境的日历
Calendar calendar = Calendar.getIntstance();//赋值给calendar
如何设置特定日期
set(int field, int value);//第一个是日期字段，比如YEAR, MONTH 等给定的日历字段设置值。 set(int year, int month, int date);//设置日历字段年月日的值
数据结构
2.5 数组
数组的创建
int[ ] arr1= new int[3]； int[ ][ ] arr = new int[m][n]；
数组的输出
//一维数组
int[] arr1= {1,2,3,4};
System.out.println(Arrays.toString(arr1));//[1, 2, 3, 4]
//二维数组
int[][] B= {{1,2,3,4},{5,6,7,8}};
System.out.println(Arrays.deepToString(B));//[[1, 2, 3, 4], [5, 6, 7, 8]]
数组的长度
一维数组：A.length 表示有多少行
二维数组：A[i].length表示第i行列有多少列
数组排序
Arrays.sort(arr) 默认升序
降序：
int [] arr={1,2,3,4,5,6};
int [] arr2=new int[6];
Arrays.sort(arr);//排序默认升序
for(int i=0,j=arr.length-1; i<=arr.length-1 & j>=0; i++,j--) {
arr2[i]=arr[j];
}
数组克隆
int[] arr1= {1,2,3,4};
int[] arr2=arr1.clone(); //[1, 2, 3, 4]
动态数组
ArrayList<Integer> list1 = new ArrayList(); ArrayList<String> list2 = new ArrayList(); 增 list1.add(element); 删 list1.remove(index); 改 list1.set(index,element); 查 list1.get(index);
PriorityQueue
翻译过来就是优先队列，但本质是一个 堆, 默认情况下堆顶每次都保留最小值，每插入一个元素，仍动态维护堆顶为最小值。
如何初始化
ProiorityQueue<Integer> queue = new PriorityQueue<>(); //初始化
实现大根堆的两种方式
因为 Java 中的优先队列默认是小根堆，要实现大根堆可以用两种方法
1 用自定义比较器
2 将所有数据变成自身的负数之后在插入，因为添加个负号就相当于是逆序了呗。1<2<3 取负之后变成 -1>-2>-3
举个例public static void main(String[] args) { Scanner in = new Scanner(new InputStreamReader(System.in)); }常用方法1
十六进制数2022对应的十进制数是多少？
这是一道填空题，只需要算出结果后提交即可。本题的结果是一个整数，填写答案时不要多写否则没有得分。
考的是java中的 valueOf 与 parseInt 有什么区别，以 Integer类 为例，其中的 valueOf 是转成 Integer封装类型，parseInt 是转换成 int 基本数类型
public class 十六进制转十进制 {
public static void main(String[] args) {
System.out.print(Integer.valueOf("2022", 16));
//或 System.out.println(Integer.parseInt("2022", 16));
}
}
小蓝准备
不超过19000的正整数中，与19000互质的数的个数是多少？
互质：公约数只有1的两个整数，叫互质数。
约数与倍数：整数a除以整数b(b!=0)得的商正好是整数而没有余数，我们
public class 质数19000 {
public static void main(String[] args) {
int count = 0;
for(int i=1; i<=19000; i++) {
if(i%2!=0 && i%5!=0 && i%19!=0) {
count++;
}
}
System.out.println(count);
}
}
int fun(int n, int a[], int idx)
{
if(_____) return 1; //填空1
if(idx==4) return 0;
for(int i = (int) sqrt(n); i>=1; i--) {
a[idx] = i;
if(_____) return 1; //填空2
}
return 0;
}
int main(int argc, char* argv[]) {
for(;;)
{
int number;
printf("输入整数(1~10忆): ");
scanf("%d", &number);
int a[] = {0, 0, 0, 0};
int r = fun(number, a, 0);
printf("%d: %d %d %d\n", r, a[0], a[1],a[2], a[3]);
}
return 0;
}
这是道递归，思路是每次减去形参中的 n 的平方根，在进行递归，减过后的数再次作为 n, 结束条件是当 n 减为 0 时就结束了。
答案：n=0 fun(n-i*i,a,idx+1)==1
请问在 1 到 2020 中，有多少个数与 2020 互质，即有多少个数与 2020 的最大公约数为 1。
会gcd就是送分题
public class test {
public static void main(String[] args) {
int count = 0;
for(int i=1; i<2020; i++) {
if(gcd(i, 2020)==1) {
count++;
}
}
System.out.println(count);
}
public static int gcd(int a, int b) {
return b==0?a:gcd(b, a%b);
}
}
在 Excel 中，第 1 列到第 26 列的列名依次为 A 到 Z，从第 27 列开始，列名有两个字母组成，第 27 列到第 702 列的列名依次为 AA 到 ZZ。
之后的列再用 3 个字母、4 个字母表示。
请问，第 2021 列的列名是什么？
题目解析
这题计算26进制,如果闲写代码麻烦,打开excel看看列名就行
public class test {
public static void main(String[] args) {
char A;
char B;
char C;
for(int i=0; i<26; i++) {
for(int j=0; j<26; j++) {
for(j2=0; j2<26; j2++) {
if(j2+j*26+i*26*26 == 2021) {
A = (char)(i+64);
B = (char)(j+64);
C = (char)(j2+64);
System.out.println("A"+"B"+"C");
}
}
}
}
}
小蓝正在写一个网页显示一个新闻列表，他需要将总共 n 条新闻显示，每页最多可以显示 p 条，请问小蓝至少需要分多少页显示？
例如，如果要显示2021条新闻，每页最多显示10条，则至少要分203页显示。
输入格式
输入的第一行包含一个整数 n，表示要显示的新闻条数。
第二行包含一个整数 p，表示每页最多可以显示的条数。
输出格式
输出一个整数，表示答案。
样例输入
2021
10
样例输出
203
样例输入
2020
20
样例输出
101
数据规模和约定
对于所有评测用例，1 <= n <= 10000，1 <= p <= 100。
题目解析
都第七题了还在送分
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int p = sc.nextInt();
int x = n%p;
int y = n/p;
if(x != 0) {
System.out.println(y+1);
}else {
System.out.println(y);
}
}
}
在书写一个较大的整数时，为了方便看清数位，通常会在数位之间加上逗号来分割数位，具体的，从右向左，每三位分成一段，相邻的段之间加一个逗号。
例如，1234567 写成 1,234,567。
例如，171****9184 写成 17,179,869,184。
给定一个整数，请将这个整数增加分割符后输出。
输入格式
输入一行包含一个整数 v。
输出格式
输出增加分割符后的整数。
样例输入
1234567
样例输出
1,234,567
题目解析
处理成字符串数组,按规则输出
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String n = sc.nextInt();
String[] s = n.split("");
if(s.length%3 == 0) {
for(int i=0; i<s.length; i++) {
if(i%3==1 && i!=1) {
System.out.print(",");
}
System.out.print(s[i]);
}
}else {
System.out.print(s[0] + s[1] + ",");
for(int i=2; i<s.length; i++) {
if(i%3==2 && i!=2) {
System.out.print(",");
}
System.out.println(s[i]);
}
}
}
}
杨辉三角
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
给出n，输出它的前n行。
样例输入
4
样例输出
1
1 1
1 2 1
1 3 3 1
代码如下所示
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
// 声明大小为n*n的二维数组存储值
int[][] arr = new int[n][n];
// 两层for循环，第一个控制行数，第二个控制列数，
// 第一列只有一个，第二列只有两个....,所以第二个for循环j<=i即可
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
// 判断每行是否在第一个或者最后一个位置，如果是那么就置为1
if (j == 0 || j == i){
arr[i][j] = 1;
}else {
// 否则当前位置的值就是上一行的前一个位置的值和上一行上一个位置的值之和
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (arr[i][j]!=0){
System.out.print(arr[i][j]+" ");
}
}
System.out.println();
}
}
}
#学习路径#更多干货请关注公粽号:龙哥手记 「加群进阶」, 进龙歌唯一的读者群。
如果有错误或者不严谨的地方，请务必得出指正，非常感谢。如果喜欢或者 有所启发，欢迎star, 对作者也是一种鼓励。
跟着龙哥一起掉亿点点秀发吧~, `别忘给我点赞 大帅比大漂亮们再走啊！！！
投递完美世界等公司10个岗位 >
我教你****：你好，本人985电子科大在读研一，本科西南大学（211）我在字节跳动实习过。对您的岗位很感兴趣，希望获得一次投递机会。
查看8道真题和解析