【Java版oj】day29求正数数组的最小不可组成和、有假币

浅浅的花香味﹌ 2024-03-24 17:06 11阅读 0赞

**目录**

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

（1）原题再现

（2）问题分析

（3）完整代码

二、有假币

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、求正数数组的最小不可组成和 ##
> 
> ### （1）原题再现 ###
> 
> [求正数数组的最小不可组成和\_百度笔试题\_牛客网][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的最小不可组成和。
> 
> ### （2）问题分析 ###
> 
> 其实这就是一道找寻所有组合可能的情况的题。
> 
> 例如数组\{3,2,4\}，可能的集合为\{3\}，\{2\}，\{4\}，\{3,2\}，\{3,4\}，\{2,4\}，\{3,2,4\}（不包含空集）。得到的和经过排序为2，3，4，5，6，7，9。8不在连续的当中，所以输出8。
> 
>  **这里我其实利用了动态规划的思想，但是没有用状态方程求解，而是遍历寻找 。我们知道Set集合有去重的功能，所有我们就用这个保存所有组合情况的和。首先第一步先将0 添加进集合，每次将数组中一个数与集合中的每一个数进行求和运算，并把结果放在队列中。还以数组\{3,2,4\}为例，第一个数3与0进行运算，此时队列中就有3。队列不为空，删去队列中的数并将其放入集合中。这时，集合里就有0,3。其次第二步将数组中下一个数与集合中的每一个数进行求和运算，2+0=2,2+3=5，加入队列，删除队列中元素加入集合。接着第三步将数组中下一个数与集合中的每一个数进行求和运算,4+0=0,4+3=7,4+2=6,4+5=9。最后数组遍历完毕，删去s集合中一开始加入的0。**
> 
> 大家可能疑惑的点，如果数组里有0，set又有去重功能，最后再把0删去不就少了一种情况嘛？这种可能是不可能的，因为题目要求全是正数。
> 
> 第二要额外定义一个链表，不能直接加入集合吗，当然不行，set集合的循环在内层，如果每次都直接加入进去，set集合的长度就不断的在改变。造成死循环。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     /*
>      * 求正数数组的最小不可组成和
>      */
>     public class Solution {
>         public int getFirstUnFormedNum(int[] arr) {
>             Set <Integer> set = new HashSet<>();
>             Deque <Integer>queue = new LinkedList<>();
>             int len = arr.length;
>             set.add(0);
>             for (int i = 0; i < len; i++) {
>                 for (int j : set) {
>                     queue.offer(arr[i] + j);
>                 }
>                 while (!queue.isEmpty()) {
>                     set.add(queue.poll());
>                 }
>             }
>             set.remove(0);
>             Object[]setArr = set.toArray();
>             Arrays.sort(setArr);
>             int min = (int)setArr[0];
>             int max = (int)setArr[setArr.length - 1];
>             for (int k = min; k <= max; k++) {
>                 if (!set.contains(k)) {
>                     return k;
>                 }
>             }
>     
>             return max + 1;
>         }
>     }
> 
> ![4ae3d88d928042c7ab26adebb5959367.png][]

> ## 二、有假币 ##
> 
> ### （1）原题再现 ###
> 
> [有假币\_\_牛客网][Link 2]
> 
> 居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder 一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。
> 
> **输入描述:**
> 
> 1≤n≤2^30,输入0结束程序。
> 
> **输出描述:**
> 
> 最多要称几次一定能把那个假币找出来？
> 
> 示例1
> 
> 输入
> 
> 3
> 
> 12
> 
> 0
> 
> 输出
> 
> 1
> 
> 3
> 
> ### （2）问题分析 ###
> 
> 是很经典的一道题目。不是用二分法，而是每次都将硬币分成3份。我感觉第一次很难有人直接想出来要分三次。
> 
> 对于 1个硬币，称量 0次。  
> 对于 2个硬币，称量 1次。  
> 对于 3个硬币，称量 1次。  
> 对于 4个硬币，称量 2次，先分成（2，2，0），第一次称量前两份（2，2），如果重量不一样，再次求出判断另外2个硬币需要称量的次数。  
> 对于 5个硬币，称量 2次，先分成（2，2，1），第一次称量前两份（2，2），如果重量不一样，再次判断另外1个硬币需要称量的次数。  
> 对于 6个硬币，称量 2次，先分成（2，2，2），第一次称量前两份（2，2），如果重量不一样，再次判断求出另外2个硬币需要称量的次数。  
> 对于 7个硬币，称量 2次，先分成（3，3，1），第一次称量前两份（3，3），如果重量不一样，再次判断求出另外3个硬币需要称量的次数。  
> 每次都将称量的硬币分成3份，要求前两份的个数不小于第三份。如果前两份重量是一样，则假币在第三份中，这样可以除去2/3的硬币；如果前两份重量不一样，那么假币在重量轻的一份中，这样也可以除去2/3的硬币。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     import java.util.zip.CheckedOutputStream;
>     
>     /*
>      * 有假币
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int n = sc.nextInt();
>                 if (n == 0) {
>                     return ;
>                 }
>                 System.out.println(fun(n));
>             }
>         }
>         public static int fun(int n) {
>             int count = 0;
>             if (n == 1) {
>                 return 0;
>             }
>             if (n <= 3) {
>                 return 1;
>             }
>             int part = (n + 2) / 3;
>             int left = n - part * 2;
>             count = Math.max(fun(part), fun(left)) + 1;
>             return count;
>         }
>     }
> 
> ![b6e9e731543c4cc8804cfebe907e76e4.png][]

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

![a22f1c698f4e4a30883ad2fabe013bf9.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
[4ae3d88d928042c7ab26adebb5959367.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c557d2e2588c4ab9aab0b4da7f511140.png
[Link 2]: https://www.nowcoder.com/questionTerminal/1d18c0841e64454cbc3afaea05e2f63c
[b6e9e731543c4cc8804cfebe907e76e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/57df5f9ca142406bbdf0442e3e9d1412.png
[a22f1c698f4e4a30883ad2fabe013bf9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/462b7a32226149c78a9b1a5877a574be.png