Leetcode刷题-蒲公英云

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

此题关键采用回溯算法解答

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //先从小到大排序,帮助去重与剪枝优化
        Arrays.sort(candidates);
        recursion(candidates,target,new ArrayList());
        return result;
    }
    List<List<Integer>> result = new ArrayList<>();
    public void recursion(int[] candidates,int target,int index,List<Integer> list){
        //如果target比candidates[index]还小了，没必要再进行下去了
        while(index < candidates.length && target >= candidates[index]){
            if(target == candidates[index]){
                //得出满足条件的集合
                list.add(candidates[index]);
                result.add(list);
                return;
            }else{
                //复制新集合保存结果避免对下一轮递归的影响
                List newList = new ArrayList(list);
                newList.add(candidates[index]);
                recursion(candidates,target - candidates[index],index,newList);
            }
            index++;
        }
    }
}

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

此题还是采用回溯算法，难点在于要考虑结果集去重

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        recursion(candidates, target, 0, new ArrayList());
        return result;
    }
    public void recursion(int[] candidates, int target, int index, List<Integer> list) {
        int start = index;
        while (index < candidates.length &&  target >= candidates[index]) {
            //结果集去重
            if(index > start && candidates[index] == candidates[index - 1]){
                index++;
                continue;
            }
            if (target == candidates[index]) {
                list.add(candidates[index]);
                result.add(list);
                return;
            } else {
                List newList = new ArrayList(list);
                newList.add(candidates[index]);
                recursion(candidates, target - candidates[index], index + 1, newList);
            }
            index++;
        }
    }
}

分苹果

题目:
果园里有一堆苹果，一共n头（n小于9且大于1）熊来分，第一头将苹果分为n份，多出一个扔掉，拿走其中一份，接着第二天熊重复这个过程，即先均分n份，丢掉多出的一个，然后拿走一份，依次类推直到最后一头熊都是这样（最后一头熊可以拿走0个也算均分）。问最初这堆苹果最少有多少个。

public class AppleAlgorithm {
    private int n;
    public AppleAlgorithm(int n) throws Exception {
        if(n<2||n>8){
            throw new Exception("非法的个数");
        }
        this.n = n;
    }
    public int getN(){
        return n;
    }
    public boolean splitApple(int num, int apple) {
        if (num == 0) {
            return true;
        }else if(apple <= 0){
            return false;
        }
        if ((apple-1) % n == 0) {
            return splitApple(num - 1, (apple - 1) / n * (n - 1));
        } else {
            return false;
        }
    }
    public static void main(String[] args) throws Exception {
        int i = 1;
        AppleAlgorithm apple = new AppleAlgorithm(2);
        while (true) {
            if (apple.splitApple(apple.getN(), i)) {
                System.out.println("result = " + i);
                break;
            }
            i++;
        }
    }
}

如题：输入正整数n，打印出1到10的n次方的值，如输入3，则输出1，2，3…，999.

看上去是一道很简单的题目，只要有点编程基础，我想大部分人都能写出如下代码:

@Test
    public void test5() {
        printNumber(3);
    }
    public void printNumber(int n) {
        int num = 1;
        while (n-- > 0) {
            num *= 10;
        }
        for (int i = 1; i < num; i++) {
            System.out.print(i+" ");
            if (i % 10 == 0)
                System.out.println();
        }
    }

但是上述代码有个很隐晦的bug，那就是当n取值很大时，比如100，那么10^n这个值也就很大，明显会超过int最大值，就算换成long也依然会出问题，所以完美解法提供如下：

@Test
    public void test4() {
    printNumber(10);
    }
   //这个值记录输出的值的个数
   int m = 0;
   public void pirntNumber(int n){
        int[] nums = new int[n];
        printNum(nums, n);
        System.out.println(" \n m = " + m);
   }
    //原理很简单，说白了就是递归而已。
    public void printNum(int[] nums, int n) {
     //要输出多少位的数值，就递归多少次
        if (n > 0) {
            n--;
            //数组由后往前依次存放要输出的数字的当前位数的值（从高到低）
            for (int i = 0; i < 10; i++) {
                nums[n] = i;
                printNum(nums, n);
            }
        } else {
        //当递归次数用尽，那么就开始打印这个数字，从高位到低位开始
            int k = nums.length - 1;
            /*下面这个循环是为了去掉无效的0，比如数组中依次存放的是应该是0,8,0,0，那么输出结果就应该是80.
            */
            while (nums[k] == 0) {
                k--;
                if (k < 0) {
                    return;
                }
            }
            //每输出10个数换行
            if (m++ % 10 == 0) {
                System.out.println();
            }
            //从后往前输出数组中的数字，也就是输出10^n的值
            for (; k >= 0; k--) {
                System.out.print(nums[k]);
            }
            System.out.print(" ");
            return;
        }
    }