Leetcode刷题

秒速五厘米 2021-06-10 20:37 503阅读 0赞

### 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++;
            }
    
        }
    
    }

![v][]

### 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;
            }
        }

[v]: /images/20210606/f445c4b15fa64258a567ef1f4ddfe3e6.png