[数据结构与算法]蓝桥杯校级预选赛题

蓝桥杯校级预选赛题

1.计算字符串周期问题

1.1 原题及实例

1.2 思路

? 这道题就是让算出一个字符串中某一个字符串循环的最小周期，那么可以使用String类型的一些方法，比如substring()方法，可以截取从第0个下标到后面index个长度的字符串，然后与i相邻位置后的字符串进行比较，如果相同则index就是最小周期。

? 比较重要的是要了解String类中substring(int startIndex,int endIndex)方法参数代表的意思

//解释String类中substring()方法的作用
public static void main(String[] args){
    String s="abcabc";
    //0指的是从下标为0开始，截取(2-0)个长度的字符串
    s.substring(0,2);
}

1.3 代码

import java.util.Scanner;

public class Main{
public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    String s=scanner.next();
    int i=calu(s);
    System.out.println(i);
}


public static int calu(String s){
    for(int i=1;i<=s.length();i++){
        //这个是从左到右依次取的字符串
        String s1=s.substring(0,i);
        //这个是在i之后相邻长度大小的字符串
        String s2=s.substring(i,i+s1.length());
        //如果两个字符串相同，那么这个i就是其最小周期
        if(s1.equals(s2)){
            return i;
        }
    }
    return 0;
}
}

2.判断无序数列中最近且大的数字

1.1 原题及实例

1.2 思路

? 这个题其实就是计算一个无序数列当中，从后到前，计算距离每一个数字最近且比其大的数字。

? 如果以上思想去思考这个问题，那么就可以使用插入排序的思想去解决这个问题

1.3 代码

import java.util.*;

public class Main{

public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    ArrayList<Integer> arrayList=new ArrayList<>();
    int num=scanner.nextInt();
    for(int i=0;i<num;i++){
        int j=scanner.nextInt(); 
        arrayList.add(j);
    }
    sort(num,arrayList);
}



/**
 * 计算距离学生最近(在这个学生之前)且身高较其大的学生
 * @param num
 * @param arrayList
 */
public static void sort(int num,ArrayList<Integer> arrayList){
    //这个集合用来存放需要输出的数据
    HashMap<Integer,Integer> hashMap=new HashMap<>();
    //从最后一个学生开始，一直遍历到第一个学生
    for (int i=num-1;i>=0;i--){
        //定义一个标志，对是否找到前面比其高的学生进行标记
        boolean flag=false;
        //ArrayList中存储的就是对应学生的身高
        //对其身高进行判断
        for (int j=i;j>=0;j--){
            //找到前面比这个学生高的那个学生
            if (arrayList.get(i)<arrayList.get(j)){
                //将第i个学生前面挡住的第j个学生记录在哈希表中
                hashMap.put(i+1,j+1);
                flag=true;
                break;
            }
        }
        //如果flag依然为false，那么说明前面没有任何一个学生挡住了他，那么就会看向黑板
        if (!flag){
            hashMap.put(i+1,0);
        }
    }
    //对数据进行循环输出
    for (int i=1;i<=num;i++){
        System.out.print(hashMap.get(i)+" ");
    }
}
}

3.判断字符串中的子字符串

3.1 原题及实例

3.2 思路

? 如果输入一段特点顺序的技能就会输，那么只需要判断一个字符串(即释放技能的顺序)当中是否有某一个字串(即输的技能顺序)即可，如果存在，那么输，如果不存在，那么赢。

3.3 代码

import java.util.*;

public class Main{

public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    //输入战斗次数
    int num=scanner.nextInt();
    //将每次战斗次数的技能释放顺序放到集合中
    ArrayList<String> arrayList=new ArrayList<>();
    //使战斗失败的技能顺序
    String s1="WZY";
    for(int i=0;i<num;i++){
        String s=scanner.next();
        arrayList.add(s);
    }
    int n=calu(num,s1,arrayList);
    System.out.print(n);
}

  /**
 * 判断技能的输赢
 * @param num 总共战斗的次数
 * @param s 使战斗输的技能顺序
 * @param arrayList 存每一次战斗的释放技能
 */
public static int calu(int num,String s,ArrayList<String> arrayList){
    //战斗胜利的次数,先和总场次一样，输一局减1
    int n=num;
    //对num次战斗的技能释放顺序进行遍历
    for (int i=0;i<num;i++){
        //第i+1次战斗所释放的技能顺序
        String s1=arrayList.get(i);
        //如果在一次战斗中释放技能的字符串中包含了输的技能顺序
        //即如果输了则进入这里面，并且给n减1
        if (s1.indexOf(s)!=-1){
            n--;
        }
    }
    return n;
}
}

4.给三个数字，判断是否可以组成直角三角形

4.1 原题及实例

4.2 思路

? 这个题灰常简单，判断三个数是否能够组成直角三角形使用勾股定理即可，但是如何输入这些数字还是需要思考一丢丢的。每一行固定输入三个数，那么可以用一个整型数组来存，这类数是需要存num个的组的，所以使用ArrayList集合来存。

4.3 代码

import java.util.*;

public class Main{
public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    int num=scanner.nextInt();
    ArrayList<int[]> arrayList=new ArrayList<>();
    for(int i=0;i<num;i++){
        int[] ints=new int[3];
        ints[0]=scanner.nextInt();
        ints[1]=scanner.nextInt();
        ints[2]=scanner.nextInt();
        arrayList.add(ints);
    }
    calu(num,arrayList);
}




/**
 * 计算三个数字是否能够组成三角形
 * @param num num组数
 * @param arrayList 存放每组数
 */
public static void calu(int num,ArrayList<int[]> arrayList){
    //用来存放每组数的答案
    ArrayList<String> arrayList1=new ArrayList<>();
    //对每组数进行遍历
    for (int i=0;i<num;i++){
        //作为能够组成三角形的标志
        boolean flag=false;
        //第一次输入的三个数
        int[] ints = arrayList.get(i);
        //对这个数组进行排序
        Arrays.sort(ints);
        //能够组成直角三角形的规则：
        //勾股定理:a^2+b^2=c^2
        if (Math.pow(ints[0],2)+Math.pow(ints[1],2)==Math.pow(ints[2],2)){
            flag=true;
        }
        if (flag){
            arrayList1.add("Yes");
        }else {
            arrayList1.add("No");
        }
    }
    for (int i=0;i<arrayList1.size();i++){
        System.out.println("Test"+(i+1)+":");
        System.out.println(arrayList1.get(i));
    }
}
}

5.计算不规则图形的周长

5.1 原题及实例

5.2 思路

? 从题中可以得出，栅栏的每一个边都是与x轴(或y轴)垂直，通过坐标画出图形如下：

? 根据上图，就可以得出思路，只需要计算出矩形的长和宽就可以计算出栅栏的总长度。矩形的长就是x_max-x_min，矩形的宽就是y_max-y_min。

【注意】：这个题并不难，但是如何满足题目要求从键盘输入，然后完成计算比较难，这个需要仔细思考一下。

5.3 代码

import java.util.*;

public class Main{

public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    //用来存放最终结果
    ArrayList<Integer> result=new ArrayList<>();
    //设置标志，以达到结束输入的目的
    boolean flag=true;
    //可以输入多个测试用例，那么就需要将num改为数组形式，接收多个
    ArrayList<Integer> arrayList1=new ArrayList<>();
    while(true){
        //用来存所有的横坐标和纵坐标,这个只能放在while里面，每一次循环重新定义一遍
        ArrayList<int[]> arrayList=new ArrayList<>();
        int num=scanner.nextInt();
        if(num==0){
            //flag=false;
            break;
        }
        //用来保存所有坐标的横坐标
        int[] ints_x=new int[num];
        //用来保存所有坐标的纵坐标
        int[] ints_y=new int[num];
        for(int i=0;i<num;i++){
            //将所有的横坐标存入ints_x
            ints_x[i]=scanner.nextInt();
            //将所有的纵坐标存入ints_y
            ints_y[i]=scanner.nextInt();
        }
        arrayList.add(ints_x);
        arrayList.add(ints_y);
        int n=method(num,arrayList);
        result.add(n);
    }
    for(int j=0;j<result.size();j++){
        System.out.println("The length is "+result.get(j)+" L");
}
}


/**
 * 计算栅栏的总长度
 * @param num 栅栏立柱的总数
 * @param arrayList 分别存放立柱的横坐标和纵坐标
 */
public static int method(int num,ArrayList<int[]> arrayList){
    //矩形的长
    int length;
    //矩形的宽
    int width;
    //arrayList中第一个位置存放的数组中有所有的横坐标
    int[] ints_x=arrayList.get(0);
    //arraylist中第二个位置存放的数组中有所有的纵坐标
    int[] ints_y=arrayList.get(1);
    //分别将所有的横坐标和纵坐标排序，可以得出其最大值和最小值
    Arrays.sort(ints_x);
    Arrays.sort(ints_y);
    //计算矩形的长
    length=ints_x[num-1]-ints_x[0];
    //计算矩形的宽
    width=ints_y[num-1]-ints_y[0];
    return (length+width)*2;
}
}

6.判断字符串中的字符

6.1 原题及实例

6.2 思路

? 这道题实际非常简单，但是必须要注意一点，字符串中，从左到右，如果")“比”("多，那么这个式子也是错误的，所以判断错误的条件有三个：

• 从左到右，如果")“比”("多，即错误
• 字符串中，压根没有"(“或”)"，直接错误
• 字符串中，"(“和”)"的数量不相等，即错误

6.3 代码

import java.util.*;

public class Main{

   public static void main(String[] args){
       Scanner scanner=new Scanner(System.in);
       while(scanner.hasNextLine()){
       String s=scanner.nextLine();
        System.out.println(method(s));
       }
   }
   /**
   * 判断字符串中"("和")"是否一致
   * s：字符串
   */
   public static String method(String s){
       if (s.equals("") || s==null){
           return "Wrong";
       }
       int num1=0;
       int num2=0;
       int k=0;
       int flag=0;
       for (int i=0;i<s.length();i++){
           if (s.charAt(i)=='('){
               k++;
               num1++;
               flag=1;
           }
           if (s.charAt(i)==')'){
               k--;
               num2++;
               flag=1;
           }
           //一定要注意这块，字符串中,")"在"("之前比"("多，那么也会错
           if(num2>num1){
               break;
           }
       }
       if(flag==0){
           return "Wrong";
       }
       if (num1==num2){
           return "Ok";
       }else {
           return "Wrong";
       }
   }
}

7.01背包问题

7.1 原题及实例

7.2 思路

? 这道题的原型就是NASA食物计划问题。这道题是一道多条件限制的01背包问题，和基础的01背包不同的是有两个条件限制，分别的最大体积和最大体重。

? 最后一道题有一个01背包问题，大家可以认识并理解一下01背包问题。

7.3 代码

import java.util.*;

public class Main{
public static void main(String[] args){
    Scanner scanner=new Scanner(System.in);
    //分别输入第一行的最大体积和最大质量
    int maxTJ=scanner.nextInt();
    int maxZL=scanner.nextInt();
    //输入食物总数
    int n=scanner.nextInt();
    //用来存储所有食物的体积
    int[] tj=new int[n];
    //用来存储所有食物的质量
    int[] zl=new int[n];
    //用来存储所有食物的卡路里
    int[] kll=new int[n];
    //dp数组
    int[][] dp=new int[maxTJ][maxZL];
    for(int i=0;i<n;i++){
        //体积
        tj[i]=scanner.nextInt();
        //质量
        zl[i]=scanner.nextInt();
        //卡路里
        kll[i]=scanner.nextInt();
    }
    int result=method(tj,zl,kll,maxTJ,maxZL,n);
    System.out.println(result);
}

/**
 * 多限制条件的01背包问题
 * @param tj 食物的体积
 * @param zl 食物的质量
 * @param kll 食物的卡路里
 * @param maxTJ 背包的最大体积
 * @param maxZL 背包的最大承受重量
 * @param n 食物总数
 */
public static int method(int[] tj,int[] zl,int[] kll,int maxTJ,int maxZL,int n){
    //如果没有装食物的话
    if (tj.length==0 || zl.length==0 || kll.length==0){
        return 0;
    }
    //dp数组,这个dp数组的长度只要比最大体积和最大质量大即可
    //因为这个只是长度，真正的数组范围是0-length-1
    int[][] dp=new int[maxTJ+1][maxZL+1];
    //前i个食物
    for (int i=0;i<n;i++){
        //体积,从后到前，由于java中数组默认全都是0，所以不用初始化
        for (int j=maxTJ;j>=tj[i];j--){
            //重量
            //这块的体积和重量都是从最大的往下遍历，并且最低范围是这个物体的体积和重量，所以不会出现物体体积、重量比背包大的问题
            for (int k=maxZL;k>=zl[i];k--){
                //对于体积为j，质量为k的背包来说，有两种情况
                //  1.不放第i个物品，那么其最大卡路里就是前一个物品的卡路里
                //  2.放第i个物品，那么其最大卡路里就是背包的体积、质量减去这个物品的体积、质量所能够承载的最大卡路里+这个物品的卡路里
                //综上，要取得最大卡路里，那就在这两种情况下取最大值
                dp[j][k]=Math.max(dp[j-1][k-1],dp[j-tj[i]][k-zl[i]]+kll[i]);
            }
        }
    }
    //返回背包体积、质量都为最大时候所能够得到的最大卡路里
    return dp[maxTJ][maxZL];
}
}

8.多个字符串的最长字串问题

8.1 原题及实例

8.2 思路

? 这个题实际就是求多个字符串的最长字串问题，最经常考的是两个字符串的最长字串问题，但思路其实都一样。

? 需要先将N个字符串中的最小字符串找到，然后使用两个for遍历出其所有的字串，然后在所有的字符串中进行contains()判断，如果都有，那么可以存入TreeMap中，这样就可以将所有的字串找到，存入到了TreeMap中，然后找到TreeMap中前几个长度递增的最后一个字串，即为答案。

【注意】：为什么要用TreeMap，题目中有要求，如果最长字串有多个，那么找到字典值最小的，而TreeMap刚好是根据字典值存入的。

【注意注意注意】：以下代码没有通过所有用例，但是由于太菜，揪了很多头发都没有找到问题所在，有发现问题的同学可以私信我，万分感谢！

8.3 代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        //int n=1;
        while(scanner.hasNext()){
        int n=scanner.nextInt();
            if(n==0){
                break;
            }
        ArrayList<String> arrayList=new ArrayList<>();
        for(int i=0;i<n;i++){
            String s=scanner.next();
            arrayList.add(s);
        }
        method(arrayList,n);   
        }
    }
    
  /**
     * 找到N个字符串中最长的字串
     * @param arrayList 存入所有的字符串
     * @param n N个字符串的"N"
     */
    public static void method(ArrayList<String> arrayList,int n) {
        //如果为空或字符串数量为0，直接返回
        if (arrayList == null || arrayList.size()==0) {
            return;
        }
        //满足题目要求，相同长度的字串按照字典值小的打印
        TreeSet<String> set = new TreeSet<>();
        //先使最小长度为第一个字符串，然后进行比较
        String minString = arrayList.get(0);
        //获取到长度最小字符串
        for (int i = 0; i < arrayList.size(); i++) {
            if (minString.length() > arrayList.get(i).length()) {
                minString = arrayList.get(i);
            }
        }

        //截取最小字符串
        for (int x = 0; x < minString.length(); x++) {
            //如果子串在所有的字符串中都有，那么就给result
            String result = null;
            for (int j = x + 1; j <= minString.length(); j++) {
                boolean flag=true;
                //获取子串
                String s = minString.substring(x, j);
                for (int k = 0; k < n; k++) {
                    //判断s字串是否在N个字符串中
                    boolean q = arrayList.get(k).contains(s);
                    //如果不存在，那么直接break，也不用运行其他的了
                    if (!q) {
                        flag=false;
                        break;
                    }
                }
                //如果flag一直为true，说明这个字串在N个字串中都存在
                if (flag){
                    result=s;
                }
            }
            if (result != null) {
                set.add(result);
            }
        }


        //遍历set
        String s1 = "";
        Iterator<String> it = set.iterator();
        if (set.size() == 0) {
            System.out.println("None");
            return;
        } else {
            while (it.hasNext()) {
                String a = it.next();
                //找到set集合前面长度增长的最后一个字串
                if (s1.length() < a.length()) {
                    s1 = a;
                } else {
                    break;
                }
            }
        }
        System.out.println(s1);

    }
}

9.经典01背包问题

9.1

9.1 详细描述

? 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为weight[i]，价值为value[i]，现在让你用这个背包装物品，最多能装的价值是多少？

? 现有W=10，N=4，物体重量和价值如下表：

9.2 思路

? 先提出一个dp二维数组，在容量为j的时候，存放第i个物体之前所能装载的最大价值，全程会围绕这个数组解释。

? 下面为dp二维数组，列(i)代表第i个物体，行(j)代表背包容量为j的时候，存入当背包容量为j的时候，第i个物体之前所能存入的最大价值。

? 下面以列为单位来看，即以背包容量为前提条件来看能够存入的物体价值：

? 当背包容量为1时，所有物体都无法装进，那么都其价值都为0

? 当背包容量为2时，当i=0，大于物体0的重量，并且此时是第一个物体，那么价值就是这个物体的价值，为1，后面的所有物品重量都比背包容量大，结束。

? 当背包容量为3时，当i=0，大于物体0的重量，并且此时是第一个物体，那么价值就是这个物体的价值，为1；当i=1，大于物体1的重量，那么就出现了装或不装这个物体两种情况，若不装，价值和i-1的价值相同，即dp[i] [j]=dp[i-1] [j]=1，若装，价值为背包容量减去第i个物体的重量所能拿到的价值+第i个物体的价值，即dp[i] [j]=dp[i-1] [j-weight[i]]+value[i]，然后比较这个两个值的大小取其最大值，后面的所有物品重量都比背包容量大，结束。

? 后面的每个容量背包都是这样的，遍历每个物体，当物体为第一个时且背包容量大于物体重量，那么其能够装的最大价值就是这个物体的价值；当物体为第二个时且背包容量大于物体重量，那么有两种选择，不装这个物体，价值为dp[i] [j]=dp[i-1] [j]；装这个物体，价值为dp[i] [j]=dp[i-1] [j-weight[i]]+value[i]，每个背包容量都是这样的，按照这样的情况填完下表为：

9.3 代码

/**
 * 01背包问题
 * @param weight 物体的重量
 * @param value 物体的价值
 * @param cap 背包最大容量
 * @return
 */
public static int test0(int[] weight,int[] value,int cap){
    int[][] dp=new int[100][cap+1];
    if (weight.length==0 || cap<=0){
        return 0;
    }
    //进行循环背包
    for (int j=1;j<cap+1;j++){
        //循环weight
        for (int i=0;i<weight.length;i++){
            //此时物体重量小于背包范围
            if (weight[i]<=j){
                //判断是否为第一个物理
                if (i==0){
                    //若是第一个物体，那么价值就直接是第一个物体的价值
                    dp[i][j]=weight[i];
                }else {
                    //若不是第一个物体，那么就要进行判断
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }else {
                //此时物体重量大于背包重量
                if (i==0){
                    //如果是第一个物体，那么为0
                    dp[i][j]=0;
                }else {
                    //如果不是第一个物体，那么其价值就是前一个的价值
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
    }
    //返回二维数组中最后一个数字，即为最大价值
    return dp[weight.length-1][cap];
}