博客

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());
	}
}

思路决定代码质量

,可以自定义一个排序规则,两个数m和n,如果mn比nm大,m应该放到n的后边,也就是认为m比n大. 关键就是制定排序规则。

• 排序规则举例如下：
• 若ab > ba 则 a > b，
• 若ab < ba 则 a < b，
• 若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个物件，一个装载重量为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

这题是一个老掉牙的01背包，思路都有，由于好久没怎么写，调试的过程中遇到了一些小的毛病，最后在eclipse中单步调试花了不少时间。代码如下：

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]);
	}
}