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

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

题目链接：

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

题目描述：

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

二.有假币

题目链接：

有假币

题目描述：

居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。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);}}}
}