【算法刷题日记之本手篇】求正数数组的最小不可组成和与有假币

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【求正数数组的最小不可组成和】和【有假币】，展示语言java。

小贴士：本专栏所有题目来自牛客->面试刷题必用工具

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年9月28日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬推荐在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：

注册地址：牛客网

有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。

---

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

🔐题目详情

给定一个全是正数的数组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 
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;
    }
}

🌱总结

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

---

到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！
后记区

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！