首页 > 代码库 > 11.7 马戏团叠罗汉
11.7 马戏团叠罗汉
思路：定义好Person的数据结构，按照身高和体重排好序。
solutions[i]代表以person[i]结尾的能够叠起的最多人的解。
solutions[0]初始化，然后求从1~n的情况。
import java.util.ArrayList;import java.util.Collections;public class Solution { public ArrayList<Person> getIncreasingSequence(ArrayList<Person> people) { Collections.sort(people); ArrayList<ArrayList<Person>> solutions = new ArrayList<ArrayList<Person>>(); ArrayList<Person> first = new ArrayList<Person>(); first.add(people.get(0)); solutions.add(first); for (int i = 1; i < people.size(); i++) { Person cur = people.get(i); int len = 0; int longestPre = -1; for (int j = 0; j < i; j++) { ArrayList<Person> pre = solutions.get(j); if (cur.isBigger(people.get(j))) { if (solutions.get(j).size() > len) { len = pre.size(); longestPre = j; } } } ArrayList<Person> curSolu = new ArrayList<Person>(); if (longestPre != -1) curSolu.addAll(solutions.get(longestPre)); curSolu.add(cur); solutions.add(curSolu); } int longestLen = 1; int longestIdx = -1; for (int i = 0; i < people.size(); i++) { if (solutions.get(i).size() > longestLen) { longestLen = solutions.get(i).size(); longestIdx = i; } } return solutions.get(longestIdx); } public static void main(String[] args) { ArrayList<Person> persons = initialize(); System.out.println(new Solution().getIncreasingSequence(persons)); } public static ArrayList<Person> initialize() { ArrayList<Person> items = new ArrayList<Person>(); Person item = new Person(65, 60); items.add(item); item = new Person(70, 150); items.add(item); item = new Person(56, 90); items.add(item); item = new Person(75, 190); items.add(item); item = new Person(60, 95); items.add(item); item = new Person(68, 110); items.add(item); item = new Person(35, 65); items.add(item); item = new Person(40, 60); items.add(item); item = new Person(45, 63); items.add(item); return items; }}class Person implements Comparable<Person> { int w; int h; public Person(int w, int h) { this.w = w; this.h = h; } public int compareTo(Person p) { if (h != p.h) return ((Integer) h).compareTo(p.h); else return ((Integer) w).compareTo(p.w); } public String toString() { return "(" + w + "," + h + ")"; } public boolean isBigger(Person b) { if (this.w > b.w && this.h > b.h) return true; else return false; }}
11.7 马戏团叠罗汉
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。