算法学习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 并且将其作为targetint[] 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--;elseleft++;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;// 首先找到起始点 找到起始点之后 两段升序找targetint 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;}
}