2016-09-13 数组

[dayang]

41. First Missing Positive 39. Combination Sum

[zhaokuohaha]

41 - C

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        if(nums.Length==0) return  1;
        bool[] res = new bool[nums.Length+1];
        res[0] = true;
        foreach(int item in nums){
            if(item>0 && item < res.Length){
                res[item] = true;
            }
        }
        for(int i=0; i<res.Length; i++){
            if(! res[i]) return i;
        }
        return nums.Length+1;
    }
}

[zhaokuohaha]

39 - C

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        List<IList<int>> res = new List<IList<int>>();
        List<int> combination = new List<int>();
        Array.Sort(candidates);
        dfs(candidates, target, res, combination, 0);
        return res;
    }

    private void dfs(int[] candidates, int target, List<IList<int>> res, List<int> combination,  int start){
        if(target == 0){
            res.Add(new List<int>(combination));
            return;
        }

        for(int i=start; i != candidates.Length && target >= candidates[i]; i++){
            combination.Add(candidates[i]);
            dfs(candidates, target-candidates[i], res, combination, i);
            combination.Remove(combination.Last());
        }   
    }
}

[SnackMen]

/*
*[AC]41. First Missing Positive
*/
public class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums.length==0)
            return 1;
        Arrays.sort(nums);
        if(nums[nums.length-1]<0)
            return 1;
        int num=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=0)
                continue;
            else{
                if(nums[i]-num>1){
                    break;
                }
                else{
                    num=nums[i];
                }
            }
        }
        return num+1;
    }
}

[SnackMen]

/*
*[AC]39. Combination Sum
*/
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList();
        if(candidates==null || candidates.length==0)
            return lists;
        List<Integer> targetList = new ArrayList();
        Arrays.sort(candidates);
        sum(candidates,target,0,targetList,lists);
        return lists;
    }

    public void sum(int []candidates,int target,int num,List<Integer> targetList,List<List<Integer>>lists){
        if(target == 0){
            List<Integer> list = new ArrayList<Integer>(targetList);
            lists.add(list);
            return;
        }

        for(int i=num;i<candidates.length;i++){
            if(target<candidates[i])
                return;
            targetList.add(candidates[i]);
            sum(candidates,target-candidates[i],i,targetList,lists);
            targetList.remove(targetList.size()-1);
        }
    }
}