Android面试题目之五: 算法题--嵌套的信封

题目：

有很多随机大小的明信片，也有很多随机大小的信封。希望把一个明信片装到多个信封里。明信片只能装入比自己大的信封，信封也只能装入更大的信封。相同的大小无法装入。

 

为了保证最大数量的信封被使用和装入最多数量的卡片，请设计算法。

 

解决方法

1.将明信片和信封各自排序。

2.找到第一个明信片。

3.找到没使用的第一个信封。

4. 是否可装入，是则装入。否按顺序向前从大到小找卡片，能装入则装入。不能装入则继续从大到小找卡片。直到没有卡片可找。

 

代码

package sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NestedEnvelope {

	public static void main(String[] args) {
		List<Card> cards = new ArrayList<>();
		for (int i = 0; i < 5; ++i) {
			Card card = new Card();
			card.size = i * 2;
			card.id = i;
			cards.add(card);
		}

		List<Envelop> evelops = new ArrayList<>();

		for (int i = 0; i < 10; ++i) {
			Envelop env = new Envelop();
			env.size = i;
			env.id = i;
			evelops.add(env);
		}

		HashMap<Card, List<Envelop>> results = putInCard(cards, evelops);

		for (Map.Entry<Card, List<Envelop>> entry : results.entrySet()) {
			System.out.println("[");
			System.out.println("card:" + entry.getKey().size);
			for (Envelop env : entry.getValue()) {
				System.out.println("envelop:" + env.size);
			}
			System.out.println("]");
		}
	}

	static class Card implements Comparable<Card> {
		int id;
		int size;

		@Override
		public int compareTo(Card o) {
			// TODO Auto-generated method stub
			return size - o.size;
		}
	}

	static class Envelop implements Comparable<Envelop> {
		int id;
		int size;

		@Override
		public int compareTo(Envelop o) {
			// TODO Auto-generated method stub
			return size - o.size;
		}
	}

	public static HashMap<Card, List<Envelop>> putInCard(List<Card> cards, List<Envelop> envelops) {

		Collections.sort(cards);

		Collections.sort(envelops);
		
		HashMap<Card, List<Envelop>> cardWithEnvelops = new HashMap<Card, List<Envelop>>();
		
		for (int i = 0; i < cards.size(); ++i) {

			Card card = cards.get(i);

			Card nextCard = null;

			if (i + 1 < cards.size()) {
				nextCard = cards.get(i + 1);
			}

			List<Envelop> cardEnvelops = new ArrayList<Envelop>();
			
			cardWithEnvelops.put(card, cardEnvelops);
			
			Envelop lastEnvelop = null;
			
			while (envelops.size() > 0) {
				
				Envelop envelop = envelops.get(0);
				
				if ((lastEnvelop != null && envelop.size == lastEnvelop.size) || envelop.size == card.size) {
					
					for (int indexCard = i - 1; indexCard >= 0; --indexCard) {
						
						List<Envelop> preEnvelops = cardWithEnvelops.get(cards.get(indexCard));
						
						if (preEnvelops.size() == 0) {
							
							preEnvelops.add(envelop);
						
						} else {
							
							Envelop maxEnv = preEnvelops.get(preEnvelops.size() - 1);
							
							if (maxEnv.size < envelop.size) {
								
								preEnvelops.add(envelop);
							}
						}
					}
					
					envelops.remove(envelop);
					
					continue;
				}
				
				if (envelop.size > card.size && (nextCard == null || envelop.size <= nextCard.size)) {
					
					cardEnvelops.add(envelop);
					
					lastEnvelop = envelop;
					
					envelops.remove(envelop);
				
				} else {
					break;
				}
			}
		}
		return cardWithEnvelops;
	}
}

 

打印：

  

[
card:4
envelop:5
envelop:6
]
[
card:8
envelop:9
]
[
card:0
envelop:1
envelop:2
]
[
card:2
envelop:3
envelop:4
]
[
card:6
envelop:7
envelop:8
]

 

总结：

    结果并不是只有一种装法最多，但是设计的这个算法能保证装的最多卡片，和最多信封。