刷题_29：求正数数组的最小不可组成和 and 有假币

向右看齐 2023-09-30 22:21 13阅读 0赞

### 一.求正数数组的最小不可组成和 ###

**题目链接：**

> [求正数数组的最小不可组成和][Link 1]

**题目描述：**

> **给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间\[min,max\]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和； 3，在区间\[min,max\]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = \{3,2,5\} arr的min为2，max为10，在区间\[2,10\]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = \{3,2,4\} arr的min为2，max为9，在区间\[2,9\]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = \{3,1,2\} arr的min为1，max为6，在区间\[2,6\]上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。**

**输入描述：**

> **无**

**输出描述：**

> **无**

**示例1：**

> **无**

**个人总结：**

> **下面…**

**代码实现：**

**回溯**：适用于\[min, max\]区间较小的情况。主要是回溯求得所有的子集和，然后遍历\[min, max\]，判断set集合中是否包含区间内的数字就行了。注意容易错的点：将set数组放入方法中初始化，不然多组数据输入的时候，set不会对每一组数据进行刷新，会一直重复保存导致报错。

import java.util.*;
    public class Solution {
        
    	/**
    	 *	正数数组中的最小不可组成和
    	 *	输入：正数数组arr
    	 *	返回：正数数组中的最小不可组成和
    	 */
        Set<Integer> set = null;
    	public int getFirstUnFormedNum(int[] arr) {
        
    //         Arrays.sort(arr);
            set = new HashSet<>();
            getSet(arr, 0, 0);
            int max = 0;
            int min = arr[0];
            for (int n : arr) {
        
                max += n;
                min = Math.min(min, n);
            }
            int cnt = 0;
            int out = -1;
            for (int i = min; i <= max; i++) {
        
                if (set.contains(i)) {
        
                    cnt++;
                } else {
        
                    out = i;
                    break;
                }
            }
            if (cnt == 0) {
        
                out = min - 1;
            } 
            if (cnt == max - min + 1) {
        
                out = max + 1;
            }
            return out;
        }
        
        public void getSet(int[] arr, int idx, int sum) {
        
            if (idx == arr.length) {
        
                return;
            }
            for (int i = idx; i < arr.length; i++) {
        
                sum += arr[i];
                set.add(sum);
                getSet(arr, i + 1, sum);
                sum -= arr[i];
            }
        }
    }

**01背包**：建一个大小max + 1的dp数组，然后使用01背包判断每个下标能是否能装满，最后判断\[min, max\]是否均满足dp\[i\] == i（装满），按要求输出即可。

import java.util.*;
    
    public class Solution {
        
        /**
         * 正数数组中的最小不可组成和
         * 输入：正数数组arr
         * 返回：正数数组中的最小不可组成和
         */
        public int getFirstUnFormedNum(int[] arr) {
        
            int max = 0;
            int min = arr[0];
            for (int n : arr) {
        
                max += n;
                min = Math.min(min, n);
            }
            int[] dp = new int[max + 1];
            for (int i = 0; i < arr.length; i++) {
        
                for (int j = max; j >= arr[i]; j--) {
        
                    dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
                }
            }
            int cnt = 0;
            int res = 0;
            for (int i = min; i <= max; i++) {
        
                if (dp[i] == i) {
        
                    cnt++;
                } else {
        
                    return i;
                }
            }
            if (cnt == 0) {
        
                res = min - 1;
            }
            if (cnt == max - min + 1) {
        
                res = max + 1;
            }
            return res;
        }
    }

--------------------

### 二.有假币 ###

**题目链接：**

> [有假币][Link 2]

**题目描述：**

> **居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder 一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。**

**输入描述：**

> **1≤n≤2^30,输入0结束程序。**

**输出描述：**

> **最多要称几次一定能把那个假币找出来？**

**示例1：**

> **输入：  
> 3  
> 12  
> 0  
> 输出：  
> 1  
> 3**

**个人总结：**

> **最快的称量方法：分成三堆1，2，3，将1和2称量比较，平衡则在3中，不平衡则在1和2较轻的一堆，然后继续分堆…我们会遇到一种情况，无法平分三堆，那怎么办？这种情况下，我们只可能多出1张或两张币，若我们剩1张，我们将它放到3中，若我们剩两张，我们将它分别放到1和2中，由于题目要求最快的时间，并且是求最多的次数，因此取每次剩余的最大值 1 + (1/3)**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                int n = sc.nextInt();
                if (n != 0) {
        
                    int cnt = 0;
                    while (n >= 2) {
        
                        cnt++;
                        if (n % 3 == 0) {
        
                            n /= 3;
                        } else {
        
                            n = n / 3 + 1;
                        }
                    }
                    System.out.println(cnt);
                }
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
[Link 2]: https://www.nowcoder.com/questionTerminal/1d18c0841e64454cbc3afaea05e2f63c?