时间戳

首页 > 技术文章 > leetcode

leetcode

lgh544 2020-06-16 16:11 原文

1、组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
    所有数字（包括 target）都是正整数。
    解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TheSumOfCombination_39 {

    public static void main(String[] args) {
        TheSumOfCombination_39 res = new TheSumOfCombination_39();
        int[] candidates = {2,4,5,6,7};
        int target = 10;
        List<List<Integer>> result = res.combinationSum(candidates, target);
        System.out.println(result.toString());
    }
     List<List<Integer>> list1 = new ArrayList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list2 = new ArrayList<>();
        int len = candidates.length;
        Arrays.sort(candidates);
        dfc(candidates,0,len,list2,target);
        return list1;
    }
    public void dfc(int[] candidates,int begin,int len,List<Integer> list2,int target) {
        if(target == 0) {
            list1.add(new ArrayList<>(list2));
            return;
        }
        for(int i = begin; i < len; i++) {
            if(target-candidates[i] < 0) {
                break;
            }
            list2.add(candidates[i]);
            dfc(candidates,i,len,list2,target-candidates[i]);
            list2.remove(list2.size()-1);
        }
    }
}

2、组合总和2

给定一个数组 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]
]

package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class theSumOfCombination_40 {

    public static void main(String[] args) {
        theSumOfCombination_40 res = new theSumOfCombination_40();
        int[] candidates = {2,5,2,1,2};
        int target = 5;
        List<List<Integer>> result = res.combinationSum(candidates, target);
        System.out.println(result.toString());
    }
     List<List<Integer>> list1 = new ArrayList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> list2 = new ArrayList<>();
        int len = candidates.length;
        Arrays.sort(candidates);
        dfc(candidates,0,len,list2,target);
        return list1;
    }
    public void dfc(int[] candidates,int begin,int len,List<Integer> list2,int target) {
        if(target == 0) {
            if(!list1.contains(new ArrayList<>(list2))) {
                list1.add(new ArrayList<>(list2));
            }
            return;
        }
        for(int i = begin; i < len; i++) {
            if(target-candidates[i] < 0) {
                break;
            }
            list2.add(candidates[i]);
            dfc(candidates,i+1,len,list2,target-candidates[i]);
            list2.remove(list2.size()-1);
        }
    }
}

3、缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:


输入: [1,2,0]
输出: 3


示例 2:

输入: [3,4,-1,1]
输出: 2
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间

方法一：将数组视为哈希表

    由于题目要求我们“只能使用常数级别的空间”，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组；
    我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；
    那么，我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。
    这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。
　　时间复杂度：O(N)，这里 NN是数组的长度。

  空间复杂度：O(1)。

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

方法一：时间复杂度：O(N)O(N)O(N)，这里 NNN 表示数组的长度。第 1 次遍历了数组，第 2 次遍历了区间 [1, len] 里的元素。
空间复杂度：O(N)O(N)O(N)，把 NNN 个数存在哈希表里面，使用了 N 个空间。

class Solution {
       public int firstMissingPositive(int[] nums) {
        Set<Integer> list = new HashSet<>();
        list.add(0);
        for(int i : nums) {
            if(i>0) {
                list.add(i);
            }
        }
            Integer[] positiveNums = list.toArray(new Integer[list.size()]);
            Arrays.sort(positiveNums);
            int m = 0;
            for(int i = 1; i < positiveNums.length; i++) {
                if(positiveNums[i] == i) {
                }else {
                    return i;
                }
                m = i;
            }
            if(m == positiveNums.length-1) {
                return ++m;
            }
            return -1;
    }
}

4、接雨水
求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。
装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。
所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况。
较矮的墙的高度大于当前列的墙的高度：

 

很明显，较矮的一边，也就是左边的墙的高度，减去当前列的高度就可以了，也就是 2 - 1 = 1，可以存一个单位的水。
较矮的墙的高度小于当前列的墙的高度：

正在求的列不会有水，因为它大于了两边较矮的墙。

  • 较矮的墙的高度等于当前列的墙的高度。

    和上一种情况是一样的，不会有水。

首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的）
对于 max_left我们其实可以这样求。
max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
对于 max_right我们可以这样求。
max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
这样，我们再利用解法二的算法，就不用在 for 循环里每次重新遍历一次求 max_left 和 max_right 了。

class Solution {
    public int trap(int[] height) {
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        int sum = 0;
        for(int i = 1;i < height.length - 1;i++){
           max_left[i] = Math.max(max_left[i -1],height[i - 1]);
        }
        for(int i = height.length - 2;i > 0;i--){
           max_right[i] = Math.max(max_right[i + 1],height[i + 1]);
        }
        for(int i = 1; i < height.length - 1; i++){
            int min = Math.min(max_left[i] , max_right[i]);
                 if(height[i] < min){
                     sum += (min - height[i]);
                 }
            
           
        }
       return sum;
    }
}

时间复杂度：O(n)。

空间复杂度：O(n)，用来保存每一列左边最高的墙和右边最高的墙。

 5、跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:
假设你总是可以到达数组的最后一个位置。我们知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。
至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的。


时间复杂度：O(n²)，因为最坏的情况比如 1111111 ，position 会从 5 更新到 0，并且每次更新都会经历一个 for 循环。
空间复杂度：O(1)。

class Solution {
    public int jump(int[] nums) {
        int step = 0;
        int position = nums.length - 1;
        while(position != 0){
          for(int i = 0; i < nums.length - 1 ;i++){
             if(nums[i] >= position - i){
                step++;
                position = i;
                break;
            }
        }
        }
        return step;
    }
   
}

 判断你是否能够到达最后一个位置。

解题思路：

    如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
    可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
    如果可以一直跳到最后，就成功了。

 

package leetcode;

public class jump_55 {

    public static void main(String[] args) {
        int[] nums = {3,2,1,0,4};
        System.out.println(canJump(nums));
    }
    public static boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++)
        {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;

    }

}

 

推荐阅读