19~Blog | 今天总是好过昨天~

package com.ll19.test;
 
import java.util.ArrayList;
import java.util.Calendar;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class PetFish {
 
	/**
	 * 在一条街上，有5座房子，喷了5种颜色,每个房里住着不同国籍的人,每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。问题：谁养鱼?
	 * 
	 * 提示：
	 * 
	 * 1、英国人住红色房子 2、瑞典人养狗 3、丹麦人喝茶 4、绿色房子在白色房子左面 5、绿色房子主人喝咖啡 6、抽Pall Mall 香烟的人养鸟
	 * 7、黄色房子主人抽Dunhill 香烟 8、住在中间房子的人喝牛奶 9、 挪威人住第一间房 10、抽Blends香烟的人住在养猫的人隔壁
	 * 11、养马的人住抽Dunhill 香烟的人隔壁 12、抽Blue Master的人喝啤酒 13、德国人抽Prince香烟
	 * 14、挪威人住蓝色房子隔壁 15、抽Blends香烟的人有一个喝水的邻居
	 * 
	 * @author <a href="http://www.LL19.com/">LL19.com</a>
	 * 
	 */
 
	// 保存所有房子的组合
	private static ArrayList<String> houseList = new ArrayList<String>();
 
	// 保存所有宠物的组合
	private static ArrayList<String> petList = new ArrayList<String>();
 
	// 保存所有烟的组合
	private static ArrayList<String> smokeList = new ArrayList<String>();
 
	// 保存所有饮料的组合
	private static ArrayList<String> drinkList = new ArrayList<String>();
 
	// 保存所有国籍的组合
	private static ArrayList<String> peopleList = new ArrayList<String>();
 
	// 过滤用
	private static ArrayList<String> filterList;
 
	public static void main(String[] args) {
 
		// 开始时间
		long l1 = Calendar.getInstance().getTimeInMillis();
 
		// 房子 "绿色", "红色", "蓝色", "黄色", "白色"
		ArrayList<String> houseArray = new ArrayList<String>();
		houseArray.add("绿色");
		houseArray.add("红色");
		houseArray.add("蓝色");
		houseArray.add("黄色");
		houseArray.add("白色");
		String[] house = new String[5];
 
		rotate(house, houseArray, houseArray.size(), houseList);
 
		// 宠物 "猫", "狗", "鱼", "马", "鸟"
		ArrayList<String> petArray = new ArrayList<String>();
		petArray.add("猫");
		petArray.add("狗");
		petArray.add("鱼");
		petArray.add("马");
		petArray.add("鸟");
		String[] pet = new String[5];
 
		rotate(pet, petArray, petArray.size(), petList);
 
		// 烟 "PallMall", "Dunhill", "Blends", "BlueMaster", "Prince"
		ArrayList<String> smokeArray = new ArrayList<String>();
		smokeArray.add("PallMall");
		smokeArray.add("Dunhill");
		smokeArray.add("Blends");
		smokeArray.add("BlueMaster");
		smokeArray.add("Prince");
		String[] smoke = new String[5];
 
		rotate(smoke, smokeArray, smokeArray.size(), smokeList);
 
		// 饮料 "茶", "牛奶", "水", "咖啡", "啤酒"
		ArrayList<String> drinkArray = new ArrayList<String>();
		drinkArray.add("茶");
		drinkArray.add("牛奶");
		drinkArray.add("水");
		drinkArray.add("咖啡");
		drinkArray.add("啤酒");
		String[] drink = new String[5];
 
		rotate(drink, drinkArray, drinkArray.size(), drinkList);
 
		// 国籍 "英国人", "瑞典人", "丹麦人", "德国人", "挪威人"
		ArrayList<String> peopleArray = new ArrayList<String>();
		peopleArray.add("英国人");
		peopleArray.add("瑞典人");
		peopleArray.add("丹麦人");
		peopleArray.add("德国人");
		peopleArray.add("挪威人");
		String[] people = new String[5];
 
		rotate(people, peopleArray, peopleArray.size(), peopleList);
 
		// 队列本身可以过滤的
		// 住在中间房子的人喝牛奶
		filterList = new ArrayList<String>();
		for (int drinkNo = 0; drinkNo < drinkList.size(); drinkNo++) {
			String[] tmp = filter(drinkList, drinkNo);
			if (tmp[2].equals("牛奶")) {
				filterList.add(drinkList.get(drinkNo));
			}
		}
		drinkList = filterList;
 
		// 挪威人住第一间房
		filterList = new ArrayList<String>();
		for (int peopleNo = 0; peopleNo < peopleList.size(); peopleNo++) {
			String[] tmp = filter(peopleList, peopleNo);
			if (tmp[0].equals("挪威人")) {
				filterList.add(peopleList.get(peopleNo));
			}
		}
		peopleList = filterList;
 
		// 绿色房子在白色房子左面
		filterList = new ArrayList<String>();
		for (int houseNo = 0; houseNo < houseList.size(); houseNo++) {
			String[] tmp = filter(houseList, houseNo);
			for (int tmpNo = 0; tmpNo < tmp.length; tmpNo++) {
				// 英国人住红色房子 因为挪威人住第一间房 所以第一间不是红色 挪威人住蓝色房子隔壁 所以蓝色是第二间房
				// 绿色房子主人喝咖啡 住在中间房子的人喝牛奶 所以绿色房子不在中间
				if (!tmp[0].equals("红色") && tmp[1].equals("蓝色")
						&& !tmp[2].equals("绿色")) {
					if (tmp[tmpNo].equals("绿色")) {
						// 绿色不是最后一间
						if (tmpNo != 4 && tmp[tmpNo + 1].equals("白色")) {
							filterList.add(houseList.get(houseNo));
						}
					}
				}
			}
		}
		houseList = filterList;
 
		// 开始过滤其他条件
		boolean end = false;
 
		while (!end) {
 
			// 英国人住红色房子
			peopleList = filterOneToOne(peopleList, "英国人", houseList, "红色");
			houseList = filterOneToOne(houseList, "红色", peopleList, "英国人");
			// 绿色房子主人喝咖啡
			houseList = filterOneToOne(houseList, "绿色", drinkList, "咖啡");
			drinkList = filterOneToOne(drinkList, "咖啡", houseList, "绿色");
			// 瑞典人养狗
			peopleList = filterOneToOne(peopleList, "瑞典人", petList, "狗");
			petList = filterOneToOne(petList, "狗", peopleList, "瑞典人");
			// 丹麦人喝茶
			peopleList = filterOneToOne(peopleList, "丹麦人", drinkList, "茶");
			drinkList = filterOneToOne(drinkList, "茶", peopleList, "丹麦人");
			// 抽Pall Mall 香烟的人养鸟
			smokeList = filterOneToOne(smokeList, "PallMall", petList, "鸟");
			petList = filterOneToOne(petList, "鸟", smokeList, "PallMall");
			// 黄色房子主人抽Dunhill
			houseList = filterOneToOne(houseList, "黄色", smokeList, "Dunhill");
			smokeList = filterOneToOne(smokeList, "Dunhill", houseList, "黄色");
			// 德国人抽Prince香烟
			peopleList = filterOneToOne(peopleList, "德国人", smokeList, "Prince");
			smokeList = filterOneToOne(smokeList, "Prince", peopleList, "德国人");
			// 抽Blue Master的人喝啤酒
			smokeList = filterOneToOne(smokeList, "BlueMaster", drinkList, "啤酒");
			drinkList = filterOneToOne(drinkList, "啤酒", smokeList, "BlueMaster");
			// 抽Blends香烟的人住在养猫的人隔壁
			petList = filterOneToTwo(smokeList, "Blends", petList, "猫");
			smokeList = filterOneToTwo(petList, "猫", smokeList, "Blends");
			// 养马的人住抽Dunhill 香烟的人隔壁
			smokeList = filterOneToTwo(petList, "马", smokeList, "Dunhill");
			petList = filterOneToTwo(smokeList, "Dunhill", petList, "马");
			// 抽Blends香烟的人有一个喝水的邻居
			drinkList = filterOneToTwo(smokeList, "Blends", drinkList, "水");
			smokeList = filterOneToTwo(drinkList, "水", smokeList, "Blends");
 
			if (houseList.size() == 1 && petList.size() == 1
					&& smokeList.size() == 1 && drinkList.size() == 1
					&& peopleList.size() == 1) {
				end = true;
			}
 
		}
 
		System.out.println(houseList);
		System.out.println(petList);
		System.out.println(smokeList);
		System.out.println(drinkList);
		System.out.println(peopleList);
 
		// 结束时间
		long l2 = Calendar.getInstance().getTimeInMillis();
		System.out.println("用时（毫秒）: " + (l2 - l1));
	}
 
	// 递规方法 算出每个种类的组合
	public static void rotate(String[] result, List<String> al, int index,
			ArrayList<String> list) {
		index = result.length - index;
		if (index == result.length - 1) {
			result[index] = (String) al.get(0);
			organizeNum(result, list);
		}
		for (int s1 = 0; s1 < al.size(); s1++) {
			result[index] = (String) al.get(s1);
			ArrayList<String> al1 = new ArrayList<String>(al);
			al1.remove(result[index]);
			rotate(result, al1, al1.size(), list);
		}
	}
 
	// 加入容器
	public static void organizeNum(String[] result, ArrayList<String> list) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < result.length; i++) {
			sb.append(result[i].toString() + ";");
		}
		String pstr = sb.toString();
		list.add(pstr);
	}
 
	// 过滤器
	public static String[] filter(ArrayList<String> list, int n) {
		String tmp = list.get(n);
		String[] tmp2 = new String[5];
		tmp2 = tmp.split(";");
		return tmp2;
	}
 
	// 过滤类似“英国人住红色房子”这样的条件
	public static ArrayList<String> filterOneToOne(ArrayList<String> List1,
			String text1, ArrayList<String> List2, String text2) {
		Set<Object> set = new HashSet<Object>();
		filterList = new ArrayList<String>();
		for (int no = 0; no < List2.size(); no++) {
			String[] tmp = filter(List2, no);
			for (int no1 = 0; no1 < tmp.length; no1++) {
				if (tmp[no1].equals(text2)) {
					if (!set.contains(no1)) {
						set.add(no1);
						for (int no2 = 0; no2 < List1.size(); no2++) {
							String[] tmp2 = filter(List1, no2);
							if (tmp2[no1].equals(text1)) {
								filterList.add(List1.get(no2));
							}
						}
					}
				}
			}
		}
		return filterList;
 
	}
 
	// 过滤类似“抽Blends香烟的人住在养猫的人隔壁”这样的条件
	public static ArrayList<String> filterOneToTwo(ArrayList<String> List1,
			String text1, ArrayList<String> List2, String text2) {
 
		Set<Object> set = new HashSet<Object>();
		Set<Object> set2 = new HashSet<Object>();
		filterList = new ArrayList<String>();
 
		for (int no = 0; no < List1.size(); no++) {
			String[] tmp = filter(List1, no);
			for (int tmpNo = 0; tmpNo < tmp.length; tmpNo++) {
				if (tmp[tmpNo].equals(text1)) {
					if (!set.contains(tmpNo)) {
						set.add(tmpNo);
						int tmpNo2;
						if (tmpNo == 0) {
							tmpNo2 = 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						} else if (tmpNo == 4) {
							tmpNo2 = 3;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						} else {
							tmpNo2 = tmpNo + 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
							tmpNo2 = tmpNo - 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						}
					}
				}
			}
		}
		return filterList;
 
	}
 
}

 
package com.ll19.test;
 
import java.util.ArrayList;
 
public class Ant {
 
	/**
	 * 
	 * 题目：有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
	 * 木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。
	 * 当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。 假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
	 * 
	 * @author <a href="http://www.LL19.com/">LL19.com</a>
	 * 
	 */
 
	// 保存所有蚂蚁可能头朝方向的组合
	private static ArrayList<String> antList = new ArrayList<String>();
 
	private char[] chars;
 
	private int woodLength = 27;
 
	private int charLen;
 
	private int antLength;
 
	public Ant() {
		String str = "左右";
		chars = str.toCharArray();
		charLen = chars.length;
		antLength = 5;
	}
 
	public static void main(String[] args) {
		Ant ant = new Ant();
		long begin = System.currentTimeMillis();
		ant.combination(new StringBuffer(""), ant.antLength);
		ant.endTime();
		System.out.println("执行时间:" + (System.currentTimeMillis() - begin)
				+ "毫秒");
	}
 
	// 计算每种组合蚂蚁全部离开的时间
	public void endTime() {
 
		int min = 10000;
		int max = 0;
 
		for (int i = 0; i < antList.size(); i++) {
			int[] position = { 3, 7, 11, 17, 23 };
			String ant = antList.get(i);
			String[] list = ant.split("");
			int time = 0;
			boolean end = false;
			System.out.print("当前为：" + antList.get(i) + " | ");
			//System.out.println("行走过程:");
			while (!end) {
				time++;
				end = true;
				//System.out.println(position[0] + "," + position[1] + ","+ position[2] + "," + position[3] + "," + position[4]);
				for (int n = 1; n < list.length; n++) {
					// 移动
					if (list[n].equals("左")) {
						position[n - 1] -= 1;
 
					}
					if (list[n].equals("右")) {
						position[n - 1] += 1;
					}
				}
				// 此时所有蚂蚁都走了一遍 则在这里判断有没有碰头的(只判断和右边的有没有碰头 如果碰头两个都改变方向
				// 则最后一个就不用判断了)
				for (int n = 1; n < list.length; n++) {
					if (n != 5) {
						if (position[n - 1] == position[n]) {
							if (list[n].equals("左"))
								list[n] = "右";
							else if (list[n].equals("右"))
								list[n] = "左";
							if (list[n + 1].equals("左"))
								list[n + 1] = "右";
							else if (list[n + 1].equals("右"))
								list[n + 1] = "左";
						}
					}
					// 判断如果没有走完的
					if (position[n - 1] >= 0 && position[n - 1] <= woodLength) {
						end = false;
					}
				}
			}
			System.out.println("所用时间：" + time);
			if (time > max) max = time;
			if (time < min) min = time;
		}
		System.out.println("最大时间: " + max);
		System.out.println("最小时间: " + min);
	}
 
	// 保存所有蚂蚁可能头朝方向的组合
	public void combination(StringBuffer str, int length) {
		if (length == 1) {
			for (int i = 0; i < charLen; i++) {
				StringBuffer result = new StringBuffer(str);
				result.append(chars[i]);
				antList.add(result.toString());
			}
		}
		if (length > 1) {
			for (int i = 0; i < charLen; i++) {
				StringBuffer temp = new StringBuffer(str);
				combination(temp.append(chars[i]), length - 1);
			}
		}
	}
}