树根_有假币_求正数数组的最小不可组成和

数根

数根

// 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()){//只能用str保存或者大数!
            String str = sc.nextLine();
            //我们需要将每一位相加即可!
            int result = 0;
           do{
               result = 0;//将和重置为0!!!
               for(int i = 0;i< str.length();i++){
                   //将各位相加!
                   result = result + (str.charAt(i) - '0');
               }
               //将 result 转成字符串继续相加!
               str = result + "";
           }while(result>9);
            System.out.println(result);
        }
    }
}

有假币

有假币

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

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

import java.util.*;
public class Solution {
    /**
     *    正数数组中的最小不可组成和
     *    输入：正数数组arr
     *    返回：正数数组中的最小不可组成和
     */
    public void getNumber(int[] arr,ArrayList<Integer> result,int pos,int sum){
        if(pos==arr.length){
            return;
        }
        for(int i = pos;i<arr.length;i++){
            sum += arr[i];
            result.add(sum);
            getNumber(arr,result,i+1,sum);
            sum -= arr[i];
        }
    }
    public int getFirstUnFormedNum(int[] arr) {
         //2种情况: 1.[min,max] 有正数不能被子集相加得到! 返回该 数
         //        2.[min,max] 所以正数都能被子集相加得到 返回 max+1
        Arrays.sort(arr);
        int min = arr[0];
        int max = arr[0];
        ArrayList<Integer> result = new ArrayList<>();
        getNumber(arr,result,0,0);
        for(int i = 1;i<arr.length;i++){
            max += arr[i];
        }
        for(int i = min+1;i<max;i++){
            if(!result.contains(i)){
                return i;
            }
        }
        return max+1;
    }
}