题解 | #扔骰子#

题目描述
牛妹在和牛牛玩扔骰子，他们的游戏规则有所不同；
每个人可以扔n次m面骰子，来获得n个数
得分为任意选取n个数中的某些数求和所不能得到的最小的正整数
得分大的人获胜
例如扔骰子3次得到了 1 2 5，那么这个人的得分是4

牛妹想知道这回合她是否能赢
牛妹的n个数存在数组a中，牛牛的n个数存在数组b中
数组下标从0开始

如果牛妹能在这回合胜利则输出Happy，否则输出Sad

方法一：哈希解法

求解思路
对于求解本题牛妹能否在这回合胜利，我们想到使用哈希的做法来求解，首先我们定义一个数组，用来存放所有的累加和，并且保证这个数组是增序的。然后我们遍历整个数组，求出所有的累加和，然后将累加和与题目输入的数据进行比较，当出现第一个与数组元素不同的值，则是我们所要求的分数。

图片说明

解题代码

import java.util.*;
public class Solution {
    public String Throwdice (int n, int m, int[] a, int[] b)
    {
        return getScore(a,n)>getScore(b,n)?"Happy":"Sad"; // 如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
    }
    private int getScore(int[] nums,int n) // 计算牛牛或牛妹的得分
    {   //记录所有可能的求和，并保证这些值是有序的
        Set<Integer> myset=new TreeSet<>();
        for(int i=0;i<n;i++)
        {   //枚举出所有可能的累加和
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=nums[j];
                myset.add(sum); // 记录累加和
            }
        }
        int mycur=1;
        for(Integer num:myset)
        {   //如果当前累加和存在，cur自增1
            if(num==mycur)
            {
                mycur++;
            }
            else //如果不存在，返回cur
            {
                return mycur;
            }
        }
        return mycur; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环加一层内插元素，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用myset数组，因此空间复杂度为 $O(N)$

方法二：贪心的思想求解

求解思路
对于本题目我们也可以采用贪心的思想进行求解，首先我们对题目所给的输入进行排序，保证累加和是从小到大的递增顺序，然后遍历递增顺序的数组，保证新增的数字在原范围的基础上加1之内，这样遍历题目所给的数组，当出现第一个不在原范围加1的数字，那么就输出它，最终得到本问题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public String Throwdice (int n, int m, int[] a, int[] b)
    {
        return getScore(a,n)>getScore(b,n)?"Happy":"Sad"; //如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
    }
    private int getScore(int[] nums,int n)
    {   //对数组进行排序
        Arrays.sort(nums);
        //记录累加和
        int mysum=0;
        for(int i=0;i<n;i++)
        {   //如果当前nums[i]>sum+1，那么[nums[i],nums[i]+sum]与[1,sum]之间就缺了一个sum+1
            if(nums[i]>mysum+1)
            {
                break;
            }
            mysum+=nums[i]; // 继续累加求和
        }
        return mysum+1; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环内嵌一次排序，因此时间复杂度为 $O(nlogn)$
空间复杂度：使用常数级内存空间，因此空间复杂度为 $O(1)$