题解 | #扑克牌顺子#

扑克牌顺子

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

解法一:排序

在解决此题目之前,需要明确:在达到何种要求时,会实现「顺子」。

显而易见,当所抽取的非零牌存在重复时,不可能有顺子出现;此外,由于0可以代替任意牌,因此能否组成顺子是由「非零牌」决定的。故,此题的本质是要我们寻找非零牌之间是否满足一定的关系。

题目说明每次抽取牌的数量为5,因此若非零牌中的最大值与最小值之差小于5,则一定会组成顺子

因此,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。

解法一的思路如下:

  1. 将原数组排序(可利用C++内置的sort()方法进行排序);
  2. 可以得到数组中的最大数max(即有序数组的最后一个元素);
  3. 从头开始遍历排序好的数组:
    1. 若遇到0,跳过;
    2. 若遇到重复元素,返回false;
    3. 若max与当前值之差大于4,返回false;
  4. 循环结束时,比满足「最大值与最小值之差小于等于4」、「不存在重复元素」,因此直接返回true。

代码实现如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (!numbers.size())
            return false;
        sort(numbers.begin(), numbers.end());  // 排序
        int i = 0, max_ = numbers[numbers.size() - 1]; // 最大值为数组的最后一个元素
        // 遍历数组
        while (i < numbers.size() - 1) {
            // 跳过0
            if (!numbers[i]) {
                i++; 
                continue;
            }
            // 若有重复,返回false
            if (numbers[i] == numbers[i + 1]) 
                return false;
            // 若最大与最小之差大于4,返回false
            if (max_ - numbers[i] > 4) 
                return false;
            i++;
        } 
        return true;
    }
};

排序算法的平均时间复杂度为O(NlogN),遍历数组时间复杂度为O(N),因此总时间复杂度为O(NlogN)。

该方法未定义额外空间,空间复杂度为O(1)。

解法二:哈希表

可以优化上述方法的时间复杂度至O(N),即不采用排序算法。

如上文所述,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。

因此,通过遍历原数组,并找出其最大值、最小值,即可解决此问题:预先定义变量min、max,分别代表最小值、最大值,并在遍历数组的过程中更新其取值,即可找到整个数组的最大、最小值(非0)。

此题需要注意重复元素的情况,因此引入哈希表便于判断:对于每一个遍历到的元素,在哈希表中进行寻找,若找到,说明有重复,否则将其加入哈希表中。

事例1:
图片说明

事例2:
图片说明

代码如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int max_ = -1, min_ = 14;
        unordered_map<int, int> hash; // 定义哈希表
        for (int i = 0; i < numbers.size(); i++) {
            if (numbers[i]) { // 跳过0
                if (hash.find(numbers[i]) != hash.end()) // 若在哈希表中找到,说明有重复
                    return false;
                hash[numbers[i]] = 1; // 未在哈希表中找到,将其加入哈希表继续遍历
                max_ = max(max_, numbers[i]); // 最大值
                min_ = min(min_, numbers[i]); // 最小值
            }
        }
        if (max_ - min_ <= 4)
            return true;
        return false;
    }
};

此方法仅遍历数组一次,且哈希表的查找复杂度为O(1),故总时间复杂度为O(N);此方法定义了哈希表用来存储元素,因此空间复杂度为O(N)。

全部评论

相关推荐

今天提了离职,领导说让我离职前请几位正式工吃饭……我本来是有请客的打算的,因为感觉这几个同事人还挺好,想以后维持一下关系。但我第一次听领导主动说让实习生请客的……(只因为一个请客,倒不至于发个帖子。主要是这个公司的离谱事情太多了,跟之前的实习感受完全不同)之前几段实习,在实习结束前,mentor或领导会请客欢送,无论是私下吃个便饭也好,还是全部门的奶茶也好。这几位正式工既不是我的mentor,也不是我的领导。而且我异地实习生活很拮据,这家公司给得很少。当然了,这也算意料之外,情理之中。这家公司一直对实习生很不友好。经常让实习生加班,总是跟实习生说“辛苦一下”。你也没给我那个辛苦钱啊!晚上干到12点,周末加班干,要么是领导要看,要么是客户着急。之前的公司,我主动加班,mentor都会跟我说,实习生不用加班,到点下班就行。加班就算了,我安慰自己就当学东西了,锻炼抗压能力。但辛苦完了,节日的福利,竟然只有正式员工才有?!我之前实习,实习生的节日福利一点也不比正式工少啊……有的正式工还会把福利分给实习生一部分。挺心寒的……而且,我觉得这家公司对实习生很不负责,纯拿你当廉价劳动力。可以让刚毕业才工作三个月的人带实习生,实习生不会的,正式员工也不会,俩人就一起探索。还真就那个“和公司共同成长”😅避雷某GJ级专精特新小巨人企业,六百多人,整体氛围挺离谱的,跟我去过的其他公司完全不一样。领导都是些老东西,喜欢PUA,爹味十足。流程混乱、管理混乱、代码混乱、职责混乱,技术领导不懂技术,总说出一些可笑的畅想。虽然技术不咋地,但是把产品技术路线吹上天的本事倒是有,而且很大!什么xx系统、xx模型、xx工具,名字一个比一个高大上,其实可能就是调用Qwen、DeepSeek、Doubao……还声称这两年要上市,我祝你们成功吧😄
不知道怎么取名字_:实习的能有多少钱,为啥要请客
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务