要求:叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。
*/
public class CircusTroup {
static class People{
int num;
int weight;
int height;
public People(int num,int weight,int height){
this.num=num;
this.weight=weight;
this.height=height;
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N;
while (scanner.hasNext()){
N=scanner.nextInt();
String inValid=scanner.nextLine();//无效
People[]  peoples=new People[N];
for(int i=0;i
String[] str=scanner.nextLine().split(" ");
peoples[i]=new People(Integer.valueOf(str[0]),Integer.valueOf(str[1]),Integer.valueOf(str[2]));
}
//第一处:注意地方
//先按照体重升序,再按照身高降序
//为什么身高要降序?因为:体重相同时，只有身高也相同才可以站在自己肩上，比自己矮是不能站在自己肩上的。
//而身高降序就保证了:体重相同时,身高不同为降序,不是升序序列,则不能站在自己肩上.
Arrays.sort(peoples,new Comparator() {
@Override
public int compare(People o1,People o2) {
if(o1.weight==o2.weight){
return o2.height-o1.height;
}else{
return o1.weight-o2.weight;
}
}
});
//第二处:注意地方 db部分开始
//按身高求最大升序子序列,不是太会
int[] dp=new int[N];
dp[0]=1;
int level=0;
for(int i=1;i
dp[i]=1;
for(int j=0;j代码,可以知道:子序列并不需要连续,只要满足if条件就可以
if(peoples[j].height<=peoples[i].height && dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
}
Arrays.sort(dp);
level=dp[N-1];
System.out.println(level);
}
}
}

Java中自定义排序可以通过实现Comparator接口或Comparable接口来完成。

关键：实现Comparator接口的关键在于重写compare()方法，Comparable接口的关键在于重写compareTo()方法。JDK中大部分的类都实现了Comparable接口，拥有compareTo方法。如Integer，String等。但是对于自己定义类，如果需要自定义排序，则要实现Comparable接口并重写compareTo()方法，若不重写就进行自定义排序，会报错。

方法：将实现好的接口作为参数传入Arrays.sort()中或Collections.sort()中即可。

上述两个静态方法都可以进行排序，简单区别：

1.Arrays.sort()方法可以对原始类型（基本数据类型）和对象类型进行排序，而Collections.sort()只能对List进行排序。

2.查看源码发现，Collections.sort()也是通过Arrays.sort()方法实现的

Comparator具体使用方法：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CustomSort {
	public static void main(String args[]){
		Integer numbers1[] = {32, 3, 321};
		List<Integer> list1 = Arrays.asList(numbers1);
		//注意list1中元素类型必须是对象类型，写原始类型会报错
		Collections.sort(list1, new MyComparator2());
		for (Integer integer : list1) {
			System.out.print(integer+" ");
		}
		
		System.out.println("\n---------------");
		
		//使用arrays.sort()方法自定义排序
		Integer numbers2[] = {1,51,6,1,465,496,-156};
		Arrays.sort(numbers2, new MyComparator2());
		for (Integer integer : numbers2) {
			System.out.print(integer+" ");
		}
		
		System.out.println("\n*************************");
		
		Student2 st1 = new Student2(123, "Bob");
		Student2 st2 = new Student2(122, "Bob");
		Student2 st3 = new Student2(124, "Allen");
		//使用collections.sort()方法
		List<Student2> list3 = new ArrayList<>();
		list3.add(st1);list3.add(st2);list3.add(st3);
		Collections.sort(list3, new MyComparator2());
		for (Student2 student : list3) {
			System.out.print(student);
		}

		System.out.println("\n---------------");
		
		Student2 ss1[] = {st1, st2, st3};
		//使用Arrays.sort()方法
		Arrays.sort(ss1, new MyComparator2());
		for (Student2 student : ss1) {
			System.out.print(student);
		}
	}
}
class MyComparator2 implements Comparator<Object>{
	@Override
	public int compare(Object o1, Object o2){
		//如果两个都是整数才调用该比较方法
		if(o1 instanceof Integer && o2 instanceof Integer){
			Integer i1 = (Integer) o1;
			Integer i2 = (Integer) o2;
			return -i1.compareTo(i2);
		}
		//如果两个都是student2类型
		if(o1 instanceof Student2 && o2 instanceof Student2){
			Student2 s1 = (Student2)o1;
			Student2 s2 = (Student2)o2;
			//先按名字字典序排序，再按学号升序排序
			int t = s1.getName().compareTo(s2.getName());
			if(t == 0){
				return s1.getId().compareTo(s2.getId());
			}else return t;
		}
		return 0;
	}
}
//自定义一个学生类，然后对学生进行排序
class Student2{
	Integer id;
	String name;
	
	public Student2(Integer id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
	public Integer getId() {
		return id;
	}
	public void setId(Integer id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	@Override
	public String toString() {
		return "[id=" + id + ", name=" + name + "] ";
	}
}

运行结果：
321 32 3 
---------------
496 465 51 6 1 1 -156 
*************************
[id=124, name=Allen] [id=122, name=Bob] [id=123, name=Bob] 
---------------
[id=124, name=Allen] [id=122, name=Bob] [id=123, name=Bob] 


Comparable具体使用方法：
public class TestComparable {
	public static void main(String args[]){
		Student3 st1 = new Student3(123, "Bob");
		Student3 st2 = new Student3(122, "Bob");
		Student3 st3 = new Student3(124, "Allen");
		//使用Collections.sort()方法进行排序
		List<Student3> list1 = new ArrayList<>();
		list1.add(st1);list1.add(st2);list1.add(st3);
		Collections.sort(list1);
		for (Student3 student : list1) {
			System.out.print(student);
		}
		
		System.out.println("\n-------------");
		
		//使用Arrays.sort()方法进行排序
		Student3 s[] = {st1, st2, st3};
		Arrays.sort(s);
		for (Student3 student : s) {
			System.out.print(student);
		}
	}
}
//实现Comparable接口
class Student3 implements Comparable<Student3>{
	Integer id;
	String name;
	
	public Student3(Integer id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
	public Integer getId() {
		return id;
	}
	public void setId(Integer id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	@Override
	public String toString() {
		return "[id=" + id + ", name=" + name + "] ";
	}
	//重写compareTo方法，自定义排序规则
	@Override
	public int compareTo(Student3 stu){
		//先按名字字典序排序，再按学号升序排序
		int t = this.name.compareTo(stu.name);
		if(t == 0){
			return this.id.compareTo(stu.id);
		}else return t; 
	}
}

运行结果：
[id=124, name=Allen] [id=122, name=Bob] [id=123, name=Bob] 
-------------
[id=124, name=Allen] [id=122, name=Bob] [id=123, name=Bob] 


弄懂Java中排序的一些使用方法后，手是不是有点痒。试试下面这个题目吧。

题目出处参考《剑指offer》：把数组排成最小的数

题目描述

   输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

输入描述

   多组输入

每组测试样例第一行为n，表示数组有n个整数，接下来一行n个整数



输入描述

   每组输入输出一行，整个数组排成的最小的数字

sample input

   5

6 2 87 15 2

3

3 32 321

sample output

   1522687

321323

source

   《剑指offer》：把数组排成最小的数


    起初可能会没有思路，但是仔细想想过后，你会发现这是一道排序题，通过自定义排序规则就可以做到排出来的数字最小。

思路：假设两个数m和n，试考虑m和n应该怎么排列才能使得m和n拼接的数字最小？这个应该很好办，无非就是两种拼接方式都试一遍，比较一下mn和nm的大小即可。这样一来，两个数扩展到n个数也是一样的。我们只需要两两进行拼接进行比较，知道最后全部比完，这也就相当于一个排序。

    当mn  < nm时，我们想要的是mn这种拼接方式，所以m应该排在n前面。而当mn = nm时，无论哪种方式都可以。同理当mn > nm时，我们定义n排在m前面。

    那么问题来了，怎么进行拼接？很直观的可以想到两个数值拼接起来，但是这样是有可能溢出的。所以我们采用字符串拼接，把数字看成字符串，然后进行比较。下面代码中调用的是String自带的compareTo方法（按照字典序）。

示例代码：
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class OfferSort {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n;
		
		while(sc.hasNext()){
			n = sc.nextInt();
			//输入
			int arr[] = new int[n];
			for(int i = 0; i < n; i++)
				arr[i] = sc.nextInt();
			
			//转化为字符串
			String s[] = new String[arr.length];
			for(int i = 0; i < arr.length; i++)
				s[i] = String.valueOf(arr[i]);
			
			//按照自定义的规则排序
			Arrays.sort(s, new MyComparator5());
			//组装答案并输出
			String ans = "";
			for (String str : s) 
				ans += str;
			System.out.println(ans);
		}
	}
}
class MyComparator5 implements Comparator<Object>{
	@Override
	public int compare(Object o1, Object o2){
		if(o1 instanceof String && o2 instanceof String){
			String s1 = (String)o1;
			String s2 = (String)o2;
			String s3 = s1+s2;
			String s4 = s2+s1;
			int t = s3.compareTo(s4);
			if(t > 0)//若s3>s4，即s1s2 > s2s1,所以我们s2排在s1的前面
				return 1;
			else if(t < 0)//s3<s4, 所以s1应该排在s2前面
				return -1;
			else return 0;
		}
		return 0;
	}
}

有两种自定义排序的方法,


实现Comparable接口

public int compareTo(Object o)   {}


实现Comparator接口


public class Main implements Comparable{
	public int age;
	public String name;
	public Main(int age,String name) {
		// TODO Auto-generated constructor stub
		this.age=age;
		this.name=name;
	}
	public Main() {
		// TODO Auto-generated constructor stub
	}
    public static void main(String[] args) {
		Random random=new Random(100);
		List<Main> list=new ArrayList<Main>();
		for(int i=0;i<10;i++) {
			list.add(new Main(random.nextInt(100),random.nextInt(100)+""));//随机生成age
		}
		Collections.sort(list);
		for(Main i:list) {
			System.out.println(i.age+" "+i.name);
		}
	}
    // <font color="red">实现compareTo方法</font>
	@Override
	public int compareTo(Object o) {
		// TODO Auto-generated method stub
		Main toCompare=(Main)o;
		if (this.age>toCompare.age) {
			return 1;
		}
		else if (this.age==toCompare.age) {
			return 0;
		}
		else {
			return -1;
		}
	}
}

package HOMEWORK;
import java.util.*;
import java.io.*;


public class Main {
	public int age;
	public String name;
	public Main(int age,String name) {
		// TODO Auto-generated constructor stub
		this.age=age;
		this.name=name;
	}
	public Main() {
		// TODO Auto-generated constructor stub
	}
    public static void main(String[] args) {
		Random random=new Random(100);
		Main[] list=new Main[10];
		for(int i=0;i<10;i++) {
			list[i]=new Main(random.nextInt(100),random.nextInt(100)+"");
		}
		System.out.println("未修改前:");
		for(Main i:list) {
			System.out.print(i.age+" ");
		}
		System.out.println();
		Arrays.sort(list,new Comparator<>() {
			
			@Override
			public int compare(Main o1, Main o2) {
				// TODO Auto-generated method stub
		    	return o1.age-o2.age;
			}
		});
		System.out.println("修改后:");
		for(Main i:list) {
			System.out.print(i.age+" ");
		}
	}
   
}

Collections.sort(List<T> list,Comparator<? super T> c);方法

 

例如有如下集合：


List<Map<String, Object>> list = new ArrayList<Map<String,Object>>();

集合内的值为：

{name=zs, age=23},

{name=ls, age=25},

{name=ww, age=22},

{name=zl, age=37},

{name=qq, age=18}

 


 

我们要根据age的值给集合中的元素排序

使用Collections.sort(List<T> list,Comparator<? super T> c);方法

Collections.sort(list, new Comparator<Map<String, Object>>()
{
    @Override
    public int compare(Map<String, Object> o1, Map<String, Object> o2)
    {
        return 0;
    }
});

 

 

Comparator接口实现compare方法

经过踩坑，知道了compare方法两个参数代表的意义

o1代表后一个元素，o2代表前一个元素

例如上述list集合，当方法进行第一次比较时，o1是{name=ls, age=25}，o2是{name=zs, age=23}

 

compare方法的返回值是0、正整数、负整数

当返回0或正整数时，元素排序不变

当返回负整数时，元素调换位置

 

例如我们要将上述list集合按照升序排列，代码如下：

Collections.sort(list, new Comparator<Map<String, Object>>()
{
    @Override
    public int compare(Map<String, Object> o1, Map<String, Object> o2)
    {
        // o1代表着后一个元素，o2代表前一个元素
        int ageF = (int)o1.get("age");
        int ageB = (int)o2.get("age");
        
        // 容易理解的代码
        if (ageF >= ageB)
        {// 如果后一个元素的值大于或等于前一个元素的值，元素位置不变
            return 1;
        }
        else
        {// 如果后一个元素的值小于前一个元素的值，代码位置调换
            return -1;
        }
        
        // 上述代码可简化为：
        // return ageF - ageB;
    }
});

遍历执行后的集合：

list.forEach(map->System.out.println(map.get("name").toString() + ":" + map.get("age")));得到结果：