2018-11-11 算法练习题
2018-11-11 本文已影响0人
大妈_b059
下面是几道算法练习题：
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<String, String> map = new HashMap<String, String>();
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<String> list = new ArrayList<String>();
List<String> list2 = new ArrayList<String>();
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();
}
}
