poker question

---

前言

一张扑克有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[]中任意挑选三张扑克,达标的方法数

解题思路

choose twoAAA,The third one is requiredAAA

一共27个牌面,必须选3How many possibilities are there for different cards
If required3个牌面,If it hits the mark,那这3How many combinations are there for each ranking?
100* 50 * 60
最暴力的就是27个牌面,Enumerate how many different three cards there are
The final solution is to multiply several numbers on the line
一共27个牌面,每个牌面要跟不要,But once and beyond3种, 就停止,
It was just right in the end3个排名,If found each-位都- sample or each-The bits are different
Multiply the number of them and you're done

The most important technique is to guess the solution based on the amount of data
我一看100Thousands of cards,I knew it was wrong to think in terms of cards,
You must start with the cards,因为只有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];
	}