BAT实习内推笔试卷（第一场）

import java.util.Arrays;import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class Solution {/*** 正数数组中的最小不可组成和* 输入：正数数组arr* 返回：正数数组中的最小不可组成和*/public int getFirstUnFormedNum(int[] arr) {int len=arr.length;if(len==0){return 0;}if(len==1){return arr[0]+1;}Arrays.sort(arr);if(len==2){return arr[1]-arr[0]==1?arr[1]+1:arr[0]+1;}int min=arr[0];int max=arr[len-1];int sum=0;for(int i=0;i<arr.length;i++){sum+=arr[i];}int[] flag=new int[sum-min+1];Set<Integer> integers=new HashSet<Integer>();integers.add(arr[0]);integers.add(arr[1]);integers.add(arr[1]+arr[0]);int set_max=arr[1]+arr[0];setFlag(arr[0],min,flag);setFlag(arr[1],min,flag);setFlag(set_max,min,flag);for(int i=2;i<len;i++){int temp=arr[i];Set<Integer> temp_set=new HashSet<Integer>(integers);temp_set.add(temp);setFlag(temp,min,flag);for (Iterator iterator = integers.iterator(); iterator.hasNext();) {int v = (Integer) iterator.next();temp_set.add(v+temp);setFlag(v+temp,min,flag);}set_max+=temp;integers=temp_set;int res=judge(flag,temp-min);if(res!=-1){return res+min;}}int res=judge(flag,sum-min);if(res!=-1){return res+min;}return sum+1;}private int judge(int[] flag, int max) {for(int i=0;i<max;i++){if(flag[i]==0){return i;}}return -1;}private void setFlag(int i, int min, int[] flag) {flag[i-min]=1;}}

，看着它洗涤一缕缕阳光，看着它映衬一片片星辉，