题目描述

每个人可以扔次面骰子，来获得个数
得分为任意选取个数中的某些数求和所不能得到的最小的正整数
问数组的得分与数组得分的大小关系

方法一 有序哈希表

解题思路

可以考虑使用C++的STL中的有序set存放每个数组可以得到的所有整数,然后遍历该set,找到不连续的最小正整数即为该数组的得分.
得到所有求和数很简单,两层循环即可做到.为了找到set中最小的不连续的正整数,比较直接的方法是从开始枚举,但是这样每次枚举需要在set中执行find操作,时间复杂度过高.一个优化方法是遍历一遍有序set,并且定义一个指针,每迭代一次加,看迭代的数组是否是,以此判断是否连续.
以数组为为例,进行第二次迭代时,,set中的数字为,出现了不连续,所以返回值即为.

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型vector a
     * @param b int整型vector b
     * @return string字符串
     */
    // n:数组长度,a:数组
    // return:数组a的得分
    int cal(int n, vector<int>& a) {
        // num:用于存储数组a能得到的所有数字的set
        set<int> num;
        // 枚举所有数字
        for(int i = 0; i < n; i++) {
            int sum = 0;
            // 枚举第i个数字之后的数字
            for(int j = i; j < n; j++) {
                sum += a[j];
                num.insert(sum);
            }
        }

        // 遍历set,寻找最小的不连续的正整数
        int ret = 1;
        for(int t : num) {
            // set中存在ret,ret++
            if(t == ret) {
                ret++;
            }
            // set中不存在ret,返回ret
            else {
                return ret;
            }
        }
        return ret;
    }

    string Throwdice(int n, int m, vector<int>& a, vector<int>& b) {
        // 根据a,b得分返回
        if(cal(n, a) > cal(n, b))
            return "Happy";
        else
            return "Sad";
    }
};

复杂度分析

• 时间复杂度：为了找到所有通过求和可以得到的数字,需要对数组进行两层循环的迭代,每次迭代需要在有序哈希表中插入一个数;为了找到set中不连续的最小正整数,需要对set迭代一次,所以时间复杂度为
• 空间复杂度：使用set存储通过求和可以得到的数字,set的最大大小为,所以空间复杂度为

方法二 模拟+贪心

解题思路

可以通过贪心的思路进行模拟.与方法一相同,还是定义函数计算数组的得分.在函数中,先对数组进行排序,然后根据贪心的思路找到答案.具体来说,迭代到第个数时,我们贪心地认为新增加的范围是下图中黄色部分,即到,因为是连续的,所以我们认为区间之内也是连续的.但是如果,与之间的范围就出现了间断,就出现了不连续的情况,这时我们就找到了所需要的最小不连续的整数.根据此思路,我们可以模拟得出答案.

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型vector a
     * @param b int整型vector b
     * @return string字符串
     */
    // n:数组长度,a:数组
    // return:数组a的得分
    int cal(int n, vector<int>& a) {
        // 对数组排序
        sort(a.begin(), a.end());
        // 目前连续区间的上界
        int sum = 0;
        // 遍历数组
        for(int i = 0; i < n; i++) {
            // 数组新添加的区间与目前已有的连续区间之间存在间断
            if(a[i] > sum + 1)
                return sum + 1;
            // 更新连续区间的上界
            sum += a[i];
        }
        return sum + 1;
    }

    string Throwdice(int n, int m, vector<int>& a, vector<int>& b) {
        // 根据a,b得分返回
        if(cal(n, a) > cal(n, b))
            return "Happy";
        else
            return "Sad";
    }
};

复杂度分析

• 时间复杂度：需要对数组a,b分别进行一次遍历和一次排序,时间复杂度为
• 空间复杂度：使用了常数个辅助变量,空间复杂度为