扑克牌问题

---

前言

一张扑克有3个属性，每种属性有3种值（A、B、C）
比如"AAA"，第一个属性值A，第二个属性值A，第三个属性值A
比如"BCA"，第一个属性值B，第二个属性值C，第三个属性值A
给定一个字符串类型的数组cards[]，每一个字符串代表一张扑克
从中挑选三张扑克，一个属性达标的条件是：这个属性在三张扑克中全一样，或全不一样
挑选的三张扑克达标的要求是：每种属性都满足上面的条件
比如：“ABC”、“CBC”、“BBC”
第一张第一个属性为"A"、第二张第一个属性为"C"、第三张第一个属性为"B"，全不一样
第一张第二个属性为"B"、第二张第二个属性为"B"、第三张第二个属性为"B"，全一样
第一张第三个属性为"C"、第二张第三个属性为"C"、第三张第三个属性为"C"，全一样
每种属性都满足在三张扑克中全一样，或全不一样，所以这三张扑克达标
返回在cards[]中任意挑选三张扑克，达标的方法数

解题思路

选两张AAA,第三张必须AAA

一共27个牌面,必须选3张不同牌面的可能性有多少种
如果必选3个牌面,如果它达标的话，那这3个排名的组合数有多少?
100* 50 * 60
最暴力的就是27个牌面，有多少不同的三个牌面你都枚举一下
最后方案就是几个数相乘就行了
一共27个牌面,每个牌面要跟不要,但是一且超过3种, 就停止，
到最后正好3个排名,如果发现每一-位都- 样或者每一-位都不一样
把它们的数量取出来一乘就搞定了

最重要的技巧就是根据数据量猜解法
我一看100万张牌，我就知道用牌的角度来想是不对的，
必须从牌面着手，因为只有27种牌面

代码

	public static int ways(String[] cards) {
    
		int[] counts = new int[27];
		for (String s : cards) {
    
			char[] str = s.toCharArray();
			counts[(str[0] - 'A') * 9 + (str[1] - 'A') * 3 + (str[2] - 'A') * 1]++;
		}
		int ways = 0;
		for (int status = 0; status < 27; status++) {
    
			int n = counts[status];
			if (n > 2) {
    
				ways += n == 3 ? 1 : (n * (n - 1) * (n - 2) / 6);
			}
		}
		LinkedList<Integer> path = new LinkedList<>();
		for (int i = 0; i < 27; i++) {
    
			if (counts[i] != 0) {
    
				path.addLast(i);
				ways += process2(counts, i, path);
				path.pollLast();
			}
		}
		return ways;
	}

	// 之前的牌面，拿了一些 ABC BBB ... 
	// pre = BBB
	// ABC ...
	// pre = ABC
	// ABC BBB CAB
	// pre = CAB
	// 牌面一定要依次变大，所有形成的有效牌面，把方法数返回
	public static int process(int[] counts, int pre, LinkedList<Integer> path) {
    
		if (path.size() == 3) {
    
			return getWays2(counts, path);
		}
		int ways = 0;
		for (int next = pre + 1; next < 27; next++) {
    
			if (counts[next] != 0) {
    
				path.addLast(next);
				ways += process2(counts, next, path);
				path.pollLast();
			}
		}
		return ways;
	}

	public static int getWays(int[] counts, LinkedList<Integer> path) {
    
		int v1 = path.get(0);
		int v2 = path.get(1);
		int v3 = path.get(2);
		for (int i = 9; i > 0; i /= 3) {
    
			int cur1 = v1 / i;
			int cur2 = v2 / i;
			int cur3 = v3 / i;
			v1 %= i;
			v2 %= i;
			v3 %= i;
			if ((cur1 != cur2 && cur1 != cur3 && cur2 != cur3) || (cur1 == cur2 && cur1 == cur3)) {
    
				continue;
			}
			return 0;
		}
		v1 = path.get(0);
		v2 = path.get(1);
		v3 = path.get(2);
		return counts[v1] * counts[v2] * counts[v3];
	}