⭐️求正数数组的最小不可组成和⭐️

🔐题目详情

给定一个全是正数的数组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的最小不可组成和。

链接：求正数数组的最小不可组成和

💡解题思路

基本思路： 动态规划
解题思路：

题目让我们得到数组arr的最小不组成和，对于最小不组成和，题目给出的条件如下：

• 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max；
• 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和；
• 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和。

解决这道题的基本思路为：

第一步，求区间的最小子集和min（其实就是数组中最小的元素）和最大子集和max（其实就是数组中所有元素的和）。
第二步，遍历[min, max]，判断区间内是否存在不可组成的和，找到第一个不可组成和就是最小的最小不可组成和。
第三步，对于判断某个数k是否是arr的子集和，本质上就是在数组arr中选择若干个数，看这若干个数的和是否能凑成k，那这个问题就是0-1背包问题，问题到这里转换成【在数组中选择若干个数，判断这个数是否恰好为k】。

对于【在数组中选择若干个数，判断这个数是否恰好为k】问题，我们考虑动态规划：

状态定义： 不妨定义 $f[i][j]$表示从前 $i$个元素中选择若干个数，其和是否恰好为 $j$。

确定初始状态： 当 $j=0$时，不论 $i$为多少，不选择元素都可以使其和恰好为 $0$，即 $f[i][0]=true$。

状态转移方程： 对于数组中的第 $i$个元素 $val$，我们可以选择也可以不选择，若选择 $f[i][j]=f[i-1][j-val], j >= val$，若不选择， $f[i][j]=f[i-1][j]$，两种选择中只要任意一个为 $true$，则 $f[i][j]=true$。

综合起来， $f[i][j]=f[i-1][j] || f[i-1][j-val]$。

优化：

我们发现 $f[i][j]$依赖于 $f[i-1][j]$和 $f[i-1][j-val]$，就是依赖于上一行在 $j$列前面的数，根据这个特点我们可以直接优化为一个一维数组，我们从 $k$的位置开始从后往前更新 $f[i][j]$。

优化后的数组设为 $f[j]$表示数组和是否能够恰好凑成 $j$，根据优化思路不难得到新的状态转移方程为 $f[j]=f[j]||f[j-val]$，需要从右往左遍历数组才行。

初始状态 $f[0]=true$。

🔑源代码

import java.util.*;
public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
	public int getFirstUnFormedNum(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            if (arr[i] < min) min = arr[i];
            max += arr[i];
        }
        //判断是否为最小组成和
        int ans = max + 1;
        for (int i = min + 1; i <= max; i++) {
            if (!isSum(arr, i)) {
                ans = i;
                break;
            }
        }
        return ans;
	}
    private static boolean isSum(int[] arr, int k) {
        //状态定义
        int n = arr.length;
        boolean[] dp = new boolean[k + 1];
        //确定初始状态
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int val = arr[i];
            for (int j = k; j >= val; j--) {
                dp[j] = dp[j] || dp[j - val];
            }
        }
        return dp[k];
    }
} 

🌱总结

本题为动态规划0-1背包问题，考察状态抽象，状态方程的推导。

⭐️有假币⭐️

🔐题目详情

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

输入描述:

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

输出描述:

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

示例1

输入

3
12
0

输出

1
3

链接：有假币
来源：牛客网

💡解题思路

基本思路： 数学推理题

解题思路：
先简单说一下题目的要求，根据输入的正整数n，表示一共有n枚货币，其中有一枚是假的，题目说假币的重量比真币的重量要轻，并且给我们一个天平，求最快找出假币的最大称量次数。

我们能使用的工具是天平，最快的方案就是先尽可能找出两堆相等货币进行称量，那么至少的将货币分为3堆，并且分为3堆也是最快的，不妨设货币的总数为n，那么有以下几种情况：

• n % 3 == 0，这种情况货币可以均分，为 $\frac{n}{3}, \frac{n}{3}, \frac{n}{3}$，第一次天平称量之后，若前两堆的重量不同，那假币就在较轻重量的一堆里，此时剩余货币为 $\frac{n}{3}$，若前两堆重量相同，那就是假币一定就在第三堆，此时剩余的货币也是 $\frac{n}{3}$，然后我们再将这 $\frac{n}{3}$个货币以同样的方式分为3组，继续以相同的规则比较，换句话说称一次可以排除 $2/3$的货币。
• n%3==1，这种情况分组为 $\frac{n}{3}, \frac{n}{3}, \frac{n}{3}+1$，同理前两组重量不相同，剩余的货币为 $\frac{n}{3}$，相同剩余的货币为 $\frac{n}{3}+1$，我们按照最坏情况考虑，此时剩余的货币为 $\frac{n}{3}+1$。
• n%3==2，这种情况分组为 $\frac{n}{3}+1, \frac{n}{3}+1, \frac{n}{3}$，同理前两组重量不相同，剩余的货币为 $\frac{n}{3} + 1$，相同剩余的货币为 $\frac{n}{3}$，我们按照最坏情况考虑，此时剩余的货币为 $\frac{n}{3}+1$。

综上所述，如果 $n$能够被 $3$整除，计数器加 $1$， $n$更新为 $\frac{n}{3}$，继续同样的操作，如果 $n$能够被 $3$整除，计数器加 $1$， $n$更新为 $\frac{n}{3} + 1$，继续同样的操作。

🔑源代码

Java代码实现：

// write your code here
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) break;
            int ans = 0;
            while (n > 1) {
                ans++;
                n = n / 3 + (n % 3 == 0 ? 0 : 1);
            }
            System.out.println(ans);
        }
    }
}

C++版本代码：

// write your code here cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        int ans = 0;
        while (n > 1) {
            ans++;
            n = n / 3 + (n % 3 == 0 ? 0 : 1);
        }
        cout << ans << endl;
    }
}

🌱总结

本题为数学推理题，考察数学逻辑思维能力和数学归纳能力。