算法学习day28

一、寻找右区间(二分法)

题意：题目很容易理解 但是转换为二分法有点晦涩

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。注意 i 可能等于 j 。

让我们去找一个区间的最小右侧区间，满足条件：右侧区间的start值>该区间的end值，可能存在多个右侧区间，取最小的start值的区间。并把该区间的下标放到数组里面返回。没有记作-

思路：

题目要让我们去找一个区间的最小右侧区间。如何做到最小？

1.首先将每个区间的start值进行排序

2.然后for循环遍历每一个区间，将其end值作为target。

3.然后二分查找第一个>=target的start值的下标。放到res数组中

4.返回res数组

代码：

//将每一个区间的左端点排序 遍历每一个数组的右端点 找到第一个比它大的左端点 然后加入到集合中。如何将左端点排序，使用二维数组
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        //第一步 创建sortStart数组 并且排序
        int[][] sortStart=new int[intervals.length][2];//start值：下标
        for(int i=0;i<intervals.length;i++){
            sortStart[i]=new int[]{intervals[i][0],i};
        }
        Arrays.sort(sortStart,(a,b)->a[0]-b[0]);

        //第二步 遍历每一个区间的end 并且将其作为target
        int[] res=new int[intervals.length];
        for(int i=0;i<intervals.length;i++){
            int target=intervals[i][1];//第i个区间的end值
            int left=0,right=sortStart.length-1;
            //第三步 二分查找最小的>=end的start值的下标 放入res数组中
            while(left<right){
                int mid=left+(right-left)/2;
                if(sortStart[mid][0]>=target){
                    right=mid;
                }else{
                    left=mid+1;
                }
            }
            res[i]=sortStart[left][0]>=intervals[i][1]?sortStart[left][1]:-1;
        }
        return res;
    }
}

二、最长递增子序列（dp+二分法）

解法一：dp动态规划

dp五部曲：

1.dp[i]的含义:以i为结尾的最长递增子序列的长度

2.递推公式：dp[i]=Math.max(dp[i],dp[j]+1);在0->i，如果找到比nums[i]小的数，说明找到了一个递增序列，然后对dp[i]进行更新。

3.初始化dp[i]=1;

4.遍历的顺序:双层for循环，i从1开始，j从0开始直j<i;

代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        //1.dp[i]:以i结尾的最长递增子序列的长度
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        int max=1;
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

解法二：辅助数组+二分法

思路：

遍历数组，如果遇到的数字是大于尾部元素的，直接放到尾部元素后面，使得递增序列变大；

如果遇到的数字是小于尾部元素的，为了使递增的速度最慢，就要将该元素放到最合适的地方.

那么这个最合适的地方如何去寻找？ 当然我们可以利用辅助数组单调递增的规律，使用二分查找法去寻找最合适的地方。

代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        //1.定义辅助数组
        int[] sortNums=new int[nums.length];
        int size=1;
        sortNums[0]=nums[0];
        for(int i=0;i<nums.length;i++){
            //如果大于的话 直接放到sortNums的后边
            if(nums[i]>sortNums[size-1]){
                sortNums[size++]=nums[i];
            }else{
                //如果小于的话 我们就要去找合适的位置
                int target=nums[i];
                int left=0,right=size-1;
                while(left<=right){
                    int mid=left+(right-left)/2;
                    if(sortNums[mid]>=target){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }
                sortNums[right+1]=nums[i];
            }
        }
        return size;
    }
}

三、寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。

因为nums[-1]=nums[n]=-∞；因此可以推断出:

nums[i]<nums[i+1]:那么后面一定存在一个峰值；

nums[i]>=nums[i+1];那么前面一定存在一个峰值；

思路：

那么就根据推断出的规律来进行二分查找：如果nums[mid]>=nums[mid+1] left=mid+1;

nums[mid]<nums[mid+1] right=mid;

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length==1)return 0;
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=nums[mid+1]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}

四、找到k个最接近的元素

题意：

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

输入：arr = [1,2,3,4,5], x = 3, k = 4
输出：[1,2,3,4] 相同距离的话 加入较小的

解法一：双指针删除法

思路：

逆向思维，在数组中删除(size-k)个离x最远的数字。可以使用双指针（left，right）向x靠近的同时不断删除元素。

比如在1 2 3 4 5中寻找4个最靠近3的数。

left指向1,right指向5。和3的距离都为2，将5删除。剩余四个数字 4==k。那么加入到集合中返回。

代码：

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 双指针删除法
        List<Integer> res = new ArrayList<>();
        int number = arr.length;
        int left = 0;
        int right = number - 1;
        int count = 0;
        while (left <= right) {
            if (count == number - k) {
                for (int i = left; i <= right; i++) {
                    res.add(arr[i]);
                }
            }
            int diff1 = Math.abs(x - arr[left]);
            int diff2 = Math.abs(arr[right] - x);
            if (diff1 <= diff2)
                right--;
            else
                left++;
            count++;// 已经删除的数字
        }
        return res;
    }
}

五、俄罗斯套娃问题(最长上升子序列的二维版)

你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

解法一：动态规划(超时)

解法二：贪心+二分查找

思路：

当只有宽和高都比上一个信封大的时候，才能实现套娃。

我们可以先对宽度进行升序排列，确认了宽度之后，就变成一维的求最长上升子序列了。

如何求最大长度的高度序列。使用贪心算法:每次我们都希望放在末尾的值是一个符合条件并且尽可能小的数字，这样我们的长度最长的概率就最大。(因此当我们遇到heights[i]<tails[size]的时候，我们需要将heights[i]放到合适的位置，但是heights所对应宽度是可能相等的。在相等的时候，我们应该按照降序排列，这样在更新下一个的时候就会把它刷掉)。

举个例子理解一下：假如按照升序排列后为:(5,5),(6,6),(7,2)(7,1)(8,3),(9,4)。

1.envelopes[i][1]=5, 集合为空，tails[0]=5 size=1;

2.envelopes[i][1]=6,  6大于5，tails[1]=6,size=2;

3.envelopes[i][1]=2,  2小于6，给2寻找合适的位置,2<5。因此tails[0]=2;

4.envelopes[i][1]=1, 1小于6，给1寻找合适的位置,1<2,因此tails[0]=1;

5.envelopes[i][1]=3，3小于6，给3寻找合适的位置,3<6,因此tails[1]=3；

6.envelopes[i][1]=4，4大于3，因此tails[2]=4；size=3

寻找合适的位置是根据二分搜索法进行寻找。

代码：

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length==0)return 0;;
        // 对信封的宽度排序
        Arrays.sort(envelopes,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
            }
        });
        int maxSize=1;
        int size=1;
        int[] tails=new int[envelopes.length];
        tails[0]=envelopes[0][1];
        for(int i=1;i<envelopes.length;i++){
            if(envelopes[i][1]>tails[size-1]){
                tails[size++]=envelopes[i][1];
            }else{
                int left=0,right=size-1;
                int target=envelopes[i][1];
                while(left<=right){
                    int mid=left+(right-left)/2;
                    if(tails[mid]>=target)right=mid-1;
                    else left=mid+1;
                }
                tails[right+1]=target;
            }
        }
        return size;
    }
}

六、寻找旋转排序数组中的最小值(要求时间复杂度为O(logN))

思路：二分法

旋转之前，是一个升序数组；旋转之后，会变成两段升序数组。

旋转时，小数往后走，大数旋转到前面来。分情况：

1.起始点在到达中间之前，(右边部分一定处于升序),nums[mid]的值一定是小于nums[right]的，此时起始点一定在mid左边(包括mid)

2.起始点到达中间之后，大数占领起始点之前的区域,nums[mid]的值一定是大于nums[right]的，此时起始点一定是在右半部分的。(反证一下，如果起始点在左部分的话，那么起始点的右边一定是升序的，那么nums[mid]一定小于nums[right])

所以

1.当nums[mid]>nums[right]，起始点一定在右边,更新左边界left=mid+1;

2.当nums[mid]<=nums[right],起始点一定在左边，更新有边界right=mid;

代码：

class Solution {
    public int findMin(int[] nums) {
        int size=nums.length;
        int left=0,right=size-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[right]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return nums[left];
    }
}

七、搜索旋转排序数组

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

思路：

将一个排序好的数组旋转，变成两段升序序列(也可能是一段 就是原始的)。然后找到元素的起始点。两种情况：

1.如果起始点==0，说明并没有进行旋转，还是原始的数组。

2.如果起始点>0,说明进行了旋转，在两段序列中进行查找target就可以。

代码:

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target)
            return 0;
        // 首先找到起始点 找到起始点之后 两段升序找target
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[right]) {
                // 说明mid一定在左半边
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // left就是起始的位置
        int res1 = 0;
        int res2 = 0;
        if (left == 0)
            return binarySearch(nums, 0, nums.length - 1, target);
        else {
            res1 = binarySearch(nums, 0, left - 1, target);
            res2 = binarySearch(nums, left, nums.length - 1, target);
        }
        return res1 == -1 ? res2 : res1;
    }

    public int binarySearch(int[] nums, int left, int right, int target) {
        int index = -1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return nums[left]==target?left:index;
    }
}

八、搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

思路：

如果从左上角或者右下角开始寻找的话，不具有区别度。

如果从右上角或者左下角寻找的话：

1.右上角：左边变小，下边变大

2.左下角：上边变小，右边变大

代码：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //从右上角出发
        int rol=matrix.length;
        int cow=matrix[0].length;
        int x=0,y=cow-1;
        while(x<rol&&y>=0){
            if(matrix[x][y]<target){
                x++;
            }else if(matrix[x][y]>target){
                y--;
            }else{
                return true;
            }
        }
        return false;
    }
}