蓝桥杯备战条记分享（java）

蓝桥杯（10道题）

jdk 8

main函数

1.填空题（只必要给答案)

2道，每题5分
2.代码题（必要提交代码）

由易到难
   Java：尚硅谷（Java数据布局和算法） Python：清华大学（数据布局和算法） 大话数据布局和算法（第四版） 刷题网站： 1.洛谷（难）刷官方题单 2.北京大学 poj 3.acwing 4.力扣 暴力递归+暴力搜素+真题
  一、循环（前三道题涉及）

1. for循环

   一般能在标题里找到循环次数
  2. while循环

   只知道循环条件，不知道循环次数
    在考察循环时，还会涉及到集合、字符串等知识等知识点的用用。 比方：
  

• 对字符串一般考察常用函数。字符串转字符数组，判断末端等。
  
• 集合一般考察特性：
  
  
  
  • list:有序可重复
    
  • set:无序不可重复
    
  • map: key-value键值对（key不能为空，不能重复）
    
  
  

  例题1

标题描述：有些数字的立方的末端恰好是该数字自己。 比如：1,4,5,6,9,24,25,…
请你计算一下，在10000以内的数字中（指该数字，并非它立方后的数值），符合这个特征的正整数一共有多少个。
请提交该整数，不要填写任何多余的内容。

1.  public class Demo2 {
2.      public static void main(String args[]) {
3.          int cubedResult, num = 0;
4.          for (int x = 1; x <= 10000; x++) {
5.              cubedResult = x * x * x;//计算变量 x 的立方并将结果存储在 cubedResult 中。
6.              String xStr = "" + x;//将整数变量 x 转换为字符串类型，存储在 xStr 中。
7.              String cubedStr = "" + cubedResult;
8.              boolean endsWithX = cubedStr.endsWith(xStr);//检查 cubedStr 是否以 xStr 结尾，并将结果存储在 endsWithX 中。
9.              if (endsWithX) {
10.                  num++;
11.              }
12.          }
13.          System.out.println(num);
14.      }
15.  }

复制代码

 
例题2

1.  public class Demo3 {
2.      public static void main(String args[]){
3.          int length = 2019;
4.          int width=324;
5.          int count=0;//切出正方形的个数
6.                  while(true){
7.                      if(length>width){//长大于宽
8.                          length=length-width;
9.                          count++;
10.              }else if(length<width){//长小于宽
11.                          width=width-length;
12.                          count++;
13.                      }else if(length==width&&width!=0){
14.                          count ++;
15.                          width-=width;
16.                          length-=length;
17.                      }else if(width==0){
18.                          break;
19.                      }
20.                  }
21.                  System.out.println(count);
22.      }
23.      }
24.  ​
25.  ​
26.  结果：21
27.  Process finished with exit code 0
28.  ​

复制代码

例题3

TIP：

• 循环的终止条件已知==总工资>=108元，用while循环
  
• 等差数列（直接暴力解题）
  

1.  public class Demo4 {
2.      public static void main(String[] args) {
3.          int sum=0;//总钱数
4.          int i=1;//每天挣得钱
5.          int day=0;//总天数
6.          while(true){
7.              sum+=i;
8.              day+=1;
9.              if(sum>=108){
10.                  break;
11.              }
12.              i+=2;//后一天比前一天多挣2块钱
13.  ​
14.          }
15.          System.out.println(day);
16.      }
17.  }
18.  结果：11
19.  Process finished with exit code 0
20.  ​

复制代码

例题4

TIP(*4是因为拿了一堆，剩下4堆)：

• 用while循环（满足下列条件竣事）：
  1 .n%5=1 a=（n-1）/5*4
  2 .a%5=2 b=(a-2)/5*4
  3 .b%5=3 c=(b-3)/5*4
  4 .c%5=4 d=(c-4)/5*4
  5 .d%5=0 d>0
  
  1.  public class Demo5 {
  2.      /*
  3.  1 .n%5=1 a=（n-1）/5*4
  4.  2 .a%5=2 b=(a-2)/5*4
  5.  3 .b%5=3 c=(b-3)/5*4
  6.  4 .c%5=4 d=(c-4)/5*4
  7.  5 .d%5=0 d>0
  8.   */
  9.      public static void main(String[] args) {
  10.        int n=1;//香蕉数量
  11.          while(true){
  12.              if(n%5==1){
  13.                  int a=(n-1)/5*4;
  14.                  if(a%5==2){
  15.                      int b=(a-2)/5*4;
  16.                      if(b%5==3){
  17.                          int c=(b-3)/5*4;
  18.                          if(c%5==4){
  19.                              int d=(c-4)/5*4;
  20.                              if(d%5==0 && d>0){
  21.                                  break;
  22.                              }
  23.                          }
  24.                      }
  25.                  }
  26.              }
  27.              n++;
  28.              }
  29.          System.out.println(n);
  30.          }
  31.      }
  32.  ​
  33.  ​
  34.  3141
  35.  Process finished with exit code 0

  复制代码
   
  

3.字符串循环和集合的利用

   对集合考察集中在集合的特性和功能。set唯一性。list有序性。以及集合元素的个数。
  例题1：

TIP（set的唯一性，去除重复的子串）:

• 下标0截取范围：【0，最大下标】
  
• 下标1截取范围：【1，最大下标】
  

   截取的方法：subString(i,j)截取子串

1.  public class Demo6 {
2.      public static void main(String[] args) {
3.           String string="0100110001010001";
4.            HashSet<Object> set=new HashSet<>();//去重
5.          for(int i=0;i<string.length();i++){//从第几个下标开始截取
6.              for(int j=i;j<string.length();j++){
7.                String s= string.substring(i,j+1);
8.                  set.add(s);
9.              }
10.              System.out.println(set.size());//打印去重后的个数
11.          }
12.      }
13.  }
14.  结果：100

复制代码

 
例题2：

找到一个整数i，使得i的平方和i的立方构成的字符串恰好包含10个唯一的字符，然后输出该整数i的值。在循环中，代码逐个递增检查i的值，直到找到满足条件的整数为止。

1.  import java.util.HashSet;
2.  ​
3.  public class Demo2 {
4.      public static void main(String args[]) {
5.          int i = 1;
6.          while (true) {
7.              HashSet<Object> set = new HashSet<>();
8.              int ping = i * i;
9.              int li = i * i * i;
10.              String string = ""+ping + li ;
11.              if (string.length() == 10) {
12.                  char[] cs = string.toCharArray();
13.                  for (int j = 0; j < 10; j++) {
14.                      set.add(cs[j]);
15.                  }
16.                  if (set.size() == 10) {
17.                      System.out.println(i);
18.                      break;
19.                  }
20.              }
21.              i++;
22.          }
23.      }
24.  ​
25.  }
26.  结果：69

复制代码

4.循环求质数

• 质数是只能被1和它自己整除的数字。最小的质数是2
  
• 如何判断一个数字n是不是质数：找一下【2，n-1】有没有能被n整除的数字，有就不是质数。
  
• 整除：n对数字取余为0
  

例题

1.  public class Demo61 {
2.      public static void main(String[] args) {
3.          ArrayList<Object> list = new ArrayList<>();
4.          for (int i = 2; i <= 20000; i++) {
5.              int a = 0;//记录有没有除了1和它本身之外可以整除的数字
6.              for (int j = 2; j <i; j++) {
7.                  if (i % j == 0) {
8.                      a++;
9.                      break;//只要找到一个能被整除的就退出内层循环，提高运算效率
10.                  }
11.              }
12.              if (a == 0) {//没有能被整除的
13.                  list.add(i);
14.  ​
15.              }
16.              System.out.println(list.get(2022));
17.          }
18.  ​
19.      }
20.  }
21.  结果：
22.  17597

复制代码

二、排序与算法

1.排序

   在一维数组中，排序是很紧张的。冒泡排序，插入排序，选择排序（排序的思维差别）
  冒泡排序

第一趟竣事后最大的数字出现在最后一位（然后不消到场排序），第二趟竣事倒数第二大的数字出现在倒数第二位（不消到场排序）
   原理：比力两个相邻的元素，将较大的值交换到右边
  2 8 7 5 9 4 3
  第一趟:
     第一次：比力2和8 （不必要交换）
   第二次：比力8和7，（将8和7交换位置：2 7 8 5 9 4 3）
   第三次：比力8和5，（将8和5交换位置：2 7 5 8 9 4 3）
   第四次：比力8和9，（不必要交换）
   第五次：比力9和4，（将9和4交换位置 ：2 7 5 8 4 9 3）
   第六次：比力9和3，（将9和3交换位置：2 7 5 8 4 3 9）
    第二趟：
     第一次：比力2和7（不必要交换）
   第二次：比力7和5（必要交换 2 5 7 8 4 3 9）
   第三次：比力7和8（不必要交换）
   第四次：比力8和4（必要交换 2 5 7 4 8 3 9）
   第五次：比力8和3（必要交换 2 5 7 4 3 8 9）
   第六次：比力8和9（不必要交换）？
    第三趟：
     第一次：比力2和5（不必要交换）
   第二次：比力5和7（不必要交换）
   第三次：比力7和4（必要交换 2 5 4 7 3 8 9）
   第四次：比力7和3（必要交换 2 5 4 3 7 8 9）
   第五次：比力7和8（不必要交换）
   第六次：比力7和9（不必要交换）
   

1.  public class Demo11 {
2.      public static void main(String[] args) {
3.          //外层for循环控制趟，内层控制次数
4.          int a[]={10,1,35,61,89,36,55};
5.          for (int i = 0; i < a.length-1-i; i++) {//趟的次数是确定的
6.              for (int j = 0; j <a.length-1; j++) {
7.                  //判断相邻的两个数字
8.                  if(a[j]>a[j+1]){
9.                      //交换位置
10.                      int k = a[j];
11.                      a[j] = a[j+1];
12.                      a[j+1] = k;
13.                  }
14.              }
15.          }
16.          for(int i=0;i<a.length;i++){
17.              System.out.println(a[i]+"");//遍历
18.          }
19.      }
20.  }
21.  ​

复制代码

选择排序

   原理:
     第一次：从未排序的数据元素里面，选出一个最小的（最大的）的元素，然后和第一位元素交换位置；
   第二次：从未排序的数据元素里面，选出一个第二小的（第二大的）的元素，然后和第二位元素交换位置；
   。。。。以此类推
   

1.  public class Demo31 {
2.      public static void main(String[] args) {
3.          int a[] = {2, 9, 5, 0, 1, 3, 6, 8};
4.          int begin = 0;
5.          int end = a.length - 1;
6.          while (begin < end) {
7.              int min = a[begin];//min用来存储数组元素中的最小值
8.              int t = begin;//min的下标
9.              for (int i = begin; i <= end; i++) {
10.                  if (min > a[i]) {
11.                      min = a[i];
12.                      t = i;
13.                  }
14.              }
15.              a[t] = a[begin];
16.              a[begin] = min;
17.              begin++;
18.          }
19.          for (int i = 0; i < a.length; i++) {
20.              System.out.println(a[i] + "");//遍历
21.          }
22.      }
23.  }
24.  ​

复制代码

插入排序

   原理：将数列分为两个部分：排好序的数列 未排序的数列
  在未排序的数列里，挨个去插入到排好序的数列里面

1.  public class Demo22 {
2.      public static void main(String[] args) {
3.          int a[] = {2, 1, 6, 4, 9, 7, 6, 8};
4.          //为排好序的数组
5.          for (int i = 1; i < a.length; i++) {
6.              int k = a[i];//哨兵。从数组第二位元素开始，每一循环向后移动一位存储元素，将这个数插入排号数的数列中
7.              int j = i - 1;//排好序数列中的最后一位元素的下标(i是未排好序里面的第一位)
8.              while (j >= 0 && k < a[j]) {//哨兵要存在左边比他小，右边比它大
9.                  a[j + 1] = a[j];//给哨兵插入腾出位置
10.                  j--;//用j记录哨兵最终插入的位置
11.              }
12.              a[j + 1] = k;//哨兵插入
13.  ​
14.          }
15.          for (int i = 0; i < a.length; i++) {
16.              System.out.println(a[i] + "");//遍历
17.          }
18.      }
19.  }
20.  ​

复制代码

2.排序

递归

   函数/方法 直接/间接 的调用自己。一般用来在原来的底子上加减乘除等操纵
  案例：斐波那契数列：
  1 1 2 3 5 8 13……第一和第二个数字是1，其他数字即是前两个数字之和。Fn=F(n-1)+F(n-2)
  代码：计算第n位的斐波那契数字

1.      //递归：代码简洁，但是涉及的运算会随着递归层数的增加而指数增长，效率低下
2.      public static int Fn(int n){
3.          if(n==1||n==2){
4.              return 1;
5.          }
6.          return Fn(n-1)+Fn(n-2);
7.      }
8.  }
9.  ​

复制代码

例题

第20行第20列相当于这个数列的第20位数字。
  

1.  public class Demo33 {
2.   public static void main(String[] args) {
3.       System.out.println(snack(20));
4.   }
5.   public static int snack(int n){
6.       if(n==1){
7.           return 1;
8.       }
9.       return snack(n-1)+4*(n-1);
10.   }
11.  }

复制代码

记得找规律
问题：递归和循环的关系？
一道题可以用递归（代码简洁、但是时间复杂度大）解答，也可以换成循环（代码量变多、运算资源淘汰了、降低了时间复杂度）来解决
假如发现标题利用递归超出了限制，那么：

• 换循环；
  
• 加字典;
  

1.  public class Demo0 {
2.      public static void main(String[] args) {
3.          System.out.println(Fn(20));
4.      }
5.      //递归：代码简洁，但是涉及的运算会随着递归层数的增加而指数增长，效率低下
6.      public static int Fn(int n){
7.          if(n==1||n==2){
8.              return 1;
9.          }
10.          return Fn(n-1)+Fn(n-2);
11.      }
12.  }
15. 思考：用辗转相除法求最大公约数

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。