求职Leetcode算法题（7）

1.搜索旋转排序数组 

这道题要求时间复杂度为o（log n），那么第一时间想到的就是二分法，二分法有个前提条件是在有序数组下，我们发现在这个数组中存在两部分是有序的，所以我们只需要对前半部分和后半部分分别进行二分查找得到目标值就OK了。 

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

1. 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
2. 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

2.组合就和

解题思路：

• 例如，输入集合 {3,4,5} 和目标整数 9 ，解为 {3,3,3},{4,5} 。需要注意两点：
• 输入集合中的元素可以被无限次重复选取。
• 子集是不区分元素顺序的，比如 {4,5} 和 {5,4} 是同一个子集。
• 向「全排列」代码输入数组 [3,4,5] 和目标元素 9 ，输出结果为 [3,3,3],[4,5],[5,4] 。虽然成功找出了所有和为 9 的子集，但其中存在重复的子集 [4,5] 和 [5,4] 。
• 这是因为搜索过程是区分选择顺序的，然而子集不区分选择顺序。如下图所示，先选 4 后选 5 与先选 5 后选 4 是两个不同的分支，但两者对应同一个子集。

重复子集剪枝：

• 我们考虑在搜索过程中通过剪枝进行去重。观察下图，重复子集是在以不同顺序选择数组元素时产生的，具体来看：
• 第一轮和第二轮分别选择 3 , 4 ，会生成包含这两个元素的所有子集，记为 [3,4,⋯] 。
• 若第一轮选择 4 ，则第二轮应该跳过 3 ，因为该选择产生的子集 [4,3,⋯] 和 1. 中生成的子集完全重复。
• 分支越靠右，需要排除的分支也越多，例如：
• 前两轮选择 3 , 5 ，生成子集 [3,5,⋯] 。
• 前两轮选择 4 , 5 ，生成子集 [4,5,⋯] 。
• 若第一轮选择 5 ，则第二轮应该跳过 3 和 4 ，因为子集 [5,3,⋯] 和子集 [5,4,⋯] 和 1. , 2. 中生成的子集完全重复。

class Solution {
    void backtrack(List<Integer> state,int target,int[] choices,int start,List<List<Integer>> res){
        //子集和等于target时，记录解
        if(target==0){
            res.add(new ArrayList<>(state));
            return;
        }
        //遍历所有的选择
        //剪枝二：从start开始遍历，避免生成重复子集
        for(int i=start;i<choices.length;i++){
            if(target-choices[i]<0){
                break;
            }
            //尝试：做出选择，更新target，start
            state.add(choices[i]);
            backtrack(state,target-choices[i],choices,i,res);
            //回退：撤销选择，恢复到之前的状态
            state.remove(state.size()-1);
        }
 
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> state =new ArrayList<>();//状态（子集）
        Arrays.sort(candidates);
        int start=0;//遍历起始点
        List<List<Integer>> res =new ArrayList<>();
        backtrack(state,target,candidates,start,res);
        return res;
 
    }
}

3.缺失第一个正数

首先我们先用几个简单的例子来演示一下：

​ 第一个例子是 1 2 -1 4 5，第一个不满足要求的元素就是-1，对应下标就是 2，先用肉眼看看，我们在 1 2 -1 4 5情况下，没有出现的最小的正整数很明显是 3。尝试着找规律——

没有出现的最小的正整数=第一个不满足要求的元素下标+1

 

满足要求，那么要求是什么呢？

我们需要找到：第一个不满足要求的元素下标

匹配成功的条件也就是数组的 元素值=元素下标+1

swap(当前位置元素<---->目的位置元素)
目的位置： nums[i] - 1
也就是 值为4的元素 要放到下标为 3 的位置

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len =nums.length;
 
        for(int i =0;i<lenli++){
            while(nums[i]>0&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){
                //满足在指定范围内，并没有放在正确的位置上，才交换
                //例如数组3应该放在索引2的位置上
                swap(nums,nums[i]-1,i);
            }
        }
      for(int i =0;i<len;i++){
        if(nums[i]!=i+1){
            return i+1;
        }
      }
      //都正确则返回数组长度+1
      return len+1;
    }
      peivate void swap(int[] nums,int index1, int index2){
        int temp =nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
      }
        
 
    }
}