题解 | #扔骰子#

题意整理

牛妹和牛牛在玩掷骰子游戏，看谁能够获胜。
得分规则为，给定每一次所掷的骰子点数，这些点数可以随意组合相加得到一些数，从1开始计算，如果某个数不在这些组合得到的数中，则这个数就是他的得分。

方法一（有序哈希）

1.解题思路

首先定义一个TreeSet，用于存放所有可能的累加和，并保证累加和是有序的。
然后遍历整个数组，将可能的累加和放入TreeSet。
最后遍历TreeSet，看其中是否包含不能得到的累加和，由于是有序排列的，所以第一个不能得到的累加和，即是所求的分数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param b int整型一维数组 b
     * @return string字符串
     */
    public String Throwdice (int n, int m, int[] a, int[] b) {
        //如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
        return getScore(a,n)>getScore(b,n)?"Happy":"Sad";
    }

    //计算牛牛或牛妹的得分
    private int getScore(int[] nums,int n){
        //记录所有可能的求和，并保证这些值是有序的
        Set<Integer> set=new TreeSet<>();
        //枚举出所有可能的累加和
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                set.add(sum);
            }
        }

        int cur=1;
        for(Integer num:set){
            //如果当前累加和存在，cur自增1
            if(num==cur){
                cur++;
            }
            //如果不存在，返回cur
            else{
                return cur;
            }
        }
        return cur;
    }
}

3.复杂度分析

时间复杂度：遍历nums数组时，使用了两层循环，内层循环里每次将累加和放入TreeSet，由于往TreeSet插入元素的时间复杂度为 $图片说明$ ，（k是所有累加和的数目），总共插入了 $图片说明$ 次，所以总的时间复杂度是 $图片说明$ 。
空间复杂度：需要额外大小为k的TreeSet集合，所以空间复杂度为 $图片说明$ 。

方法二（排序+贪心）

1.解题思路

首先对nums数组进行排序，保证累加和是从小到大递增的
然后遍历整个nums数组，之前所有累加和的取值范围在 $[1,sum]$ ，新增 $nums[i]$ 之后，新增的范围在 $[nums[i],nums[i]+sum]$ ，要向包含从1开始的所有数字，那么 $nums[i]$ 必然要小于等于 $sum+1$ 。所以，如果当前 $nums[i]>sum+1$ ，那么 $[nums[i],nums[i]+sum]$ 与 $[1,sum]$ 之间就缺了一个 $sum+1$ ，即找到第一个不能得到的累加和。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param b int整型一维数组 b
     * @return string字符串
     */
    public String Throwdice (int n, int m, int[] a, int[] b) {
        //如果牛妹的得分大于牛牛，则输出Happy，否则输出Sad
        return getScore(a,n)>getScore(b,n)?"Happy":"Sad";
    }

    private int getScore(int[] nums,int n){
        //对数组进行排序
        Arrays.sort(nums);
        //记录累加和
        int sum=0;
        for(int i=0;i<n;i++){
            //如果当前nums[i]>sum+1，那么[nums[i],nums[i]+sum]与[1,sum]之间就缺了一个sum+1
            if(nums[i]>sum+1){
                break;
            }
            sum+=nums[i];
        }
        return sum+1;
    }
}

3.复杂度分析

时间复杂度：只需遍历nums数组一次，时间复杂度 $O(n)$ ，但是需要进行排序预处理，排序的时间复杂度是 $O(nlog_2n)$ ，所以最终的时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为 $O(1)$ 。