@TOC

前言

一张扑克有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];
    }