B駅の筆記試験の2つの問題

1、カンマで区切られた数のセットを入力し、そのセットを最小の数にします.

 
  ：123,22,32
  ：1232232

  ：210,21,11,12
  ：111221021

問題を解くとき、最初の桁数の小さい数字を前に、最初の桁数の大きい数字を後ろに置くと思いがちです.肝心な問題が来て、第一位の数字が同じようにどうするかというと、小さい数字を前にすることが容易に考えられます.例えば「12,11」の構成1112は全く問題ありません.「30,3」のように「0」の数があると問題があります.ソートするときは30を3の前に並べて、ソートルールをカスタマイズします.大体の考えはこうです.具体的なコードは以下の通りです.

package exam;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

class MYComparator implements Comparator {

	@Override
	public int compare(Object o1, Object o2) {
		Integer data1 = (Integer) o1;
		Integer data2 = (Integer) o2;
		String str1 = new String(data1+"");
		String str2 = new String(data2+"");
		if(data1>data2) {
			if(str1.contains(str2)) {
				int first = Integer.parseInt(str1.charAt(0)+"");
				int last = Integer.parseInt(str1.charAt(str1.length()-1)+"");
				if(first>last) return -1;
			}
			return 1;
		} else if (data1 < data2) {
			if(str2.contains(str1)) {
				int first = Integer.parseInt(str1.charAt(0)+"");
				int last = Integer.parseInt(str1.charAt(str1.length()-1)+"");
				if(first<last) return 1;
			}
			return -1;
		} else {
			return 0;
		}
	}
}

public class Problem2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String[] strs = str.split(",");
		int len = strs.length;
		Integer[] datas = new Integer[len];

		HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
		for(int i=0 ;i<len; i++) {
			datas[i] = Integer.parseInt(strs[i]);
			Integer tmp = datas[i];
			while(tmp>9) {
				tmp/=10;
			}
			if(map.get(tmp)==null) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(datas[i]);
				map.put(tmp, list);
			} else {
				ArrayList<Integer> list = (ArrayList<Integer>)map.get(tmp) ;
				list.add(datas[i]);
			}
		}
		StringBuilder sb = new StringBuilder();
		for(Integer i=1; i<=9; i++) {
			if(map.get(i)!=null) {
				ArrayList<Integer> lists = (ArrayList<Integer>)map.get(i);
				Collections.sort(lists,new MYComparator());
				for(Integer data:lists) {
					sb.append(data);
				}
			}
		}
		System.out.println(sb.toString());
	}
}

構想はコードの品質を決定して、1つの並べ替え規則をカスタマイズすることができて、2つの数mとn、もしmnがnmより大きいならば、mはnの後ろに置くべきで、つまりmがnより大きいと思っています.肝心なのは並べ替え規則を制定することです.

並べ替え規則は、例えば、

である.

ab>baであればa>b,

ab

ab=baの場合a=b;

解釈説明:

例えば「3」<「31」であるが「331」>「313」であるため、両者をつなぎ合わせる

を比較する.

package bilibili;

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

class MYComparator implements Comparator<Integer> {
	@Override
	public int compare(Integer m, Integer n) {
		Integer data1 = Integer.parseInt(m+""+n);
		Integer data2 = Integer.parseInt(n+""+m);
		if(data1>data2) {
			return 1;
		} 
		return -1;
	}
}

public class Problem2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String[] strs = str.split(",");
		int len = strs.length;
		Integer[] datas = new Integer[len];
		for(int i=0; i<strs.length; i++) {
			datas[i] = Integer.parseInt(strs[i]);
		}
		Arrays.sort(datas, new MYComparator());
		for(Integer data:datas) {
			System.out.print(data);
		}
	}
}

2、現在N個の物品があって、1個は重量Mのリュックサックを積んで、各物品の重量と価値を与えて、リュックサックが入れることができる物品の最大の価値を求めます.

  ：
5
10
2 3 4 6 5 
3 4 7 9 5

  ：16

  ：
5
10
2 2 5 6 5 
3 4 7 9 5

  ：16

この問題は1つの老いぼれた01リュックサックで、構想はすべてあって、長い間あまり書いていないため、デバッグの過程の中でいくつかの小さい欠点に出会って、最後にeclipseの中で1歩でデバッグして多くの時間を費やしました.コードは以下の通りです:

package exam;

import java.util.Scanner;

public class Problem3 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();		//N   
		int M = sc.nextInt();		//     M
		int[] w = new int[N+1];		//       
		int[] v = new int[N+1];		//       
		for(int i=1; i<N+1; i++) {
			w[i] = sc.nextInt();	//         
		}
		for(int i=1; i<N+1; i++) {
			v[i] = sc.nextInt();	//         
		}
		int[][] record = new int[N+1][M+1];
		for(int i=1; i<N+1; i++) {
			int weight = w[i];			//       
			int value = v[i];				//       
			for(int j=1; j<M+1; j++) {
				if(j>=weight) {
					record[i][j] = Math.max(record[i-1][j],record[i-1][j-weight] +value);
				} else {
					record[i][j] = record[i-1][j];
				}
			}
		}
		System.out.println(record[N][M]);
	}
}