Problem A. 众数
题目描述
给定一个长度为N的非降数列，求数列中出现次数最多的数。如果答案不唯一，输出其中最小的数。
输入格式
输入数据第一行是一个整数T(1≤T≤100)，表示测试数据的组数。对于每组测试数据:
第一行是一个正整数N(1≤N≤100)，表示数列长度。
第二行有N个整数，整数之间用空格隔开，所有的整数都不超过105，表示这个数列。输出格式
对于每组测试数据，输出一个整数。
输入样例
2
4
1 1 1 2
5
1 1 2 2 3题目思路
- 用java里面的Map数据结构，统计每一个数字出现的次数。
- 然后对Map进行排序。
Map 排序
利用map的
entrySet()（返回键值对的set集合）将map转换成list，然后对list进行排序。List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(arrayMap.entrySet());AC代码
import java.io.IOException;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int arrayNum = scanner.nextInt();
for (int i = 0;i < arrayNum;i++){
//input
int num = scanner.nextInt();
List<Integer> array = new ArrayList<Integer>();
Map<Integer, Integer> arrayMap = new HashMap<Integer, Integer>();
for (int j = 0; j < num; j++){
int in = scanner.nextInt();
array.add(in);
if (arrayMap.containsKey(in)){
arrayMap.put(in,arrayMap.get(in)+1);
}else {
arrayMap.put(in,1);
}
}
//from small to big by number of appearance
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(arrayMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
if (o1.getValue() < o2.getValue()){
return 1;
}else if (o1.getValue() > o2.getValue()){
return -1;
}
else {
if (o1.getKey() > o2.getKey()){
return 1;
}else if (o1.getKey() < o2.getKey()){
return -1;
}else {
return 0;
}
}
}
});
System.out.println(list.get(0).getKey());
}
scanner.close();
}
}Problem B. 旋转图像
题目描述
在图形学中，我们经常需要对具体的图像进行一些处理。在这个问题中，你的任务是将一幅只包含01像素点的图片进行顺时针旋转。旋转的角度仅包含0度，90度，180度和270度。
输入格式
输入的第行是一个整数T (T≤50)，表示输入的数据组数。
每组测试数据的第一.行是两个整数N和M(1≤N,M≤50),表示图片的高度和宽度。
接下来N行，每行是一个长度为M的01串，表示图片的像素点。最后一行是一个整数angle,表示旋转的角度。输出格式
对于每组测试数据，输出旋转后得到的图片。请注意不要输出多余的空格或空行。
输入样例
2
2 3
111
000
90
3 3
111
101
111
180输出样例
01 01 01 111 101 111
思路解析
- 对字符串进行按位拆分，用到string.toCharArray() 拆分成字符数组。
- 对旋转90，180，270分别写一个函数。（不要忘记对旋转0时候要原封不对的输出）
可以自己写一个例子，比如
123 456 789
然后分别旋转90，180，270找规律，不难看出字符输出的规律。（就是换个方式输出原数组而已）
AC代码
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
private static List<char[]> imageRow = new ArrayList<char[]>();
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int arrayNum = scanner.nextInt();
for (int i = 0;i < arrayNum; i++){
int row = scanner.nextInt();
int column = scanner.nextInt();
imageRow.clear();
List<Integer> imageColumn = new ArrayList<Integer>();
for (int j = 0;j<row;j++){//input colum data
String number = scanner.next();
char[] columnArray = number.toCharArray();
imageRow.add(columnArray);
}
switch (scanner.nextInt()){
case 0:
for (int k = 0; k<row; k++){
for (int m = 0;m < column;m++){
System.out.print(imageRow.get(k)[m]);
}
System.out.println();
}
break;
case 90:
rotate90(row,column);
break;
case 180:
rotate180(row,column);
break;
case 270:
rotate270(row,column);
break;
}
}
}
private static void rotate90(int row,int column){
for (int j = 0; j<column;j++){
for (int i = row -1;i>=0; i--){
System.out.print(imageRow.get(i)[j]);
}
System.out.println();
}
}
private static void rotate180(int row,int column){
for (int i = row -1; i>=0;i--){
for (int j = column-1;j>=0;j-- ){
System.out.print(imageRow.get(i)[j]);
}
System.out.println();
}
}
private static void rotate270(int row,int column){
for (int j = column - 1; j>= 0 ;j--){
for (int i = 0 ;i < row; i++ ){
System.out.print(imageRow.get(i)[j]);
}
System.out.println();
}
}
}Problem C. 网络的核
题目描述
给定一个无向网络G,网络中共有N个节点(从1编号到N), M条边，求网络的核。
网络的核: 到网络中其他节点的距离之和最小的节点。且对于不连通的两点，它们之间的距离为N。
如果有多组解，输出编号最小的节点。输入格式
输入的第一行是一个整数T(T≤25)，表示输入的数据组数。
对于每组测试数据:第一行有两个整数N,M(1≤N≤50, 0≤M≤N*(N-1),表示网络中有N个点，M条边。
接下来M行，每行两个整数u,v(1≤u,v≤N, u≠v),表示点u和点v之间有一条距离为1的边。任意两个点之间最多只会有一条边相连。输出格式
对于每组测试数据，输出网络的核。
输入样例
2
3 3
1 2
1 3
2 3
4 2
1 2
2 3输出样例
1 2
思路解析
- 正确理解核。即图中的某个点到其他所有点距离之后最小的顶点。显然是最短路径。比较简单方法是弗洛伊德（把每个顶点i作为中间点，用三重循环，将 A[j,k] 距离 与 A[j,i] + A [i,k] 距离之和比较，并判断是否需要修改）
- 图数据结构的表示，简单的写法是二维矩阵表示（一般OJ题用顺序存储结构用时更少），或者用顶点链表，每个顶点后面跟着该顶点的边的集合。
AC代码
import java.io.IOException;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
Main core = new Main();
core.handle();
}
private void handle(){
Scanner scanner = new Scanner(System.in);
int arrayNum = scanner.nextInt();
for (int x =0 ;x < arrayNum;x++){
MGraph mGraph = new MGraph();
mGraph.setVertexNum(scanner.nextInt());
mGraph.setEdgeNum(scanner.nextInt());
for (int j = 0; j < mGraph.getEdgeNum(); j++){//input edges data
int vertex1 = scanner.nextInt();
int vertex2 = scanner.nextInt();
mGraph.edges[vertex1][vertex2] = 1;
mGraph.edges[vertex2][vertex1] = 1;
}
//use floyd to calculate A[]
mGraph.initA_array();
for (int k = 1;k<= mGraph.getVertexNum(); k++){// circle each vertex as an intermediate point
for (int l=1;l <= mGraph.getVertexNum();l++){
for (int m = 1;m <= mGraph.getVertexNum();m++){
if (mGraph.A[l][m] > mGraph.A[l][k] + mGraph.A[k][m]){
mGraph.A[l][m] = mGraph.A[l][k] + mGraph.A[m][k];
}
}
}
}
//
Map<Integer, Integer> arrayMap = new HashMap<Integer, Integer>();
for (int i = 1; i <= mGraph.getVertexNum();i++){
int distanceToOtherVertexes = 0;
for (int j = 1; j <= mGraph.getVertexNum();j++){
distanceToOtherVertexes += mGraph.A[i][j];
}
arrayMap.put(i,distanceToOtherVertexes);
}
//sort and print the vertex which has the shortest distance to other vertexes
List<Map.Entry<Integer,Integer>> sortList = new ArrayList<Map.Entry<Integer,Integer>>(arrayMap.entrySet());
Collections.sort(sortList, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
if (o2.getValue() < o1.getValue()){
return 1;
}else if (o2.getValue() > o1.getValue()){
return -1;
}else {
if (o2.getKey() <o1.getKey()){
return 1;
}else if (o2.getKey() > o1.getKey()){
return -1;
}else {
return 0;
}
}
}
});
System.out.println(sortList.get(0).getKey());
}
}
class MGraph{
int vertexNum;
int edgeNum;
int edges[][] = new int[51][51];
int A[][] = new int[51][51];//distance
public MGraph() {
for (int i = 0;i<51;i++){
for (int j = 0; j< 51;j++){
edges[i][j] = -1;//init edges array
}
}
}
public void initA_array(){
for (int i = 1;i<=this.getVertexNum();i++){
for (int j = 1;j<=this.getVertexNum();j++){
if (edges[i][j] == -1){//not have edges between the two vexes
A[i][j] = this.getVertexNum();
}else {
A[i][j] = edges[i][j];//because not have weight of edges,so it is a fixed value 1
}
}
}
}
public int getVertexNum() {
return vertexNum;
}
public void setVertexNum(int vertexNum) {
this.vertexNum = vertexNum;
}
public int getEdgeNum() {
return edgeNum;
}
public void setEdgeNum(int edgeNum) {
this.edgeNum = edgeNum;
}
public int[][] getEdges() {
return edges;
}
public void setEdges(int[][] edges) {
this.edges = edges;
}
}
}Problem D. Python List
题目描述
)
在Python中，List (列表)是一种非常重要的数据结构。它与C/C++/Java中的数组有些类似，但支持添加新元素时的动态扩展。在这个问题中，你需要处理如下的几种对List的操作。
L=[]: 将名字为L的List清空。在这里，List 的名字是长度为1到10之间
的字符串(只包括大小写字母)。如果L原来不存在，这个语句相当于定义了一个名字为L的空列表。
L.append(x):向L的末端插入元素x。为方便起见，这里的x只会是[0, 65536]之间的整数。
L.sort():将L中的元素按升序排序。
L[id]:返回L中下标为id(id≥0)的值。下标是从0开始计数的。
给定若干Python语句，你的任务是对于每个形如L[id]的语句，输出它返回的值。输入格式
输入数据包含多组测试数据。请注意各组测试数据之间是相互独立的。输入的第一行是一个整数T(T≤100)，表示测试数据的组数。
每组测试数据第一行是语句的数量N (N≤100)。接下来N行,每行一个python语句。测试数据保证只会出现上述四种语句，语句中间不会出现空格。一个List在被使用前一定会被先定义。输出格式
对于每个查询，输出查找的L[id]的值。如果id超出了当前List 的下标范围，;输出一行ERROR。
样例输入
2
5
a=[]
a.append(0)
a.append(1)
a[0]
a[1]
8
lista=[]
lista.append(123)
lista.append(65)
lista[0]
lista.sort()
lista[0]
listb=[]
listb[0]样例输出
0
1
123
65
ERROR思路解析
- 对输入的操作语句进行分离。这里用到JAVA里面
string.split([正则表达式])或者是Pattern p = Pattern.compile([正则表达式]) p.split(string)两种方法都可以。前者更简单一点。 - 使用IDEA注意输入
a.append(0)不能直接手敲进去，而是要复制粘贴过去，否则这个0会变成特殊字符，而导致输入错误
AC代码
import com.sun.org.apache.xalan.internal.lib.ExsltStrings;
import java.io.IOException;
import java.util.*;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args)throws IOException{
Main list = new Main();
list.handle();
}
private void handle(){
Scanner scanner = new Scanner(System.in);
int arrayNum = scanner.nextInt();
for (int i = 0; i < arrayNum;i++){
int num = scanner.nextInt();
PythonListList pythonListList = new PythonListList();
for (int j = 0; j<num; j++){
String input = scanner.next();
Pattern p = Pattern.compile("\\.");
String[] result = p.split(input);
String arrayName;
if (result.length == 1){
p = Pattern.compile("=");
String [] result2 = p.split(input);
if (result2.length == 1){//get value by index
//get the array name and query value
int pos = input.indexOf("[");//L[id]
arrayName = input.substring(0,pos);
int index = Integer.parseInt(input.substring(pos + 1,input.length()-1));
int listIndex = pythonListList.find(arrayName);
if (listIndex != -1){
if (index <= pythonListList.pythonLists.get(listIndex).list.size() -1){
System.out.println(pythonListList.pythonLists.get(listIndex).list.get(index));
}else {// index is greater than the maximum of the array
System.out.println("ERROR");
}
}else {// not have the array
System.out.println("ERROR");
}
}else if (result2.length == 2){//clear or create array
arrayName = result2[0];
int x = pythonListList.find(arrayName);
if (x != -1){
//clear the array
pythonListList.pythonLists.get(x).list.clear();
}else {
//create new array
pythonListList.pythonLists.add(new PythonList(arrayName));
}
}
}else if (result.length == 2){//append(x) or sort()
arrayName = result[0];
String lastString = result[1];
int arrayIndex = pythonListList.find(arrayName);
if (arrayIndex != -1){
//get operation name
int pos = lastString.indexOf("(");
String operation = lastString.substring(0,pos);
if (operation.equals("append")){
int value = Integer.parseInt(lastString.substring(pos + 1,lastString.length() - 1));
pythonListList.pythonLists.get(arrayIndex).list.add(value);
}else if (operation.equals("sort")){
Collections.sort(pythonListList.pythonLists.get(arrayIndex).list);
}
}else {// not have the array
System.out.println("ERROR");
}
}
}
}
}
class PythonListList{
List<PythonList> pythonLists = new ArrayList<PythonList>();
int find(String name){
for (int i =0;i < pythonLists.size();i++){
if (name.equals(pythonLists.get(i).name)){
return i;//following operation is clear the array
}
}
return -1;// following operation is create
}
}
class PythonList{
String name;
List<Integer> list = new ArrayList<Integer>();
PythonList() {
}
public PythonList(String name) {
this.name = name;
}
}
}