MyException - 我的异常网
当前位置:我的异常网» Android » Android面试题目之5: 算法题-嵌套的信封

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

www.MyException.Cn  网友分享于:2013-08-16  浏览:0次
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
]

 

总结:

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

 

 

 

 

文章评论

十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
鲜为人知的编程真相
鲜为人知的编程真相
每天工作4小时的程序员
每天工作4小时的程序员
程序员应该关注的一些事儿
程序员应该关注的一些事儿
旅行,写作,编程
旅行,写作,编程
 程序员的样子
程序员的样子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
中美印日四国程序员比较
中美印日四国程序员比较
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
那些争议最大的编程观点
那些争议最大的编程观点
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员和编码员之间的区别
程序员和编码员之间的区别
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
一个程序员的时间管理
一个程序员的时间管理
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
代码女神横空出世
代码女神横空出世
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
10个调试和排错的小建议
10个调试和排错的小建议
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员的鄙视链
程序员的鄙视链
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
如何成为一名黑客
如何成为一名黑客
编程语言是女人
编程语言是女人
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员都该阅读的书
程序员都该阅读的书
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
我的丈夫是个程序员
我的丈夫是个程序员
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java程序员必看电影
Java程序员必看电影
漫画:程序员的工作
漫画:程序员的工作
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
总结2014中国互联网十大段子
总结2014中国互联网十大段子
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有