数指针是一个很常见的技巧，为大家提供了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;
}
}
