From The OJ of ECNU

• From The OJ of ECNU

  1. No3532热河路，找1101001000.....数字规律

     找1101001000.....数字规律
     输入元素位置返回是0还是1
     找规律
     每两个1之间各的1的数量为等差数列
     0个1,1个1，2个1,3个1，依次递增
     因此
     每个 1 的位置是固定的，它们出现在序号 1, 2, 4, 7, 11, 16, ...。
     
     这些 1 的位置满足以下规律：
     
     第 1 个 1 在序号 1。
     
     第 2 个 1 在序号 2。
     
     第 3 个 1 在序号 4（1 + 2 + 1）。
     
     第 4 个 1 在序号 7（1 + 2 + 3 + 1）。
     
     第 5 个 1 在序号 11（1 + 2 + 3 + 4 + 1）。
     
     以此类推。
     
     换句话说，第 k 个 1 的位置是：1 + 2 + 3 + ... + k + 1 = k*(k + 1)/2 + 1
     
     因为第 k 个 1 的位置是 k*(k + 1)/2 + 1。
     
     我们需要找到 k，使得 k*(k + 1)/2 + 1 是小于或等于 n 的最大值。
     
     因此，我们将条件写成 k*(k + 1)/2 < n - 1，以确保我们找到的 k 是满足条件的最大值。
     
     public class SequencePattern {
         public static void main(String[] args) {
             int n = 10; // 你可以根据需要改变n的值
             System.out.println(getNumber(n));
         }
     
         public static int getNumber(int n) {
             if (n == 1) {
                 return 1;
             }
             int k = 1;
             while (k * (k + 1) / 2 < n - 1) {
                 k++;
             }
             if (n == (k * (k + 1) / 2) + 1) {
                 return 1;
             } else {
                 return 0;
             }
         }
     }
     

     重点逻辑：

     找11010010001……字符串的规律，重点是1的位置

     第 1 个 1 在序号 1。 第 2 个 1 在序号 2。 第 3 个 1 在序号 4（1 + 2 + 1）。 第 4 个 1 在序号 7（1 + 2 + 3 + 1）。 第 5 个 1 在序号 11（1 + 2 + 3 + 4 + 1）。

     使用求和公式来计算1的序号

  2. No3531定西

     package com.wpf.algorithm.ecnu.oj;
     
     import java.util.Arrays;
     import java.util.Scanner;
     
     /**
      * @author wpf
      * @project JavaTec
      * @title No3531定西
      * @description
      * 一个人走走了很多年，发现自己走到了一个很长的，年久失修的楼梯面前。年久失修的意思就是，有k个台阶坏了，没法走。
      *
      * 楼梯一共有  层，你一次能上一阶、两阶或三阶台阶，请问，你从楼梯底部 (0开始) 走到楼梯顶部，共有多少种走法。
      *
      * 输入格式
      * 输入数据共两行，第一行包含两个自然数n(1<n<100)和k(0<k<n),第二行包含k个自然数 Xi(
      * 1<Xi<n)，数字之间用一个空格隔开,表示损坏的台阶的序号(从楼梯底部到楼梯顶部，台阶序号依次为1到
      * n ) *
      * 输出格式
      * 输出数据仅包含一个整数，表示所有可行走法的总数。
      * 样例
      * input
      * 5 2
      * 2 4
      * output
      * 2
      * @date 2025.02.16 18:10:34
      */
     public class No3531定西 {
     
         public static void main(String[] args) {
     
             Scanner sc = new Scanner(System.in);
             int n = sc.nextInt();
             int[] stairs = new int[n + 1];
             int[] floorsWay = new int[n + 1];
     
             for (int i = 0; i < stairs.length; i++) {
                 stairs[i] = 1;
             }
     //        System.out.println(Arrays.toString(stairs));
     
             int k = sc.nextInt();
             sc.nextLine();
     //        int[] xi = new int[k];
     //
     //        for (int i = 0; i < xi.length; i++) {
     //            xi[i] = sc.nextInt();
     //            sc.nextLine();
     //        }
     
             for (int i = 0; i < k; i++) {
                 int floor = sc.nextInt();
                 stairs[floor] = 0;
             }
     
     //        int floor = 0;
     //        while (floor < stairs.length) {
     //
     //        }
     
             floorsWay[0] = 1;
             for (int i = 1; i < floorsWay.length; i++) {
                 if (stairs[i] == 0) {
                     floorsWay[i] = 0;
                 } else {
                     floorsWay[i] = floorsWay[i - 1];
                     if (i >= 2) {
                         floorsWay[i] += floorsWay[i - 2];
                     }
                     if (i >= 3) {
                         floorsWay[i] += floorsWay[i - 3];
                     }
                 }
             }
     
             System.out.println(floorsWay[n]);
     
         }
     
     }
     
     

     重点逻辑：

     动态规划思路

     第n级台阶的方式数量是由前1级，前2级，前3级…的方式数量决定的

     因此递推公式为：way(n) = way(n-1) + way(n-2) + way(n-3)，当第k级阶梯损坏是，对应的方式数量为0

  3. No3530和你在一起 - 计算排列的所有可能情况

  package com.wpf.algorithm.ecnu.oj;
  
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Scanner;
  
  /**
   * @author wpf
   * @project JavaTec
   * @title 和你在一起
   * @description
   * 这么n个数字，联成一排拼到一起便是我爱你的时间，那么我们会在一起多久呢
   *
   * 例如: n=3时，3 个整数 13，312，343 联接成的最长时间为: 34331213。
   * 又如: n=4时，4 个整数 7，13，4，246 联接成的最长时间为: 7424613。
   *
   * 输入格式
   * n (1< n< 20),表示几个数。
   * 接下来一行n个正整数，大小不超过10^4。
   *
   * 输出格式
   * 拼成的最长时间。
   *
   * 样例
   * input
   * 3
   * 623 583 413
   * output
   * 623583413
   *
   * @date 2025.02.17 10:38:55
   */
  public class No3530和你在一起 {
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int num = sc.nextInt();
          sc.nextLine();
  
          int[] nums = new int[num];
          for (int i = 0; i < num; i++) {
              nums[i] = sc.nextInt();
          }
  
          //先对所有数字进行排列组合
          List<String> permutationList = getPermutation(nums);
  
          //对比所有排列组合数组
          String max = "";
          for (String str : permutationList) {
              if (str.compareTo(max) > 0) {
                  max = str;
              }
          }
  
          System.out.println(max);
      }
  
      /**
       * 递归调用获取数组的排列组合后拼接成的字符串List
       * @param nums
       * @return
       */
      private static List<String> getPermutation(int[] nums) {
          List<String> permutationList = new ArrayList<>();
          int start = 0;
          permute(nums, start, permutationList);
          return permutationList;
      }
  
      /**
       * 生成nums数组的排列组合，并将配列组合结果链接起来返回list集合
       * @param nums
       * @param start
       * @param permutationList
       */
      private static void permute(int[] nums, int start, List<String> permutationList) {
          //递归终止条件
          if (start == nums.length - 1) {
              String permutation = "";
              for (int i = 0; i < nums.length; i++) {
                  permutation = permutation + nums[i];
              }
              permutationList.add(permutation);
              return;
          }
  
          for (int index = 0; index < nums.length; index++) {
              swapElement(nums, start, index); //交换元素
              permute(nums, start + 1, permutationList);
              swapElement(nums, start, index); //回溯元素
          }
      }
  
      /**
       * 交换数组中j与k元素的位置
       * @param nums
       * @param j
       * @param k
       */
      private static void swapElement(int[] nums, int j, int k) {
          int temp = nums[j];
          nums[j] = nums[k];
          nums[k] = temp;
      }
  
  }
  
  

  重点逻辑：

  递归生成数组的各种组合拼接的字符串，先交换元素，从某个节点开始向后递归调用，再回溯到原位置。

  4.No3529梵高先生 - 绘制杨辉三角 - 计算组合数

  package com.wpf.algorithm.ecnu.oj;
  
  import java.util.Scanner;
  
  /**
   * @author wpf
   * @project JavaTec
   * @title No3529梵高先生(打印杨辉三角)
   * @description
   * 1
   * 1 1
   * 1 2 1
   * 1 3 3 1
   * 1 4 6 4 1
   * ...
   * 现在给你一个正整数n，请你给出星空的前n行。
   *
   * 输入格式
   * 输入文件共一行，包含一个正整数n(1≤n≤20)。
   *
   * 输出格式
   * 输出文件共n行，即星空的前n行。每行包含若干正整数，这些正整数之间用一个空格隔开（不能有多余的空格），最后一个正整数后面没有空格。
   *
   * 样例7
   * input
   * 4
   * output
   * 1
   * 1 1
   * 1 2 1
   * 1 3 3 1
   * @date 2025.02.17 16:52:09
   */
  public class No3529梵高先生 {
  
      public static void main(String[] args) {
  
          Scanner sc = new Scanner(System.in);
  
          int lineNum = sc.nextInt();
  
          for (int i = 0; i < lineNum; i++) {
              for (int j = 0; j <= i; j++) {
                  int combinationResult = calculateCombinationByDynamicProgram(i, j);
                  if (j == i) {
                      System.out.print(combinationResult);
                  } else {
                      System.out.print(combinationResult + " ");
                  }
              }
              System.out.println();
          }
  
      }
  
  //    public static void main(String[] args) {
  //        System.out.println(calculateCombination(3,1));
  //    }
  
      /**
       * 计算组合数
       * @param n 从n个数字中
       * @param k 取出k个数字
       * @return
       */
      private static int calculateCombination(int n, int k) {
  
          //递归结束条件
          if (k == 0 || n == k) {
  //            System.out.println("k = " + k);
  //            System.out.println("n = " + n);
              return 1;
          }
  
          /**
           * 递归调用
           *  C(n, k) = C(n-1, k-1) + C(n-1, k)C(n,k)=C(n−1,k−1)+C(n−1,k)
           *  递推公式的核心思想是：将问题分为两种情况：
           *
           * 包含某个特定元素：
           *
           * 假设我们从 n 个元素中选取 k 个元素，并且包含第 n 个元素。
           *
           * 如果第 n 个元素被选中，那么剩下的 k−1 个元素需要从剩下的 n−1 个元素中选取。
           *
           * 这种情况的组合数是 C(n-1, k-1)C(n−1,k−1)。
           *
           * 不包含某个特定元素：
           *
           * 如果第 n 个元素 不被选中，那么我们需要从剩下的 n-1 个元素中选取全部的 k 个元素。
           *
           * 这种情况的组合数是 C(n-1, k)C(n−1,k)。
           *
           * 将这两种情况相加，就得到了总的组合数：
           *
           *
           * 例如：C(4,2)=C(3,1)+C(3,2)
           */
          return calculateCombination(n-1, k) + calculateCombination(n-1, k-1);
      }
  
      /**
       * 通过动态规划的方式计算组合数，可以省去重复计算的时间
       * @param n
       * @param k
       * @return
       */
      public static int calculateCombinationByDynamicProgram(int n, int k) {
          int[][] dp = new int[n + 1][k + 1];
  
          for (int i = 0; i <= n; i++) {
              for (int j = 0; j <= Math.min(i, k); j++) {
                  if (j == 0 || j == i) {
                      dp[i][j] = 1; // 基本情况
                  } else {
                      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 递推公式
                  }
              }
          }
  
          return dp[n][k];
      }
  
  }
  
  

  重点逻辑：

  计算n项式的系数，即C(n,k)的组合数

  1. 用递归方式：从n项中取k项的组合数等于从n-1项中区k项和从n-1项中取出k-1项的和(即第n项有没有被取出) 而从n项中取出0项或从n项中取出n项的组合数都是1
  2. 用动态规划的方式：主要思想类似，但是能在n和k较大时节省运算时间

  扩展

  计算A(n,k)的排列数

  1. 直接使用阶乘公式

     public class Permutation {
         public static void main(String[] args) {
             int n = 5;
             int k = 3;
             System.out.println("A(" + n + ", " + k + ") = " + calculatePermutation(n, k));
         }
     
         // 计算排列数 A(n, k)
         public static int calculatePermutation(int n, int k) {
             if (k > n) {
                 return 0; // 如果 k > n，排列数为 0
             }
             return factorial(n) / factorial(n - k);
         }
     
         // 计算阶乘
         public static int factorial(int num) {
             if (num == 0 || num == 1) {
                 return 1;
             }
             int result = 1;
             for (int i = 2; i <= num; i++) {
                 result *= i;
             }
             return result;
         }
     }
     

     代码说明：

     1. factorial 方法：
        • 计算一个数的阶乘。
        • 使用循环实现，避免递归导致的栈溢出。
     2. calculatePermutation 方法：
        • 检查 kk 是否大于 nn，如果是，返回 0（因为无法从 nn 个元素中选取 kk 个元素进行排列）。
        • 否则，计算 A(n, k) = \frac{n!}{(n - k)!}A(n,k)=(n−k)!n!。

  2. 递推计算排列数

     排列数 A(n, k)也可以通过递推公式计算： $A(n, k) = n \times (n-1) \times (n-2) \times \dots \times (n - k + 1)$

     public class Permutation {
         public static void main(String[] args) {
             int n = 5;
             int k = 3;
             System.out.println("A(" + n + ", " + k + ") = " + calculatePermutation(n, k));
         }
     
         // 计算排列数 A(n, k)
         public static int calculatePermutation(int n, int k) {
             if (k > n) {
                 return 0; // 如果 k > n，排列数为 0
             }
             int result = 1;
             for (int i = 0; i < k; i++) {
                 result *= (n - i);
             }
             return result;
         }
     }
     

     代码说明：

     1. 递推计算：
        • 使用循环从 nn 开始，依次乘以 n-1n−1, n-2n−2, ..., 直到 n - k + 1n−k+1。
        • 例如，A(5, 3) = 5 \times 4 \times 3 = 60A(5,3)=5×4×3=60。
     2. 优点：
        • 避免了计算完整的阶乘，减少了计算量。
        • 适用于较大的 nn 和 kk。