撲克牌的順子

題目：從撲克牌中隨機(jī)抽 5 張牌，判斷是不是一個(gè)順子， 即這 5 張牌是不是連續(xù)的。2～10 為數(shù)字本身， A 為 1。 J 為 11、Q 為 12、 為 13。小王可以看成任意數(shù)字。

解題思路

我們可以把 5 張牌看成由 5 個(gè)數(shù)字組成的數(shù)組。大、小王是特殊的數(shù)字，我們不妨把它們都定義為 0，這樣就能和其他撲克牌區(qū)分開來了。

接下來我們分析怎樣判斷 5 個(gè)數(shù)字是不是連續(xù)的，最直觀的方法是把數(shù)組排序。值得注意的是，由于 0 可以當(dāng)成任意數(shù)字，我們可以用 0 去補(bǔ)滿數(shù)組中的空缺。如果排序之后的數(shù)組不是連續(xù)的，即相鄰的兩個(gè)數(shù)字相隔若干個(gè)數(shù)字，但只要我們有足夠的?？梢匝a(bǔ)滿這兩個(gè)數(shù)字的空缺，這個(gè)數(shù)組實(shí)際上還是連續(xù)的。舉個(gè)例子，數(shù)組排序之后為{0，1，3，4，5}在 1 和 3 之間空缺了一個(gè) 2，剛好我們有一個(gè) 0，也就是我們可以把它當(dāng)成 2 去填補(bǔ)這個(gè)空缺。

于是我們需要做 3 件事情： 首先把數(shù)組排序，再統(tǒng)計(jì)數(shù)組中 0 的個(gè)數(shù)，最后統(tǒng)計(jì)排序之后的數(shù)組中相鄰數(shù)字之間的空缺總數(shù)。如果空缺的總數(shù)小于或者等于 0 的個(gè)數(shù)，那么這個(gè)數(shù)組就是連續(xù)的：反之則不連續(xù)。

最后，我們還需要注意一點(diǎn)： 如果數(shù)組中的非 0 數(shù)字重復(fù)出現(xiàn)，則該數(shù)組不是連續(xù)的。換成撲克牌的描述方式就是如果一副牌里含有對子，則不可能是順子。

算法實(shí)現(xiàn)

import java.util.Arrays;
public class Test44 {
    /**
     * 題目：從撲克牌中隨機(jī)抽5張牌，判斷是不是一個(gè)順子， 即這5張牌是不是連續(xù)的。
     * 2～10為數(shù)字本身， A為1。 J為11、Q為12、 為13。小王可以看成任意數(shù)字。
     * @param numbers
     * @return
     */
    public static boolean isContinuous(int[] numbers) {
        if (numbers == null || numbers.length != 5) {
            return false;
        }
        // 對元素進(jìn)行排序
        Arrays.sort(numbers);
        int numberOfZero = 0;
        int numberOfGap = 0;
        for (int i = 0; i < numbers.length && numbers[i] == 0; i++) {
            numberOfZero++;
        }
        // 第一個(gè)非0元素的位置
        int small = numberOfZero;
        int big = small + 1;
        while (big < numbers.length) {
            if (numbers[small] == numbers[big]) {
                return false;
            }
            numberOfGap += (numbers[big] - numbers[small] - 1);
            small = big;
            big++;
        }
        return numberOfGap <= numberOfZero;
    }
    public static void main(String[] args) {
        int[] numbers1 = {1, 3, 2, 5, 4};
        System.out.println(isContinuous(numbers1));
        int[] numbers2 = {1, 3, 2, 6, 4};
        System.out.println(isContinuous(numbers2));
        int[] numbers3 = {0, 3, 2, 6, 4};
        System.out.println(isContinuous(numbers3));
        int[] numbers4 = {0, 3, 1, 6, 4};
        System.out.println(isContinuous(numbers4));
        int[] numbers5 = {1, 3, 0, 5, 0};
        System.out.println(isContinuous(numbers5));
        int[] numbers6 = {1, 3, 0, 7, 0};
        System.out.println(isContinuous(numbers6));
        int[] numbers7 = {1, 0, 0, 5, 0};
        System.out.println(isContinuous(numbers7));
        int[] numbers8 = {1, 0, 0, 7, 0};
        System.out.println(isContinuous(numbers8));
        int[] numbers9 = {3, 0, 0, 0, 0};
        System.out.println(isContinuous(numbers9));
        int[] numbers10 = {0, 0, 0, 0, 0};
        System.out.println(isContinuous(numbers10));
        int[] numbers11 = {1, 0, 0, 1, 0};
        System.out.println(isContinuous(numbers11));
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/62.png" alt="" />