牛客编程题--必刷101之双指针篇

补充知识

双指针

双指针从广义上来说，是指用两个变量在线性结构上遍历而解决的问题。狭义上说，

• 对于数组，指两个变量在数组上相向移动解决的问题，也称为「左右指针」问题；
• 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题；

左右指针

首先判断是用左右指针还是快慢指针，这个可以根据数据结构来进行选择，如果给出的是一个数组，那么可以考虑用左右指针。左右指针在数组中实际是指两个索引值，⼀般初始化为 left = 0, right =nums.length - 1 。

滑动窗口算法框架：

int	left	=	0,	right	=	0;
while	(right	<	s.size())	{`
	#增大窗口
	window.add(s[right]);				
	right++;
	while	(window	needs	shrink)	{
		//	缩⼩窗⼝								
		window.remove(s[left]);								
		left++;
		}
}

快慢指针

【主要针对的数据结构存储方式是 链表 、链表 、链表】
快慢指针⼀般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决⼀些链表中的问题。

具体内容题目之前已经发过，感兴趣的小伙伴可以查看小曾带你刷leetcode–双指针篇之左右指针(一)小曾带你刷leetcode --双指针篇之快慢指针(二)

1、合并两个有序的数组

题目描述：给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

输入：
[4,5,6],[1,2,3]
返回值：
[1,2,3,4,5,6]
说明：A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组

思路：既然是两个已经排好序的数组，如果可以用新的辅助数组，那很容易我们可以借助归并排序的思想，将排好序的两个子数组合并到一起。但是这道题要求我们在数组A上面添加，那因为数组A后半部分相当于为空，则我们可以考虑逆向使用归并排序思想，从较大的开始排。对于两个数组每次选取较大的值，因此需要使用两个同时向前遍历的双指针。

具体步骤：
step 1：使用三个指针，i指向数组A的最大元素，j指向数组B的最大元素，k指向数组A空间的结尾处。
step 2：从两个数组最大的元素开始遍历，直到某一个结束，每次取出较大的一个值放入数组A空间的最后，然后指针一次往前。
step 3：如果数组B先遍历结束，数组A前半部分已经存在了，不用管；但是如果数组A先遍历结束，则需要把数组B剩余的前半部分依次逆序加入数组A前半部分，类似归并排序最后的步骤。

代码实现：

import java.util.*;
public class Solution {
    
    public void merge(int A[], int m, int B[], int n) {
    
        // 定义三个指针
        int i = m-1,j = n-1,index = m+n-1;
        // 满足大于0的情况
        while(i>=0 && j>=0){
    
            // 如果A数组大于B数组，则将A数组元素放到最末尾位置
            if(A[i]> B[j]){
    
                A[index--] = A[i--];
            }else{
    
            // 反之，将B数组放入末尾位置
                A[index--] = B[j--];
            }
        }
        // 如果A数组先遍历结束,则需要将B数组剩余部分基于逆序加入A中
        while(j>=0){
    
            A[index--] = B[j--];
        }
  
    }
}

2、判断是否为回文字符串

题目描述：给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。
字符串回文指该字符串正序与其逆序逐字符一致。

示例1
输入：“absba”
返回值：true
示例2
输入：“ranko”
返回值：false

思路：直接首尾双指针
回文字符串正向遍历与逆向遍历结果都是一样的，因此我们可以准备两个对撞指针，一个正向遍历，一个逆向遍历。

//首指针
int left = 0;
//尾指针
int right = str.length() - 1;
//首尾往中间靠 
while(left < right){
     
    ......
}

具体步骤
step 1：准备两个指针，一个在字符串首，一个在字符串尾。
step 2：在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，若是不相等则直接就不是回文。
step 3：直到两指针在中间相遇，都还一致就是回文。因为首指针到了后半部分，走过的正好是尾指针走过的路，二者只是交换了位置，比较相等还是一样的。

public boolean judge (String str) {
    
        // 定义首尾指针
        int left = 0,right = str.length() -1;
        while(left < right){
    
            if(str.charAt(left) != str.charAt(right))
                return false;
            left ++ ;
            right --;
        }
        return true;
    }

3、合并区间

题目描述：给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

示例1
输入：[[10,30],[20,60],[80,100],[150,180]]
返回值：[[10,60],[80,100],[150,180]]
示例2
输入：[[0,10],[10,20]]
返回值：[[0,20]]

解题思路: 贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

首先考虑什么样的区间可以进行合并： 交叉的区间【后一个区间的头小于前一个区间的尾】

//区间有重叠，更新结尾
if(intervals[i].start <= res.back().end) 
    res.back().end = max(res.back().end, intervals[i].end);

那我们肯定是区间在一定程度上有序的才可以方便比较（区间有两个边界值，完全有序不可能，但是可以按照区间首排序），这时候只要遍历到交叉的情况，就利用贪心思想，一直合并，直到不能合并为止。

具体步骤：
step 1：既然要求重叠后的区间按照起点位置升序排列，我们就将所有区间按照起点位置先进行排序。使用sort函数进行排序，重载比较方式为比较interval结构的start变量。
step 2：排序后的第一个区间一定是起点值最小的区间，我们将其计入返回数组res，然后遍历后续区间。
step 3：后续遍历过程中，如果遇到起点值小于res中最后一个区间的末尾值的情况，那一定是重叠，取二者最大末尾值更新res中最后一个区间即可。
step 4：如果遇到起点值大于res中最后一个区间的末尾值的情况，那一定没有重叠，后续也不会有这个末尾的重叠区间了，因为后面的起点只会更大，因此可以将它加入res。

import java.util.*;

public class Solution {
    
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals.size() == 0)
            return res;
        // 进行首区间排序,重载比较
        Collections.sort(intervals, new Comparator<Interval>(){
    
            public int compare(Interval a1, Interval a2){
    
                if(a1.start != a2.start)
                    return a1.start - a2.start;
                else
                    return a1.end -a2.end;
            }
        } );
        // 放入第一个最小的区间
        res.add(intervals.get(0));
        int count = 0;
        // 继续遍历
        for(int i=1; i< intervals.size(); i++){
    
            Interval a1 = intervals.get(i);
            Interval a0 = res.get(count);
            if(a1.start > a0.end){
    
                res.add(a1);
                count++;
            }else{
    
                // 有重叠
                res.remove(count);
                Interval s = new Interval(a0.start, a1.end);
                if(a1.end < a0.end){
    
                    s.end = a0.end;
                }
                res.add(s);
            }  
        }
        return res;
    }
}

4、最小覆盖子串

题目描述：给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
例如：
S ="XDOYEZODEYXNZ"S=“XDOYEZODEYXNZ”
T =“XYZ"T=“XYZ”
找出的最短子串为"YXNZ”“YXNZ”.

示例 输入：“abcAbA”,“AA” 返回值：“AbA”

思路：可以直接用滑动窗口的方法 + hash表来统计

滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)O(1)O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑快速查找某个元素是否出现过的哈希表——只需要维护一个哈希表，将字符串T中的字符作为key值，初始化时当字符在T中出现一次则对应的value值减1：

for(int i = 0; i < T.length(); i++)
    //初始化哈希表都为负数，找的时候再加为正
    hash[T.charAt(i)] = -1; 
//后续如果在字符串S中找到相应字符就可以将其加回来
char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;
//然后使用双指针维护滑动窗口，在窗口内，哈希表中value都大于0：
for (int i = 0; i < hash.length; i++) {
    
    if (hash[i] < 0)
        return false;
}
return true;
//这个窗口内出现了T中所有的字符串，此时可以尝试缩小窗口，因为双指针同步向右遍历，因此缩小窗口只能是缩小左界。

具体步骤：
step 1：建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。

import java.util.*;


public class Solution {
    
    /** * * @param S string字符串 * @param T string字符串 * @return string字符串 */
    boolean check(int[] hash) {
     //检查是否有⼩于0的
        for (int i = 0; i < hash.length; i++) {
    
            if (hash[i] < 0)
                return false;
        }
        return true;
};
    public String minWindow (String S, String T) {
    
        // write code here
        int cnt = S.length() +1;
        // hash 表记录目标字符串T的字符个数
        int[] hash = new int[128];
        for(int i = 0; i< T.length(); i++)
            // 初始化哈希表为负数，找的时候为正
            hash[T.charAt(i)] -= 1;
        // 滑动窗口
        int slow = 0, fast = 0;
        int left = -1, right =-1 ; //记录左右区间
        for(; fast < S.length(); fast++){
    
            char c = S.charAt(fast);
            hash[c] ++;
            while(check(hash)){
    
                // 都覆盖了,缩小窗口
                if( cnt > fast -slow +1){
    
                    cnt = fast -slow +1;
                    left = slow;
                    right = fast;
                }
                c  = S.charAt(slow);
                hash[c]--;
                slow ++; // 窗口缩小
            }
        }
        if(left == -1){
    
            return "";
        }  
        return S.substring(left , right +1);
    }
}

5、反转字符串

题目描述：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

示例：输入：“abcd” 返回值：“dcba”

思路：字符串反转即逆序，前后顺序是反的，也就是前面的字符换到了后面，后面的字符换到了前面，那既然这样我们就将前后的顺序依次对称交换，这时候就需要使用到了对撞双指针，从前后同时遍历。

具体步骤：
step 1：准备两个指针，从字符串一首一尾同时出发。
step 2：每次交换二者指向的字符，直到二者相遇，这样刚好可以将字符串首尾交换，完成反转。

import java.util.*;


public class Solution {
    
    /** * 反转字符串 * @param str string字符串 * @return string字符串 */
    public String solve (String str) {
    
        // write code here
        char[] s = str.toCharArray();
        int left = 0, right = str.length()-1;
        while(left < right){
    
            char c = s[left];
            s[left] = s[right];
            s[right] = c;
            left ++;
            right --;
        }
        return new String(s);
    }
}

6、最长无重复子数组

题目描述: 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

示例：输入：[2,3,4,5] 返回值：4 说明：[2,3,4,5]是最长子数组

输入： [2,2,3,4,3] 返回值： 3 说明： [2,3,4]是最长子数组

思路：滑动窗口的思想
既然要找一段连续子数组的内不重复的长度，我们可以使用滑动窗口，保证窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复数组，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。

而保证窗口内的元素不重复，我们可以使用根据key值快速访问的哈希表，key值为窗口内的元素，value为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。

while(mp.get(arr[right]) > 1) 
    //窗口左移，同时减去该数字的出现次数
    mp.put(arr[left],mp.get(arr[left++])-1); 

具体步骤：
step 1：构建一个哈希表，用于统计数组元素出现的次数。
step 2：窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
step 3：一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
step 4：每轮循环，维护窗口长度最大值。

import java.util.*;


public class Solution {
    
    /** * * @param arr int整型一维数组 the array * @return int整型 */
    public int maxLength (int[] arr) {
    
        // 滑动窗口思路
        // 用hash表记录窗口内非重复的数字
        HashMap<Integer, Integer> mp = new HashMap<>();
        int res = 0;
        // 设置窗口的左右界
        for(int left = 0, right = 0; right < arr.length ; right ++){
    
            // 记录出现次数
            if(mp.containsKey(arr[right])){
    
                mp.put(arr[right],mp.get(arr[right])+1);
            }
            else
                mp.put(arr[right],1);
            // 当出现次数大于1，需要进行滑动
            while(mp.get(arr[right])>1){
    
                // 窗口右移
                mp.put(arr[left],mp.get(arr[left++])-1);
            }
            res = Math.max(res, right-left+1);
        }
        return res;
    }
}

7、盛水最多的容器

题目描述：给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时，视为不能形成容器，请返回0
3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1

如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:

输入：[1,7,3,2,4,5,8,2,7] 返回值：49

思想： 双指针 + 贪心思想
这道题利用了水桶的短板原理，较短的一边控制最大水量，因此直接用较短边长乘底部两边距离就可以得到当前情况下的容积。但是要怎么找最大值呢？

可以利用贪心思想：我们都知道容积与最短边长和底边长有关，与长的底边一定以首尾为边，但是首尾不一定够高，中间可能会出现更高但是底边更短的情况，因此我们可以使用对撞双指针向中间靠，这样底边长会缩短，因此还想要有更大容积只能是增加最短变长，此时我们每次指针移动就移动较短的一边，因为贪心思想下较长的一边比较短的一边更可能出现更大容积。

//优先舍弃较短的边
if(height[left] < height[right])
    left++;
else
    right--;

具体步骤：
step 1：优先排除不能形成容器的特殊情况。
step 2：初始化双指针指向数组首尾，每次利用上述公式计算当前的容积，维护一个最大容积作为返回值。
step 3：对撞双指针向中间靠，但是依据贪心思想，每次指向较短边的指针向中间靠，另一指针不变。

import java.util.*;


public class Solution {
    
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param height int整型一维数组 * @return int整型 */
    public int maxArea (int[] height) {
    
        // write code here
        if(height.length < 2)
            return 0;
        int res = 0;
        int left = 0;
        int right = height.length -1;
        while(left < right){
    
            // 计算水容量
            int capacity = Math.min(height[left], height[right]) *(right - left);
            // 维护最大值
            res = Math.max(res, capacity);
            // 优先舍弃较短的边
            if(height[left] < height[right])
                left++;
            else 
                right--;
        }
        return res;
        }
}

8、接雨水问题

题目描述：给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

输入：[3,1,2,5,2,4] 返回值：5
说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。

我们都知道水桶的短板问题，控制水桶水量的是最短的一条板子。这道题也是类似，我们可以将整个图看成一个水桶，两边就是水桶的板，中间比较低的部分就是水桶的底，由较短的边控制水桶的最高水量。但是水桶中可能出现更高的边，比如上图第四列，它比水桶边还要高，那这种情况下它是不是将一个水桶分割成了两个水桶，而中间的那条边就是两个水桶的边。

有了这个思想，解决这道题就容易了，因为我们这里的水桶有两个边，因此可以考虑使用对撞双指针往中间靠。

具体步骤：
step 1：检查数组是否为空的特殊情况
step 2：准备双指针，分别指向数组首尾元素，代表最初的两个边界
step 3：指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。

import java.util.*;


public class Solution {
    
    /** * max water * @param arr int整型一维数组 the array * @return long长整型 */
    public long maxWater (int[] arr) {
    
        // 排除空数组
        if(arr.length == 0)
            return 0;
        long res = 0;
        // 左右双指针
        int left =0;
        int right = arr.length -1;
        // 中间区域的边界高度
        int maxL = 0;
        int maxR = 0;
        // 直到左右指针相遇
        while(left < right){
    
            // 维护最大边界
            maxL = Math.max(maxL, arr[left]);
            maxR = Math.max(maxR, arr[right]);
            // 确定格子水量
            if(maxR > maxL)
                res += maxL - arr[left++];
            else
                res += maxR- arr[right--];
        }
        return res;
    }
}