ITKeyword,专注技术干货聚合推荐

注册 | 登录

算法和数据结构面试题(15)-8张扑克的游戏

qhshiniba 分享于 2014-12-27

推荐:算法与数据结构面试题(10)-颠倒链表

题目 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。 解题思路 1.先用递归颠倒 2.尝试不用递归颠倒 代码 1.递归式 public class Problem8

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目


有4 张红色的牌和4 张蓝色的牌,主持人先拿任意两张,
再分别在A、B、C 三人额头上贴任意两张牌,
A、B、C 三人都可以看见其余两人额头上的牌,
看完后让他们猜自己额头上是什么颜色的牌,
A 说不知道,B 说不知道,C 说不知道,然后A 说知道了。
请教如何推理,A 是怎么知道的。
如果用程序,又怎么实现呢?

解题思路


首先组合的情形是3×3×3 = 27


public void group() {
        String[] arg = { "蓝-蓝", "红-红", "红-蓝" };
        int size = arg.length;
        int index = 0;
        for (int i = 0; i < size; i++) {
            String A = arg[i];
            for (int j = 0; j < size; j++) {
                String B = arg[j];
                for (int k = 0; k < size; k++) {
                    String C = arg[k];
                    index++;
                    String group = String.format("%s-%s-%s", A, B, C);
                    String groupStr = String.format("%s %s %s", A, B, C);
                    System.out.print(index + ": ");
                    System.out.println(groupStr);
                }
            }
        }
    }

1: 蓝-蓝 蓝-蓝 蓝-蓝
2: 蓝-蓝 蓝-蓝 红-红
3: 蓝-蓝 蓝-蓝 红-蓝
4: 蓝-蓝 红-红 蓝-蓝
5: 蓝-蓝 红-红 红-红
6: 蓝-蓝 红-红 红-蓝
7: 蓝-蓝 红-蓝 蓝-蓝
8: 蓝-蓝 红-蓝 红-红
9: 蓝-蓝 红-蓝 红-蓝
10: 红-红 蓝-蓝 蓝-蓝
11: 红-红 蓝-蓝 红-红
12: 红-红 蓝-蓝 红-蓝
13: 红-红 红-红 蓝-蓝
14: 红-红 红-红 红-红
15: 红-红 红-红 红-蓝
16: 红-红 红-蓝 蓝-蓝
17: 红-红 红-蓝 红-红
18: 红-红 红-蓝 红-蓝
19: 红-蓝 蓝-蓝 蓝-蓝
20: 红-蓝 蓝-蓝 红-红
21: 红-蓝 蓝-蓝 红-蓝
22: 红-蓝 红-红 蓝-蓝
23: 红-蓝 红-红 红-红
24: 红-蓝 红-红 红-蓝
25: 红-蓝 红-蓝 蓝-蓝
26: 红-蓝 红-蓝 红-红
27: 红-蓝 红-蓝 红-蓝

然后再通过一些条件过滤掉上面组合中一些选项


条件1.组合中的红的数量或者蓝的数量不能超过4


public void group() {
		String[] arg = { "蓝-蓝", "红-红", "红-蓝" };
		int size = arg.length;
		int index = 0;
		for (int i = 0; i < size; i++) {
			String A = arg[i];
			for (int j = 0; j < size; j++) {
				String B = arg[j];
				for (int k = 0; k < size; k++) {
					String C = arg[k];
					index++;
					String group = String.format("%s-%s-%s", A, B, C);
					String groupStr = String.format("%s %s %s", A, B, C);
					if (getStrCount(group)) {
						System.out.print(index + ": ");
						System.out.println(groupStr);
					}
				}
			}
		}
	}

	public boolean getStrCount(String str) {
		String[] args = str.split("-");
		int blueCount = 0;
		int redCount = 0;
		for (int i = 0; i < args.length; i++) {
			if (args[i].equals("蓝")) {
				blueCount++;
			} else if (args[i].equals("红")) {
				redCount++;
			}
		}
		if (blueCount > 4 || redCount > 4) {
			return false;
		}
		return true;
	}


过滤掉上面编号为1,3,7,14,15,17,19,23八种情况。还剩19种。


2: 蓝-蓝 蓝-蓝 红-红
4: 蓝-蓝 红-红 蓝-蓝
5: 蓝-蓝 红-红 红-红
6: 蓝-蓝 红-红 红-蓝
8: 蓝-蓝 红-蓝 红-红
9: 蓝-蓝 红-蓝 红-蓝
10: 红-红 蓝-蓝 蓝-蓝
11: 红-红 蓝-蓝 红-红
12: 红-红 蓝-蓝 红-蓝
13: 红-红 红-红 蓝-蓝
16: 红-红 红-蓝 蓝-蓝
18: 红-红 红-蓝 红-蓝
20: 红-蓝 蓝-蓝 红-红
21: 红-蓝 蓝-蓝 红-蓝
22: 红-蓝 红-红 蓝-蓝
24: 红-蓝 红-红 红-蓝
25: 红-蓝 红-蓝 蓝-蓝
26: 红-蓝 红-蓝 红-红
27: 红-蓝 红-蓝 红-蓝

条件2.A不知道,B不知道,C不知道。说明三个人当中不能每个人手里的两张牌都是一样的颜色。


反证法:如果出现三个人当中每个人手里的牌都是颜色一样的。那么第一次的时候,3个人当中一眼就直接能猜出来了。


public void group() {
		String[] arg = { "蓝-蓝", "红-红", "红-蓝" };
		int size = arg.length;
		int index = 0;
		for (int i = 0; i < size; i++) {
			String A = arg[i];
			for (int j = 0; j < size; j++) {
				String B = arg[j];
				for (int k = 0; k < size; k++) {
					String C = arg[k];
					index++;
					String groupStr = String.format("%s %s %s", A, B, C);

					// 条件1
					String group = String.format("%s-%s-%s", A, B, C);
					if (!getStrCount(group))
						continue;
					// 条件2
					if (!isEveryOneSame(A) && !isEveryOneSame(B)
							&& !isEveryOneSame(C))
						continue;
					System.out.print(index + ": ");
					System.out.println(groupStr);
				}
			}
		}
	}

	// 条件2
    private boolean isEveryOneSame(String one) {
        String[] args = one.split("-");
        if (args[0].equals(args[1])) {
            return true;
        }
        return false;
    }

	// 条件1
	private boolean getStrCount(String str) {
		String[] args = str.split("-");
		int blueCount = 0;
		int redCount = 0;
		for (int i = 0; i < args.length; i++) {
			if (args[i].equals("蓝")) {
				blueCount++;
			} else if (args[i].equals("红")) {
				redCount++;
			}
		}
		if (blueCount > 4 || redCount > 4) {
			return false;
		}
		return true;
	}


可能的组合就剩下了下面几种了。

推荐:算法与数据结构面试题(18)-二叉树镜像

题目 输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 解题


6: 蓝-蓝 红-红 红-蓝
8: 蓝-蓝 红-蓝 红-红
9: 蓝-蓝 红-蓝 红-蓝
12: 红-红 蓝-蓝 红-蓝
16: 红-红 红-蓝 蓝-蓝
18: 红-红 红-蓝 红-蓝
20: 红-蓝 蓝-蓝 红-红
21: 红-蓝 蓝-蓝 红-蓝
22: 红-蓝 红-红 蓝-蓝
24: 红-蓝 红-红 红-蓝
25: 红-蓝 红-蓝 蓝-蓝
26: 红-蓝 红-蓝 红-红
27: 红-蓝 红-蓝 红-蓝


可以排除编号2,4,5,10,11,13六种情况。还剩13种。


条件3.上面的情况中,要排除C可以根据A,B的不知道,然后可以一眼就能看出自己是什么牌组合。


这种情况就是A手中的牌颜色是一样的,B手中的牌颜色也是一样的。例如6和12


public void group() {
		String[] arg = { "蓝-蓝", "红-红", "红-蓝" };
		int size = arg.length;
		int index = 0;
		for (int i = 0; i < size; i++) {
			String A = arg[i];
			for (int j = 0; j < size; j++) {
				String B = arg[j];
				for (int k = 0; k < size; k++) {
					String C = arg[k];
					index++;
					String groupStr = String.format("%s %s %s", A, B, C);

					// 条件1
					String group = String.format("%s-%s-%s", A, B, C);
					if (!getStrCount(group))
						continue;
					// 条件2
					if (isEveryOneSame(A) && isEveryOneSame(B)
							&& isEveryOneSame(C))
						continue;
					// 条件3
					if (isEveryOneSame(A) && isEveryOneSame(B))
						continue;
					System.out.print(index + ": ");
					System.out.println(groupStr);
				}
			}
		}
	}

	// 条件2
	private boolean isEveryOneSame(String one) {
		String[] args = one.split("-");
		if (args[0].equals(args[1])) {
			return true;
		}
		return false;
	}

	// 条件1
	private boolean getStrCount(String str) {
		String[] args = str.split("-");
		int blueCount = 0;
		int redCount = 0;
		for (int i = 0; i < args.length; i++) {
			if (args[i].equals("蓝")) {
				blueCount++;
			} else if (args[i].equals("红")) {
				redCount++;
			}
		}
		if (blueCount > 4 || redCount > 4) {
			return false;
		}
		return true;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Problem22 problem = new Problem22();
		problem.group();
	}

}


还剩下11种情况。


8: 蓝-蓝 红-蓝 红-红
9: 蓝-蓝 红-蓝 红-蓝
16: 红-红 红-蓝 蓝-蓝
18: 红-红 红-蓝 红-蓝
20: 红-蓝 蓝-蓝 红-红
21: 红-蓝 蓝-蓝 红-蓝
22: 红-蓝 红-红 蓝-蓝
24: 红-蓝 红-红 红-蓝
25: 红-蓝 红-蓝 蓝-蓝
26: 红-蓝 红-蓝 红-红
27: 红-蓝 红-蓝 红-蓝

得出结果


上面剩下的11中情况都是符合实际的拿牌情况,以及根据A,B,C第一轮都无法判断出自己手中的牌这些条件过滤后的组合。那么再根据最后一个第二轮A就已经知道自己的牌了。说明从上面组合中找出,以B,C组合为关键字的,A只有一种情况的组合。比如情况8中,B,C组合是“红-蓝 红-红”,那么根据这个去找找看,同样是这个条件的A还有没有其他情况。很显然发现了第26号符合。说明这种组合是不符合要求的。而第20号的“蓝-蓝 红-红”只有一种情况,说明符合要求。那用程序怎么实现,我们可以以B+C为关键字组建一个map,value值为这个关键字在上面11情况中出现的次数。这样我们可以得到出现一次的关键字,这样很容易确定是第几号。


public class Problem22 {
    //以BC为关键字,次数为value的MAP
    Map<String,Integer> map = new LinkedHashMap<String,Integer>();
    //以BC为关键字,组合为value的MAP
    Map<String,String> map1 = new LinkedHashMap<String,String>();

    public void group() {
        String[] arg = { "蓝-蓝", "红-红", "红-蓝" };
        int size = arg.length;
        int index = 0;
        for (int i = 0; i < size; i++) {
            String A = arg[i];
            for (int j = 0; j < size; j++) {
                String B = arg[j];
                for (int k = 0; k < size; k++) {
                    String C = arg[k];
                    index++;
                    String groupStr = String.format("%s %s %s", A, B, C);

                    // 条件1
                    String group = String.format("%s-%s-%s", A, B, C);
                    if (!getStrCount(group))
                        continue;
                    // 条件2
                    if (isEveryOneSame(A) && isEveryOneSame(B)
                            && isEveryOneSame(C))
                        continue;
                    // 条件3
                    if (isEveryOneSame(A) && isEveryOneSame(B))
                        continue;

                    if(map.containsKey(B + C)){
                       int num =  map.get(B+C);
                       map.put(B+C,++num);
                    }else{
                        map.put(B+C,1);
                    }
                    map1.put(B+C,index + ": "+groupStr);
                    System.out.print(index + ": ");
                    System.out.println(groupStr);
                }
            }
        }
        Set<Map.Entry<String, Integer>> entrys = map.entrySet();
        Iterator<Map.Entry<String, Integer>> iter = entrys.iterator();
        //找到次数为1的组合
        while(iter.hasNext()){
            Map.Entry<String, Integer> entry= iter.next();
            if(entry.getValue() ==1){
                String answer = map1.get(entry.getKey());
                System.out.println("从上面的组合中找到的符合条件的答案为 : "+answer);
            }
        }


    }

    // 条件2
    private boolean isEveryOneSame(String one) {
        String[] args = one.split("-");
        if (args[0].equals(args[1])) {
            return true;
        }
        return false;
    }

    // 条件1
    private boolean getStrCount(String str) {
        String[] args = str.split("-");
        int blueCount = 0;
        int redCount = 0;
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("蓝")) {
                blueCount++;
            } else if (args[i].equals("红")) {
                redCount++;
            }
        }
        if (blueCount > 4 || redCount > 4) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Problem22 problem = new Problem22();
        problem.group();
    }

}

结果为


8: 蓝-蓝 红-蓝 红-红
9: 蓝-蓝 红-蓝 红-蓝
16: 红-红 红-蓝 蓝-蓝
18: 红-红 红-蓝 红-蓝
20: 红-蓝 蓝-蓝 红-红
21: 红-蓝 蓝-蓝 红-蓝
22: 红-蓝 红-红 蓝-蓝
24: 红-蓝 红-红 红-蓝
25: 红-蓝 红-蓝 蓝-蓝
26: 红-蓝 红-蓝 红-红
27: 红-蓝 红-蓝 红-蓝
从上面的组合中找到的符合条件的答案为 : 20: 红-蓝 蓝-蓝 红-红
从上面的组合中找到的符合条件的答案为 : 21: 红-蓝 蓝-蓝 红-蓝
从上面的组合中找到的符合条件的答案为 : 22: 红-蓝 红-红 蓝-蓝
从上面的组合中找到的符合条件的答案为 : 24: 红-蓝 红-红 红-蓝


有4种情况下,A可以猜出自己的牌。当然需要A能有这么强的逻辑。


总结


有没有发现可能的情况中A  手中的牌都是一样的:红蓝。所以以后你就猜自己是红蓝就行了吧。

推荐:算法和数据结构面试题(16)-单链表倒置

题目 链表操作(1)单链表就地逆置 解题思路 关于单链表 1.创建单链表,需要首先写一个单链表的类。 模仿LinkedList写一个SingleLinkedList类。 /** * Copyrig

题目 有4 张红色的牌和4 张蓝色的牌,主持人先拿任意两张,再分别在A、B、C 三人额头上贴任意两张牌,A、B、C 三人都可以看见其余两人额头上的牌,看完后让他们猜自己额头上是什么颜色的牌,

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。