[数据结构与算法]【蓝桥】算法笔记真题篇（一）

历年真题

杨辉三角

• 题目：

将杨辉三角的数按从上到下、从左到右的顺序排成一列。给定一个正整数N，请输出数列中第一次出现N是在第几个数？

对20%的测试用例，1<=N<=10；对所有的测试用例，1<=N<=1000000000

• 思路1：(该思路适合N较小的时候，如1<=N<=10)

  用二维数组构造杨辉三角，停止构造条件是当

  arr[i][j]==N
  

  相应题解如下：（是参照基础题 “类型4：二维数组”的代码改过来的）

  import java.util.Scanner;
  public class Main {
      public static void main(String[] args) {
          Scanner s=new Scanner(System.in);
          int N=s.nextInt()+1;// 最多 构建一个长度为N的二维数组，下标为N-1
          int [][] arr=new int [N][N];
          arr[0][1]=0;
  
          for (int i = 0; i <N-1 ; i++) {
              arr[i][0]=1;
              arr[i][i]=1;
              for (int j = 1; j <N; j++) {
                  arr[i+1][j]=arr[i][j-1]+arr[i][j];
              }
          }//赋值过程
  int count=1;boolean flag=false;
          for (int i = 0; i < N; i++) {
              for (int j = 0; j <=i; j++) {
                  if(arr[i][j]==N-1){
                      //System.out.println(count);
                      flag=true;
                      break;
                  }
                  count++;
              }
              if(flag==true) break;
          }//搜索过程，只搜索下半部分
          System.out.println(count);
      }
      }
  

  不出所料，只拿了二十分。因为剩下的测试样例的N 太大，生成二维数组时内存超限了。。

• 思路2：参照CSDN上一位c++大佬的解法，做了一点笔记，并且自己用java写了一遍

  大佬的文章链接如下：

  https://blog.csdn.net/njuptACMcxk/article/details/116426985

思路：找规律（只看下半部分）

• 规律：设行下标为i，列下标为j

  • 对应的数字为
    $$C_i^j$$

  • 矩阵的每一行和每一列，都是递增的，而对角线上的数，恰是矩阵中每一列的首个数字，对称轴上的数可表示为
    $$C_{2j}^j$$

    • 当j>16时，$C_{2j}^j$>10^9。所以可以将循环范围缩减至16
    • “递增”——>已排序，便于查找——>二分法查找第j列上>=N的数——>从大到小找效率更高（N可以很大）
    • 找到了数，它是第几个数？——>个数求和。

    ? 如目标数字在第i行，第j列，前i-1行的数有
    $$\frac{i(i+1)}{2}$$

个，j从0起算，所以总数要在这个基础上加j+1,结果为
$$\frac{i(i+1)}{2}+j+1$$

• 题解：

  import java.math.BigInteger;
  import java.util.Scanner;
  
  public class Main {
      static long N;
  
      public static void main(String[] args) {
          Scanner s = new Scanner(System.in);
          N = s.nextInt();
          for (int i = 16; ; i--) {
              if(hasFind(i)) break;
          }
      }
  
      public static boolean hasFind(int j) {
          long l = 2 * j, r = Math.max(l, N);
  //二分法
          while (l < r) {
              long mid = l + r >> 1;//右移一位，相当于除以2取整
              if (C(mid, j) >= N) r = mid;
              else l = mid + 1;
          }
          if (C(r, j) != N) return false;
  
          else System.out.println(r * (r + 1) / 2 + j + 1);
          return true;
      }
  
      public static long C(long a, long b) {//求解Cmn
          long c = 1;
          for (long i = a, j = 1; j <= b; i--, j++) {
              c = c * i / j;
              if (c > N) return c;
          }
          return c;
      }
  }
  

• 心得体悟：程序员学好数据结构与算法真的是很必要的；掌握多种解决方法也是很必要的。因为数据量小的时候怎么舒服怎么来，但是数据量一大就是考验功底的时候了。暴力只能解决极小部分问题。

时间显示

• 这题的原型可归为：类型10：打印输出找规律 中的类题1

  package pra;
  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner s = new Scanner(System.in);
          int n=s.nextInt();
          System.out.print((n/60-n/60%60)/60);//h
          System.out.print(":");
          System.out.print(n/60%60);//m
          System.out.print(":");
          System.out.print(n%60);//s
      }
  }
  

  那题的题解如上。

  注意这题有两处不同，一是数据范围。 二是输出格式：有前置0。

• 解题过程：（注：过程嘛，说明前几步都是错的，赶时间的小伙伴建议直接下拉至最后一步）

  • 在这题扩大了数据范围的情况下，我发现我之前的代码通用性不强，初步猜测是只适用于24 * 60 *60 的评测数据，因为在仅仅把数据类型由int换为long之后，我发现输入46800999，输出为13000:16:39，但答案是13:00:00……。

  • 后面我在输出之前加了一行语句，希望把时间减到一天之内

        n%=(24*60*60);
    

    但发现还是不对劲。输入46800999，输出了16:16:39。

  • 于是我又看了看题目，发现自己漏了一个关键信息**:给定的输入是毫秒**。（认真读题！不能心急！）

    这就简单了，在上面那条语句之前再加上一句：

    n/=1000;
    

  • 另外，对于时的计算，其实还有更简便的写法：

    n/3600
    

    写基础题的时候没想起来，写了长长的一串……

  • 最终通过评测的代码如下：

    import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            long n=s.nextLong();
            n/=1000;
            n%=(24*60*60);
            System.out.printf("%02d",n/3600);//h
            System.out.print(":");
            System.out.printf("%02d",n/60%60);//m
            System.out.print(":");
            System.out.printf("%02d",n%60);//s
        }
    }
    

双向排序

• 题目：

• 题解：不用测都知道以下写法最多只能过60%的测试样例，因为new Integer[len]里的len数据类型只能是int，不能是long；对数组进行切割排序的时候也有这个问题。输入数据最大可达10万，直接溢出。

  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner s = new Scanner(System.in);
          int len = s.nextInt();//序列长度
          Integer[] arr = new Integer[len];
          for (int i = 0; i < len; i++) {
              arr[i] = i + 1;
          }
          long count = s.nextInt();//操作次数
          for (long i = 1; i <= count; i++) {
              int flag = s.nextInt();//0 对0到edge-1号元素降序;1 对edge到len-1号元素升序
              int edge = s.nextInt();//
              if (flag == 0) {
                  Integer[] tmp = new Integer[edge];
                  System.arraycopy(arr, 0, tmp, 0, edge);
                  Arrays.sort(tmp, Collections.reverseOrder());
                  System.arraycopy(tmp, 0, arr, 0, edge);
              }
              if (flag == 1) {
                  //Arrays.sort(arr);
                  Integer[] tmp = new Integer[len - edge + 1];
                  System.arraycopy(arr, edge - 1, tmp, 0, len - edge + 1);
                  Arrays.sort(tmp);
                  System.arraycopy(tmp, 0, arr, edge - 1, len - edge + 1);
              }
  
          }
          for (int i = 0; i < len; i++) {
              System.out.print(arr[i] + " ");
          }
      }
  }
  

害，在网上找到了很多c++的题解，思路看懂了一些，之后有机会再补充？感觉有些数据结构没法和java的对应上，我也不知道能用什么代替……我承认我这算法学习还停留在了浅层阶段，被具体语言限制……

特别数的和

• 题目：小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到
  　　40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。请问，在 1 到 n 中，所有这样的数的和是多少？

• 题解：

  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
   Scanner s=new Scanner(System.in);
   String n=s.next();
  int N=Integer.valueOf(n);
   int sum=0;
          for (int i = 0; i <=N ; i++) {
              String tmp=String.valueOf(i);
              for (int j = 0; j < tmp.length(); j++) {
                  if((tmp.charAt(j)=='2'||tmp.charAt(j)=='9'||tmp.charAt(j)=='1'||tmp.charAt(j)=='0')&&(tmp.charAt(0)!='0')){
                      sum+=i;
                      break;
                  }
              }
          }
          System.out.println(sum);
      }
  }
  

  其实这里面以字符串形式读入再转换成整数是画蛇添足了。不过一开始这样转换还因为我在循环里面也在用这个n，结果输出结果不对劲。现在保留这段多余代码也算是给自己提个醒

  。

等差数列

• 题目：

  问题描述

  数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
  　　现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

  输入格式

  输入的第一行包含一个整数 N。
  　　第二行包含 N 个整数 A?, A?, · · · , AN。(注意 A? ～ AN 并不一定是按等差数列中的顺序给出)

• 题解：

  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
   Scanner s=new Scanner(System.in);
  int N=s.nextInt();
          ArrayList<Integer> arr=new ArrayList<>();
          for (int i = 0; i < N; i++) {
             arr.add(s.nextInt());
          }
          Collections.sort(arr);
          int odd=arr.get(1)-arr.get(0);
          for (int i = 1; i < N-1; i++) {
              if((arr.get(i+1)-arr.get(i))<=odd){
                  odd=arr.get(i+1)-arr.get(i);
              }
          }
          int max=arr.get(N-1);int min=arr.get(0);
          //special situation
          if(odd==0) System.out.println(N);
          else System.out.println((max-min)/odd+1);
      }
  }
  

• 注意：

  • N才十万，不是很大，存进数组然后暴力循环遍历就能通过全部测试样例

  • 给定数据不按顺序，要排序

  • 用等差数列的公式：
    $$an=a1+(n?1)d$$

  • 差为0的很特殊，另外输出