题解 | #扑克牌顺子#

扑克牌顺子

http://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4

题意理解

5张扑克牌对应5个数,包含0~13。其中0可以表示1~13之间的任意数字。判断这5个数字是否连成1~13之内的顺子。

方法一

对于5个数字是否能连成顺子,主要观察两方面:
(1)如果有重复的数字(0除外),则必然不可能连成顺子。
(2)如果最大值和最小值(0除外)的差大于等于5,则必然不可能连成顺子。(3个数填不满中间的间隔)

对于算法的正确性:
在满足条件1的情况下,假设存在i(i<5)个0,对于剩下5-i个数,如果满足条件2,即它们的极差为(4-i)~4。
当极差为4的时候,把i个0填在中间;
当极差变小的时候,i个0一部分填在中间,一部分填在max或者min的外侧即可。(因为数组长度为5,远小于13,所以如果max为13,则min外侧可用0代替;如果min是1,则max外侧可用0代替)。
示意图如下:
图片说明
具体代码如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        vector<int> exist(14,-1);//定义一个数组用来判断某个数字是否出现过
        int minm = 14, maxm = -1;
        //遍历数组,找到最值
        for (int i=0;i<numbers.size();i++) {
            if (numbers[i] == 0) {
                continue;
            }
            if (exist[numbers[i]] != -1) return false;
            exist[numbers[i]] = 1;
            if (minm > numbers[i]) minm = numbers[i];
            if (maxm < numbers[i]) maxm = numbers[i];
        }
        if (maxm - minm < 5) return true;
        return false;
    }
};

时间复杂度:。只是遍历了一遍数组。
空间复杂度:。创建了新数组exist,用来记录数字是否有重复的情况。

方法二

对数组进行排序,找出最值,注意要排除0。同样是根据方法一中的两个条件进行判断。
注意,排序之后如果出现重复的情况,则重复的两个数必然是相邻的。

具体代码如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        sort(numbers.begin(), numbers.end());
        int index = 0;// index记录第一个非0数值出现的位置
        for (int h=0; h<numbers.size(); h++) {
            if (!numbers[h]) {
                index++; 
                continue;
            }
            //注意范围不能越界.&&的先后顺序不能错
            if (h<numbers.size()-1 && numbers[h] == numbers[h+1]) return false;
        }
        //判断极差的大小
        if (numbers.back() - numbers[index] <= 4) {
            return true;
        }
        else return false;
    }
};

时间复杂度:。排序的时间为,之后遍历一遍数组。
空间复杂度:。没有开辟任何新的空间。

全部评论

相关推荐

头像
11-07 01:12
重庆大学 Java
精致的小松鼠人狠话不多:签哪了哥
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务