欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

正数数组的最小不可组成和问题

程序员文章站 2024-02-03 11:21:28
...

问题描述:

  • 给定一个正数数组arr, 其中所有的值都为整数, 以下是最小不可组成和的概念:把arr每个子集内的所有元素加起来会出现很多值, 其中最小的记为
    min, 最大的记为max。在区间[min,max]上, 如果有数不可以被arr某一个子集相加得到, 那么其中最小的那个数是arr的最小不可组成和。在区间[min,max]上, 如果所有的数都可以被arr的某一个子集相加得到, 那么max+1是arr的最小不可组成和。请写函数返回正数数组arr的最小不可组成和。
  • 例子:arr=[3,2,5]。 子集{2}相加产生2为min, 子集{3,2,5}相加产生10 max。 在区间[2,10]上, 4、 6和9不能被任何子集相加得到, 其中4是arr的最小不可组成和。arr=[1,2,4]。 子集{1}相加产生1为min, 子集{1,2,4}相加产生7为max。 在区间[1,7]上, 任何数都可以被子集相加得到, 所以8是arr的最小不可组成和。
  • 牛客链接
  • 进阶问题:
    • 如果已知正数数组arr中肯定有1这个数, 是否能更快地得到最小不可组成和?

解题思路

  • 第一时间看到这个题,想到了一个经典的DP问题,用某个数组中的数是否能累加成target。该题与那题类似,只不过对从min到max每次都执行一遍该函数,看能否累加出来,显然复杂度过高。
  • 该题有三种解法(具体细节参考代码注释):
    • 递归
    • 动态规划(二维数组)
    • 动态规划(压缩矩阵,一维数组)
  • 对于进阶问题,可以先对该数组排序,然后用变量range表示用(0~i)位置能累加出的范围。即(1~range)范围内的数全部可以用(0~i)位置上的数累加出来,如数组[1,2,5],起初对于1而言,range为1,向后遍历,对于2而言,2<=range+1,则2对应的range更新为range+arr[i],为3,说明用[1,2]能加出1~3范围上的数。然而对于5,5>range+1,说明用[1,2,5]累加不出(1~range+arr[i] = 8)内的全部元素,因为出现了断层,断点便是range+1(4)处,所以该值便是最小不可组成和。若遍历数组到最后,也没有出现断点,那么此时range便是该数组的累加和,最小不可组成和便是range+1。

经验教训

  • dp问题的压缩矩阵问题(具体看代码实现)

代码实现

  • 递归方法
/*
     * 法1: 递归方法:
     *  0~i位置上已经完成决策,和为 preSum,决定i位置上的元素要还是不要。
     *  每次面临两个选择,向下不断分支(类似二叉树),最终决策完成。将最终的和加入set中。set中便存储了所有可能的子序列累加和。
     *  然后找到min与max,从中遍历,查找是否在set中。
     */
    public static int unformedSum1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        HashSet<Integer> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0;i < arr.length;i++) {
            min = Math.min(min, arr[i]);
            max += arr[i];
        }
        process(arr,0,0,set);
        for (int num = min + 1; num <= max; num++) {
            if (! set.contains(num)) {
                return num;
            }
        }
        return max + 1;

    }

    public static void process(int[] arr,int i,int preSum,HashSet<Integer> set) {
        //决策结束,把决策累加的和加入set中
        if (i == arr.length) {
            set.add(preSum);
            return;
        }
        //不要当前元素
        process(arr,i+1,preSum,set);
        //要当前元素
        process(arr,i+1,preSum + arr[i],set);
    }
  • 动态规划(二维数组)
/*
     * 法2:动态规划(未压缩矩阵,二维数组):
     *  dp[i][j]表示arr[0~i]*选择,看能否累加出j,所以i的取值范围为0~arr.length-1,j取值范围为0~max
     *  注意和str1有多少个字序列等于str2那一道题的dp方法区分,因为那一道题要考虑空串的情况,该题不用,当然,也可以考虑。
     *  依赖关系:dp[row][col] = dp[row-1][col]||dp[row-1][col-arr[row]]
     *  注意这种依赖关系,先填好第一行,第一列,然后从上到下,从左到右填满整个数组
     */
    public static int unformedSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0;i < arr.length;i++) {
            min = Math.min(min, arr[i]);
            max += arr[i];
        }
        boolean[][] dp = new boolean[arr.length][max+1];
        //初始化第一行,第一行除了dp[0][0],dp[0][arr[0]],其他都是false,
        dp[0][arr[0]] = true;
        //初始化第一列,当然,第一列不初始化也可以
        for (int row = 0; row < dp.length; row++) {
            dp[row][0] = true;
        }
        //根据依赖关系,填好其他位置,并注意判断越界问题
        for (int row = 1; row < dp.length; row++) {
            for (int col = 1; col < dp[0].length; col++) {
                if (col - arr[row] >= 0) {
                    dp[row][col] = dp[row-1][col]||dp[row-1][col-arr[row]];
                }else {
                    dp[row][col] = dp[row-1][col];
                }
            }
        }
        for (int num = min + 1; num <= max; num++) {
            if (! dp[dp.length - 1][num]) {
                return num;
            }
        }
        return max + 1;

    }
  • 动态规划(一维数组)
/*
     * 法3:动态规划(压缩矩阵,一维数组)
     *  观察依赖关系,只是上下行的关系,第i行元素的值只依赖上一行的值,并且最终要求的是最后一行的值,此时前面所有的行便没有作用。
     * 所以可以只用一行来保存当前值,即假设上一行元素为dp[],那么计算当前行时,直接用该数组,但是这样会引起一个问题,以怎么的顺序
     * 更新该行,原则便是如果旧的dp[i]还有用,一定不能用新值覆盖旧值,填入新的dp[i]时,一定确保旧的dp[i]已经没有用处了。
     *  
     */
    public static int unformedSum3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0;i < arr.length;i++) {
            min = Math.min(min, arr[i]);
            max += arr[i];
        }
        boolean[] dp = new boolean[max + 1];
        //初始化
        dp[0] = true;
        dp[arr[0]] = true;
        //还需要决策 arr.length - 1 次
        for (int i = 1;i < arr.length; i++) {
            //对于第i个字符,选择要还是不要
            for (int col = dp.length - 1; col-arr[i] >= 0; col--) {
                dp[col] = dp[col - arr[i]] ? true : dp[col];
            }
            //等同于下列代码
            /*for (int col = dp.length; col >= 0;col--) {
                if (col - arr[i] >= 0) {
                    dp[col] = dp[col - arr[i]]||dp[col];
                }else {
                    dp[col] = dp[col];
                }
            }*/
        }
        for (int num = min + 1; num <= max; num++) {
            if(! dp[num]) {
                return num;
            }
        }
        return max + 1;
    }
  • 进阶问题
/*
     * 解决进阶问题:
     */
    public static int unformedSum4(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        Arrays.sort(arr);
        int range = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] <= range + 1) {
                range = range + arr[i];
            }else {
                return range + 1;
            }
        }
        return range + 1;
    }