[数据结构与算法]蓝桥杯java练习学习(2)

蓝桥杯练习

大部分程序来自查阅网络资源总结。

1.阶乘计算

package Chapter02;

import java.math.BigInteger;
import java.util.Scanner;

//阶乘计算
public class Demo01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        //BigInteger.valueOf();此方法接受单个参数值，该值是要创建的BigInteger的值。
        BigInteger n = BigInteger.valueOf(1);
        //BigInteger n = new BigInteger("1");
        for (int i = 1; i <=m; i++) {
            n = n.multiply(BigInteger.valueOf(i));//multiply为BigInteger的乘法函数。
        }
        System.out.println(n);
    }
}

2.高精度加法

package Chapter02;

import java.math.BigInteger;
import java.util.Scanner;

//高精度加法
public class Demo02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BigInteger a = scanner.nextBigInteger();
        BigInteger b = scanner.nextBigInteger();
        BigInteger c= a.add(b);
        System.out.println(c);

    }
}

3.Huffuman树

package Chapter02;

import java.util.Arrays;
import java.util.Scanner;

//Huffuman树
public class Demo03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        scanner.close();

        int sum = 0;
        for (int j = 0; j < n - 1; j++) {
            Arrays.sort(arr);//对指定T型数组按指定数值升序排序。
            arr[j] = arr[j]+arr[j+1];//最小的两个数相加。
            sum = sum+arr[j];
            //剩下的往前移一位。
            for (int i = j+2; i < n; i++) {
                arr[i-1] = arr[i];
            }
            arr[n-1] = 0;//另最后一位为零。
        }
        System.out.println(sum);
    }
}

4.报时助手

package Chapter02;

import java.util.Scanner;

//报时助手
public class Demo04 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int m = scanner.nextInt();
        //小于20的读数
        String[] time = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
        //大于20的整数读数
        String[] time2 = {" "," ","twenty","thirty","forty","fifty"};

        //小时
        if (h>20){
            int b = h%10;//得到个位数的数
            System.out.print("twenty"+" "+time[b]+" ");
        }else if (h==20){
            System.out.print("twenty"+" ");
        }else {
            System.out.print(time[h]+" ");
        }

        //分钟
        if (m>20){
            int a = m/10;//得到十分位的数
            int b = m%10;//得到个位数的数
            System.out.print(time2[a]+" "+time[b]);
        }else if (m==20){
            System.out.print("twenty");
        }else if (m>0 && m<20){
            System.out.print(time[m]);
        }else if (m==0){
            System.out.print("o'clock");//为0时候的读数
        }
    }
}

5.龟兔赛跑预测

package Chapter02;

import java.util.Scanner;

//龟兔赛跑预测
public class Demo05 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int v1 = scanner.nextInt();//兔子的速度
        int v2 = scanner.nextInt();//乌龟的速度
        int t = scanner.nextInt();//兔子领先路程
        int s = scanner.nextInt();//兔子领先休息的时间
        int l = scanner.nextInt();//赛道的长度
        scanner.close();

        int r1 = 0;//比赛结束兔子的路程
        int t1 = 0;//比赛结束兔乌龟的路程
        int time = 0;//比赛结束所用时间
        boolean flag = false;//设置一个标志位

        while (true){//做死循环表示比赛不间断进行
            time++;
            r1 +=v1;
            t1 +=v2;

            //判断是否到达终点
            if (r1>=l || t1>=l) {
                break;
            }

            //判断兔子是否该休息了
            if (r1-t1 >=t){
                //休息s秒
                for (int i = 0; i < s; i++) {
                    t1 +=v2;
                    time++;
                    //判断兔子休息的时候乌龟是否到达了终点
                    if (t1>=l){
                        flag=true;
                        break;
                    }
                }
                if (flag)
                    break;
            }
        }

        if (r1>t1) {
            System.out.println("R");
        }else if (r1<t1){
            System.out.println("T");
        }else {
            System.out.println("D");
        }
        System.out.println(time);
    }
}

6.芯片测试

package Chapter02;

import java.util.Scanner;

//芯片测试
/*
用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。
而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
已知好芯片比坏芯片多。所以用一个芯片测好芯片的时候1大于0,用一个芯片测坏芯片的时候0大于1。所以判断每列0的个数是否大于n的一半，是的就是坏芯片排除。
 */
public class Demo06 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] a = new int[n][n];
        int[] b = new int[n];//存储坏的芯片的个数。
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = scanner.nextInt();
                if (a[i][j]==0){   //判断是否为坏的
                    b[j] = b[j]+1;//统计每列0的个数。
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (b[i]<=n/2){   //判断坏的个数是否小于n的一半
                System.out.print(i+1+" ");
            }
        }
    }
}

7.FJ的字符串

package Chapter02;

import java.util.Scanner;

//FJ的字符串
//递归思想。
public class Demo07 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        System.out.println(FJstr(n));
    }

    public static String FJstr(int num){
        if (num==1){
            return "A";
        }
        return FJstr(num-1)+(char)('A'+(num-1))+FJstr(num-1);
    }
}

8.Sine之舞

package Chapter02;

import java.util.Scanner;

//Sine之舞
/*
Sn为递归。Sn=(Sn-1)An+[n-(n-1)]。n变小
An为递推。不太会，好好学习！。m变大
 */
public class Demo08 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(SN(n));
    }

    private static String SN(int n){
        if(n==1){
            return AN(1,1)+"+"+n;
        }
        else {
            return "("+SN(n-1)+")"+AN(1,n)+"+"+(n-(n-1));//n=(Sn-1)An+[n-(n-1)]
        }
    }

    private static String AN(int m,int n){
        if (m==n){
            return "sin("+n+")";
        }
        else {
            if (m%2!=0){
                return "sin("+m+"-"+AN(m+1,n)+")";
            }else {
                return "sin("+m+"+"+AN(m+1,n)+")";
            }
        }
    }
}

9.字符串对比

package Chapter02;

import java.util.Scanner;

//字符串对比
/*
equals:区分大小写比较；
equalsIgnoreCase：不区分大小写比较；
 */
public class Demo09 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();
        String str2 = scanner.next();

        if (str1.length() != str2.length()){
            System.out.println(1);
        }else {
            if (str1.equals(str2)){
                System.out.println(2);
            }else if (str1.equalsIgnoreCase(str2)){
                System.out.println(3);
            }else {
                System.out.println(4);
            }
        }

    }
}

10.数的读法

package Chapter02;

import java.util.Scanner;

//数的读法
/*
1。正常情况下：数字+单位；
2。0的情况；
3。1的情况。
 */
public class Demo10 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        scanner.close();

        String[] num = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
        String[] unit = {"","","shi","bai","qian","wan","shi","bai","qian","yi","shi"};

        int n = str.length();
        for (int i = 0; i < n; i++) {
            int x = str.charAt(i)-'0';
            //0的情况
            if (x==0){
                //在万和亿位上的0，只读出单位。
                if ((n-i)==5 || (n-i)==9){
                    System.out.print(String.format("%s ",unit[n-i]));
                }
                //1001或101的情况。
                if ((n-i)!=1 && str.charAt(i+1)!='0'){
                    System.out.print(String.format("%s ","ling"));
                }
            }
            //当数字为1时，并且1打头，而且在十亿、十万、十位上时才不读数字，只读单位。（读shi，不读yi shi）
            else if ((n==2 || n==6 || n==10) && x==1 && i==0) {
                System.out.print(String.format("%s ","shi"));
            }
            //其他情况下，读数字+单位。（ge不读）
            else {
                System.out.print(String.format("%s %s ",num[x],unit[n-i]));
            }
        }
    }
}

11.时间转换

package Chapter02;

import java.util.Scanner;

//时间转换
public class Demo11 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t =scanner.nextInt();
        int h = t/3600;
        int m = t%3600/60;
        int s = t%3600%60;
        System.out.println(h+":"+m+":"+s);
    }
}

12.矩形面积交

package Chapter02;

import java.util.Scanner;

//矩形面积交
/*
有三种情况：
1。两个矩形有一部分是相交的；
2。一个矩形包含着另一个矩形；
3。没有相交。
 */
public class Demo12 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //输入两个长方形左下和右上点的坐标。
        double x1 = scanner.nextDouble();
        double y1 = scanner.nextDouble();
        double x2 = scanner.nextDouble();
        double y2 = scanner.nextDouble();
        double x3 = scanner.nextDouble();
        double y3 = scanner.nextDouble();
        double x4 = scanner.nextDouble();
        double y4 = scanner.nextDouble();
        double width = 0,high = 0,sum = 0;
        //得到相交长方形的长和高。
        width = Math.min(Math.max(x1,x2),Math.max(x3,x4))-Math.max(Math.min(x1,x2),Math.min(x3,x4));
        high = Math.min(Math.max(y1,y2),Math.max(y3,y4))-Math.max(Math.min(y1,y2),Math.min(y3,y4));
        //相交三角形的面积。
        sum = width*high;
        //判断是否不相交。
        if (width<=0 || high<=0){
            System.out.println(String.format("%.2f",0.00));
        }else {
            System.out.println(String.format("%.2f",sum));
        }
    }
}

13.矩阵乘法

package Chapter02;

import java.util.Scanner;

//矩阵乘法
public class Demo13 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();   //n阶矩阵
        int m = scanner.nextInt();   //m次方
        int[][] arr = new int[n][n];
        int[][] arr2 = new int[n][n];
        int[][] arr3 = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr2[i][j]=arr[i][j] = scanner.nextInt();
                arr3[i][j] = 0;   //初始化结果矩阵。
            }
        }
        scanner.close();

        //若为0次方，则输出为一个单位矩阵。
        if (m==0){
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i==j){
                        System.out.print(1+" ");
                    }else {
                        System.out.print(0+" ");
                    }
                }
                System.out.println();
            }
        }
        else {
            //m次方，循环。
            for (int k = 1; k < m; k++) {

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        //计算结果矩阵对应位置的元素值。
                        int w = 0;
                        for (int l = 0; l < n; l++) {
                            w += arr[i][l]*arr2[l][j];
                        }
                        arr3[i][j] = w;
                    }
                }
                //把过渡矩阵的值传给矩阵。
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        arr[i][j] = arr3[i][j];
                    }
                }

            }
            //输出结果
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(arr[i][j]+" ");
                }
                System.out.println();
            }
        }

    }
}

14.回形取数

package Chapter02;

import java.util.Scanner;

//回形取数
public class Demo14 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] arr = new int[m][n];
        for (int i = 0; i <m ; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        scanner.close();

        int sum = 0;//输出的总数。
        int i=0,j=0;
        int[][] flag = new int[m][n];//设置一个标志位，标记已经输出的位置。

        while (sum<n*m){
            //向下遍历
            while (i<m && flag[i][j]!=1){
                System.out.print(arr[i][j]+" ");
                flag[i][j] = 1;//把已经输出的位置标记。避免重复输出。
                i++;sum++;
            }
            //上面循环里i多加了一次，所以i--；此时需要循环下一列，所以j++。
            i--;j++;
            //向右遍历
            while (j<n && flag[i][j]!=1){
                System.out.print(arr[i][j]+" ");
                flag[i][j] = 1;
                j++;sum++;
            }
            j--;i--;
            //向上遍历
            while (i>=0 && flag[i][j]!=1){
                System.out.print(arr[i][j]+" ");
                flag[i][j] = 1;
                i--;sum++;
            }
            i++;j--;
            //向左遍历
            while (j>=0 && flag[i][j]!=1){
                System.out.print(arr[i][j]+" ");
                flag[i][j] = 1;
                j--;sum++;
            }
            j++;i++;
        }

    }
}

15.完美的代价

package Chapter02;

import java.util.Scanner;

//完美的代价
//还没看懂
public class Demo15 {
        private static int count=0;
        private static boolean haveOnlyOneMiddle=true;

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            //输入长度为N的字符串
            int N = sc.nextInt();
            String s = sc.next();
            char[] charArr = s.toCharArray();//字符串转为字符数组
            if(palindrome(charArr,0,N-1)) {
                System.out.println(count);
            }
            else {
                System.out.println("Impossible");
            }
        }

        //判断是否满足回文
        private static boolean palindrome(char[] charArr, int a, int b) {
            // TODO 自动生成的方法存根
            if(a>=b) {//此时代表交换后满足了回文数
                return true;
            }
            //由后往前遍历 匹配首字符
            for(int i=b;i>a;i--) {
                if(charArr[a]==charArr[i]) {
                    exchangeTo(charArr,i,b);//匹配到了依次进行交换
                    count+=b-i;
                    return palindrome(charArr,a+1,b-1);//再重复判断接下来是否满足回文
                }
            }

            //判断此时的charArr[a]是否为中间字符，即该字符未匹配到其他字符
            if(haveOnlyOneMiddle) {
                haveOnlyOneMiddle=false;//有中间字符但仅能出现一个中间字符
                count+=charArr.length/2-a;//直接计算最后中间字符移至中间需要交换的次数
                return palindrome(charArr,a+1,b);//跳过中间字符，判断后面是否满足回文
            }
            return false;
        }

        //字符交换
        private static void exchangeTo(char[] charArr, int i, int b) {
            // TODO 自动生成的方法存根
            char temp;
            for(int k=i;k<b;k++) {
                temp=charArr[k];
                charArr[k]=charArr[k+1];
                charArr[k+1]=temp;
            }

        }

}

16.印章

package Chapter01;

import java.util.Scanner;

//印章

/**
 * 列表：买了m张印章，集齐了n种印章的概率。
 */
public class Demo01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//集齐n种印章.
        int m = scanner.nextInt();//买了m张印章.
        double p = 1.0/n;//每一次买到某一种的概率。
        double[][] arr = new double[m+1][n+1];//开辟(m+1)*(n+1)个空间。
        for (int i = 1; i <=m; i++) {
            for (int j = 1; j<=n ; j++) {
                if (i<j){   //购买的次数小于种类数时，概率为零。比如买一次不肯能买到2种。
                    arr[i][j] = 0;
                }else if (j==1){   //只要买了一次就会买到一种，买多次买到一种一定是重复的。
                    arr[i][j] = Math.pow(p,i-1);
                }else {   //其他情况下，考虑买到重复和没重复的情况。
                    arr[i][j] = arr[i-1][j]*(j*p)+arr[i-1][j-1]*((n-(j-1))*p);
                }
            }
        }
        System.out.println(String.format("%.4f",arr[m][n]));//注意题目要求保留四位小数。
    }
}

17.拿金币

package Chapter01;

import java.util.Scanner;

//拿金币

/**
 * dp公式：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+arr[i][j];
 */
public class Demo02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] arr = new int[n+1][n+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        scanner.close();

        int[][] dp = new int[n+1][n+1];
        dp[1][1] = arr[1][1];  //初始化第一个数。第一行和第一列默认为0。
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+arr[i][j];
            }
        }
        System.out.println(dp[n][n]);
    }
}

18.kAc给糖果你吃

package Chapter01;

import java.util.Arrays;
import java.util.Scanner;

//kAc给糖果你吃
public class Demo03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
        scanner.close();

        Arrays.sort(A);//从小到大排序。
        long sum = 0;
        //拿m次
        for (int i = n-1; i >n-1-m; i--) {
            sum += A[i];
        }
        System.out.println(sum);
    }
}

19.最大分解

package Chapter01;

import java.util.Scanner;

//最大分解
public class Demo04 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = 0;
        for (int i = n-1; i >0 ; i--) {
            if (n%i==0){
                sum += i;
                n=i;
            }
        }
        System.out.println(sum);
    }
}

20.藏匿的刺客

package Chapter01;

//藏匿的刺客
//这个题有bug，尚未解决。
import java.util.Arrays;
import java.util.Scanner;

/**
 * 这道题为贪心类型的区间选点问题。
 */
public class Demo05 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        person[] person = new person[n];
        for (int i = 0; i <n; i++) {
            person[i] = new person(scanner.nextInt(),scanner.nextInt(),1);
        }
        scanner.close();

        Arrays.sort(person);
        int max = person[n-1].N;
        int[] axis = new int[max+1];   //建一个标记数组，有敌人的话就标记在这个数组上。
        for (int i = 0; i < n; i++) {
            int s = person[i].M;   //开始的草丛。
            int t = person[i].N;   //结束的草丛。

            //优化
            /*boolean flag = true;
            for (int j = 0; j < n; j++) {
                if (person[j].M>s && person[j].N<t){
                    flag = false;break;
                }
            }
            if(flag=false) break;*/

            int count = sum(axis,s,t);   //查看这个区间内敌人的个数。
            person[i].c -= count;
            while (person[i].c>0){
                if (axis[t]==0){   //从区间终点开始选点
                    axis[t]=1;
                    person[i].c--;
                    t--;
                }else {
                    t--;
                }
            }

        }
        System.out.println(sum(axis,0,max));
    }


    //统计数轴axis上s-t已经有多少个点。
    private static int sum(int[] axis,int s,int t){
        int sum=0;
        for (int i = s; i <=t; i++) {
            sum +=axis[i];
        }
        return sum;
    }


    //新建一个士兵类，包含三个属性：开始的草丛和结束的草丛和敌人数。
    private static class person implements Comparable<person>{
        int M;
        int N;
        int c;

        public person(int m, int n,int c) {
            M = m;
            N = n;
            this.c = c;
        }

        @Override
        public int compareTo(person o) {
            int x = this.N-o.N;
            int y = this.M-o.M;
            return x!=0? x:y;
        }
    }
}