2018-11-11 算法练习题

下面是几道算法练习题:

package java算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
 * 
 * @author 刘慧丽
 * 
 * 几道算法题
 *
 */

public class Test2 {

    private static Scanner input = new Scanner(System.in);

    /**
     * 每个PAT考生在参加考试时都会被分配两个座位号,一个是试机座位,一个是考试座位。正常情况下,考生在入场时先得到试机座位号码,入座进入试机状态后,
     * 系统会显示该考生的考试座位号码,考试时考生需要换到考试座位就座。
     * 但有些考生迟到了,试机已经结束,他们只能拿着领到的试机座位号码求助于你,从后台查出他们的考试座位号码。
     * 
     * 输入格式:
     * 
     * 输入第一行给出一个正整数N(<=1000),随后N行,每行给出一个考生的信息:“准考证号 试机座位号 考试座位号”。
     * 其中准考证号由14位数字组成,座位从1到N编号。输入保证每个人的准考证号都不同,并且任何时候都不会把两个人分配到同一个座位上。
     * 
     * 考生信息之后,给出一个正整数M(<=N),随后一行中给出M个待查询的试机座位号码,以空格分隔。
     * 
     * 输出格式:
     * 
     * 对应每个需要查询的试机座位号码,在一行中输出对应考生的准考证号和考试座位号码,中间用1个空格分隔。
     * 
     * 输入样例: 4 10120150912233 2 4 10120150912119 4 1 10120150912126 1 3
     * 10120150912002 3 2 2 3 4 输出样例: 10120150912002 2 10120150912119 1
     */
    public static void Test01() {
        int n = Integer.parseInt(input.nextLine());
        Map map = new HashMap();
        for (int i = 0; i < n; i++) {
            String str = input.nextLine();

            String[] s = str.split(" ");
            map.put(s[1], s[0] + " " + s[2]);
        }
        int m = Integer.parseInt(input.nextLine());
        int[] arr = new int[m];
        for (int i = 0; i < m; i++) {
            arr[i] = input.nextInt();
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(map.get(String.valueOf(arr[i])));
        }

    }

    /**
     * 输入样例: This is a simple TEST. There ARE numbers and other symbols
     * 1&2&3........... 输出样例: e 7
     */
    public static void Test02() {
        String str = input.nextLine().toLowerCase();
        int[] arr = new int[123];
        int max = 0;
        int min = 123;
        for (int i = 0; i < str.length(); i++) {
            if (((int) str.charAt(i) > 96 && (int) str.charAt(i) < 123)) {
                arr[str.charAt(i)]++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                min = i;
            }
        }
        System.out.println((char) min + " " + max);

    }

    /**
     * 给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序,按“PATestPATest....”这样的顺序输出,
     * 并忽略其它字符。当然,六种字符的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按PATest的顺序打印,直到所有字符都被输出。
     * 
     * 输入格式:
     * 
     * 输入在一行中给出一个长度不超过10000的、仅由英文字母构成的非空字符串。
     * 
     * 输出格式:
     * 
     * 在一行中按题目要求输出排序后的字符串。题目保证输出非空。
     * 
     * 输入样例: redlesPayBestPATTopTeePHPereatitAPPT 输出样例: PATestPATestPTetPTePePee
     */

    public static void Test03() {
        String str = input.nextLine();
        char[] ch = { 'P', 'A', 'T', 'e', 's', 't' };
        int[] value = new int[123];
        for (int i = 0; i < str.length(); i++) {
            if (ch[0] == str.charAt(i)) {
                value[ch[0]]++;
            } else if (ch[1] == str.charAt(i)) {
                value[ch[1]]++;
            } else if (ch[2] == str.charAt(i)) {
                value[ch[2]]++;
            } else if (ch[3] == str.charAt(i)) {
                value[ch[3]]++;
            } else if (ch[4] == str.charAt(i)) {
                value[ch[4]]++;
            } else if (ch[5] == str.charAt(i)) {
                value[ch[5]]++;
            } else {

            }
        }
        int count = 0;
        while (true) {
            for (int i = 0; i < 6; i++) {
                if (value[ch[i]] == 0) {
                    count++;
                } else {
                    System.out.print(ch[i]);
                    value[ch[i]]--;
                }

            }
            if (count == 6) {
                break;
            }
        }

    }

    /**
     * 本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充。
     * 要求矩阵的规模为m行n列,满足条件:m*n等于N;m>=n;且m-n取所有可能值中的最小值。
     * 
     * 输入格式:
     * 
     * 输入在第1行中给出一个正整数N,第2行给出N个待填充的正整数。所有数字不超过104,相邻数字以空格分隔。
     * 
     * 输出格式:
     * 
     * 输出螺旋矩阵。每行n个数字,共m行。相邻数字以1个空格分隔,行末不得有多余空格。
     * 
     * 输入样例: 12 37 76 20 98 76 42 53 95 60 81 58 93 ,94输出样例: 98 95 93 42 37 81
     * 53 20 76 58 60 76
     */
    public static void Test04() {
        int N = input.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = input.nextInt();
        }

        int n = (int) Math.sqrt(N);
        int m_v = 1;
        int n_v = 1;
        int min = n;
        for (int i = n; i > 1; i--) {
            if (N % i == 0) {
                if (N / i - i <= min && (N / i - i >= 0)) {
                    min = N / i - i;
                    n_v = i;
                    m_v = N / i;
                }
            }

        }
        Arrays.sort(arr);
        int i = 1, j = 0, k = 0, flag = 0, sign = 0;
        int[][] arry = new int[m_v][n_v];

        for (i = 1; i <= m_v * n_v;) {
            for (k = 0 + flag; k < n_v - flag; k++) {
                arry[j + sign][k] = arr[i - 1];
                i++;
            }
            for (j = 1 + flag; j < m_v - flag; j++) {
                arry[j][k - 1] = arr[i - 1];
                i++;
            }
            for (k = k - 2; k >= 0 + flag; k--) {
                arry[j - 1][k] = arr[i - 1];
                i++;
            }
            for (j = j - 2; j >= 1 + flag; j--) {
                arry[j][k + 1] = arr[i - 1];
                i++;
            }
            flag++;
            sign = 1;
        }
        for (i = 0; i < m_v; i++) {
            for (j = 0; j < n_v; j++)
                System.out.print(arry[i][j] + " ");
            System.out.println();
        }

    }

    /**
     * 
     * 英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力,还定义了一个“爱丁顿数”E,即满足有E天骑车超过E英里的最大整数E。
     * 据说爱丁顿自己的E等于87。
     * 
     * 现给定某人N天的骑车距离,请你算出对应的爱丁顿数E(<=N)。
     * 
     * 输入格式:
     * 
     * 输入第一行给出一个正整数N(<=105),即连续骑车的天数;第二行给出N个非负整数,代表每天的骑车距离。
     * 
     * 输出格式:
     * 
     * 在一行中给出N天的爱丁顿数。
     * 
     * 输入样例: 10 6 7 6 9 3 10 8 2 7 8 输出样例: 6
     */
    public static void Test05() {
        int n = input.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = input.nextInt();
        }
        Arrays.sort(arr);
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr.length - i) {
                if (arr.length - i > max) {
                    max = arr.length - i;
                }
            }
        }

        System.out.println(max);
    }

    /**
     * C语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩,颁奖规则也就制定得很滑稽:
     * 
     * 0. 冠军将赢得一份“神秘大奖”(比如很巨大的一本学生研究论文集……)。 1. 排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶! 2.
     * 其他人将得到巧克力。
     * 
     * 给定比赛的最终排名以及一系列参赛者的ID,你要给出这些参赛者应该获得的奖品。
     * 
     * 输入格式:
     * 
     * 输入第一行给出一个正整数N(<=10000),是参赛者人数。随后N行给出最终排名,每行按排名顺序给出一位参赛者的ID(4位数字组成)。
     * 接下来给出一个正整数K以及K个需要查询的ID。
     * 
     * 输出格式:
     * 
     * 对每个要查询的ID,在一行中输出“ID: 奖品”,其中奖品或者是“Mystery
     * Award”(神秘大奖)、或者是“Minion”(小黄人)、或者是“Chocolate”(巧克力)。如果所查ID根本不在排名里,打印“Are
     * you kidding?”(耍我呢?)。如果该ID已经查过了(即奖品已经领过了),打印“ID: Checked”(不能多吃多占)。
     * 
     * 输入样例: 6 1111 6666 8888 1234 5555 0001 6 8888 0001 1111 2222 8888 2222
     * 输出样例: 8888: Minion 0001: Chocolate 1111: Mystery Award 2222: Are you
     * kidding? 8888: Checked 2222: Are you kidding?
     * 
     */
    public static void Test06() {
        String[] str = { "Mystery Award", "Minion", "Chocolate", "Checked" };
        List list = new ArrayList();
        List list2 = new ArrayList();

        int N1 = input.nextInt();
        for (int i = 0; i < N1; i++) {
            list.add(input.nextLine());
        }
        int N2 = input.nextInt();
        for (int i = 0; i < N2; i++) {
            list2.add(input.nextLine());
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            if ((i + 1) == 1) {
                arr[i] = 0;
            } else if ((i + 1) % 2 != 0) {
                arr[i] = 2;
            } else {
                arr[i] = 1;
            }
        }
        for (int i = 0; i < list2.size(); i++) {
            if (list.contains(list2.get(i))) {
                int n = list.indexOf(list2.get(i));
                System.out.println(list2.get(i) + ":" + str[arr[n]]);
                arr[n] = 3;

            } else {
                System.out.println(list2.get(i) + ":" + " Are you kidding?");
            }
        }

    }

    public static void main(String[] args) {
        // Test01();
        // Test02();
        // Test03();
        Test04();
        // Test05();
        // Test06();

    }

}

你可能感兴趣的