大厂高频算法考点--双指针
数指针是一个很常见的技巧，为大家提供了leetcode的练习题和答案。
问题一：922. 按奇偶排序数组 II - 力扣（LeetCode）
class Solution {
public int[] sortArrayByParityII(int[] nums) {
//题目写了这个数组就是大与2的
//分析题目，将技术放置在下标是奇数的位置 偶数放置在下表是偶数的位置
//双指针的方式解决这个问题
//在考虑一个问题，是将双指针设置为标
int even =0;
int odd=1;
while(even<nums.length){
while(nums[even]%2!=0){
swap(nums,even,odd);
if(odd+2>nums.length-1){
break;
}else{
odd+=2;
}
}
even+=2;
}
return nums;
}
private void swap(int[] arr,int a,int b){
int temp =arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}问题二：287. 寻找重复数 - 力扣（LeetCode）
class Solution {
public int findDuplicate(int[] nums) {
//这个问题真的很像单链表的查找入环节点 就是将他包装为单链表，但是如何包装呢
//使用数组和下标进行包装 我们吧当前位置的值设置为就是他下一个位置的下标
if(nums.length<=2){
return nums[0];
}
int slow=nums[0];
int fast=nums[nums[0]];
while(slow!=fast){
slow=nums[slow];
fast=nums[nums[fast]];
}
fast=0;
while(fast!=slow){
fast=nums[fast];
slow=nums[slow];
}
return fast;//指针的值是下标
}
}问题三：42. 接雨水 - 力扣（LeetCode）
方法一：浪费空间，未经优化
class Solution {
public int trap(int[] height) {
//采取两种方式
//直接在创建两个数组 记录每个点左右的的比他大的值
//第一个数组是记录在0~i位置上的最大值
//第二个数组就是记录在i~n-1的最大值
//如果求解i的位置的话，就直接使用数组lmax的i-1的值，和rmax的i+1的值。
int n=height.length;
int[] lmax=new int[n];
int[] rmax=new int[n];
lmax[0]=height[0];
for(int i=1;i<n;i++){
lmax[i]=Math.max(lmax[i-1],height[i]);
}
rmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--){
rmax[i]=Math.max(rmax[i+1],height[i]);
}
int ans=0;
for(int i=1;i<n-1;i++){
ans+=Math.min(lmax[i-1],rmax[i+1])-height[i]>=0?Math.min(lmax[i-1],rmax[i+1])-height[i]:0;
}
return ans;
}
}方法二:不会创建新的数组
接雨水规律：如果现在右侧的最大高度>左侧，那就计算左侧的接雨水点，反之亦然
public static int trap(int[] height){
//优化的版本，不会创建新的数组，但是需要思考的过程
//总结就是一句话：如果现在右侧的最大高度>左侧，那就计算左侧的接雨水点，反之亦然
//因为如果现在右侧的高度已经大于左侧了，木桶原理，受限的原因一定是短板，右侧的高度一定不会比现在小，但是左面的高度不会半大，已经确定
//我能确定的最大值就是最小值
int n=height.length;
int l=0;
int r=n-1;
int lmax=height[0];
int rmax=height[n-1];
int ans=0;
while(l<r&&(l<n-1&&r>0)){
if(lmax<=rmax){
l++;
ans+=lmax-height[l]>=0?lmax-height[l]:0;
lmax=Math.max(height[l],lmax);
}else{
r--;
ans+=rmax-height[r]>=0?rmax-height[r]:0;
rmax=Math.max(height[r],rmax);
}
}
return ans;
}问题四：881. 救生艇 - 力扣（LeetCode）
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);//将数组排序
int l=0,r=people.length-1;
int ans=0;
while(l<=r){
if(people[l]+people[r]<=limit){
l++;
r--;
ans++;
}else{
r--;ans++;
}
}
return ans;
}
}问题五:11. 盛最多水的容器 - 力扣（LeetCode）
class Solution {
public int maxArea(int[] height) {
//思路就是短板效应，如果你现在得值是小的，那你就计算面积
int l = 0;
int r =height.length-1;
int ans=0;
while(l<=r){
if(height[l]<=height[r]){
ans=Math.max((r-l)*height[l],ans);
l++;
}else{
ans=Math.max((r-l)*height[r],ans);
r--;
}
}
return ans;
}
}问题六：475. 供暖器 - 力扣（LeetCode）
方法一：暴力方式
因为数组的长度是10^4所以即使是n*n的操作也不会超时，所以这道题可以暴力,但是如果暴力的话效率低
public int findRadius(int[] houses, int[] heaters) {
int ans=0;
//无需创建数组，直接相减就行
for(int i=0;i<houses.length;i++){
int count=Integer.MAX_VALUE;
for(int j=0;j<heaters.length;j++){
count=Math.min(count,getNum(houses[i]-heaters[j]));
}
ans=Math.max(count,ans);
}
return ans;
}
public int getNum(int n){
return n>=0?n:-n;
}方法二：双指针
我感觉这个解体方法很美妙
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int ans=0;
//使用双指针解决问题
//将r指针的移动就是在查找到位置是才会移动
//特别注意的是我们收集的答案时同一个房间的最短距离，但是房间之间我们收集的是最大值
//注意这个数组的数据必须是有序的
int l =0;
int r=0;
for(l=0;l<houses.length;l++){
while(!best(houses,heaters,l,r)){//这里面直接比较出来房间里的最小的值了
r++;
}
//现在直接比较房间与房间之间的最大值
ans=Math.max(ans,Math.abs(houses[l]-heaters[r]));
}
return ans;
}
public boolean best(int[] houses,int[] heaters,int i,int j){
//之里面一定是> 我么的设定就是即使时相等时，就必须要前进
return j==heaters.length-1 ||Math.abs(houses[i]-heaters[j+1])- Math.abs(houses[i]-heaters[j])>0;
}
}问题七41. 缺失的第一个正数 - 力扣（LeetCode）
class Solution {
//整体的思路如下
//因为数值在设计这个题目时设定，如果长度是n的数组，那他每个位置的值就在n-1处，所以最佳状态
//是缺的就是第n+1的数字
//使用双指针去解决问题，将l指针放置在0位置，r指针放置在n位置，注意是n位置，不是n-1，我们将要维护一个无效区
//哪几种情况数值无效，
//1.数值大小《=0 或者是当前的下表是3 但是这个数比4小
//2.当前的之大于r
//3.如果当前值就是n在n-1位置，l++
//如果现在的数字是4 但是你的三位置放置了4 那就是垃圾
public int firstMissingPositive(int[] arr) {
int l=0;
int r=arr.length;
while(l<r){
if(arr[l]==l+1){
l++;
}else if (arr[l]>r||arr[l]<=l||arr[l]==arr[arr[l]-1]){
swap(arr,l,--r);
}else{
swap(arr,l,arr[l]-1);//现在就是数值时合法的，该如何计算 5
}
}
return l+1;
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}原文地址：https://blog.csdn.net/hdk5855/article/details/142921522
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！