【九章算法强化班】两指针

outline

1. 一个数组，从两边往中间移动（对撞型）
2. 一个数组，同时向前移动（前向型）
3. 两个数组两根指针（并行型）

1.对撞型或相会型

leetcode 11.Container With Most Water

题目

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

分析

灌水问题，从两边向内灌水，所以初始两个指针ij一头一尾，此时能够容纳的水量是i和j中比较高度的柱子高度*ij两个柱子之间的距离：

max(height[i] , height[j]) * (j - i)

然后考虑将柱子向内移动，其实我们只需要移动比较矮的柱子，因为如果移动长的一边的柱子，根据上面的公式，j-i会变短，max(height[i] , height[j])可能变小可能不变，所以总的水量不会增加，所以我们只有移动短的柱子，才有可能会遇到更高的柱子，使得水量增大。

这样一来，每次选取较短的柱子向内移动，时间复杂度为$O(n)$

代码

class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length-1;
        int max = Integer.MIN_VALUE;
        while(i < j){
            if(height[i] < height[j]){
                max = Math.max(max,(j-i) *height[i]);
                i++;
            }
            else {
                max = Math.max(max,(j-i) * height[j]);
                j--;
            }
        }
        return max;
    }
}

Quick select — Kth Largest Element in an Array

问题

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

在一组数字中找到第K大的数字

思路

方法一：可以用堆，维护一个大小为K的堆，将数字依次加入堆，找到第k大，时间复杂度$O(nlogk)$

方法二：quick select，基于quick sort的思想

1. 每次在数组中随机选取一个数组作为pivort，这里面随机选取，经过大量的验证，选取中间位置的数字作为pivot比较稳妥。
2. 然后和快排一样，将比它小的放在它左边，比它大的放在右边，找到pivot的位置即是pivot的最终位置。
   1. 如果此时pivot的位置==k-1，找到了
   2. 如果此时pivot的位置 >k-1，只需在pivot左边寻找第k大
   3. 如果此时pivot的位置 <k-1，只需在pivot右边寻找第k-pivot大

这种方法的时间复杂度为$O(n)+O(n/2)+O(n/4)+...+O(1) = O(2n) = O(n)$

两种方法的比较：

代码

class Solution {
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int partition(int[] nums,int start,int end,int k){
        int pivotIdx = start+(end-start)/2;
        int pivot = nums[pivotIdx];
        int j = end;
        int i = start;
        swap(nums,i,pivotIdx);//把pivot交换至数组头
        while(i < j){
            while(i < j && nums[j] <= pivot){
                j--;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] >= pivot){
                i++;
            }
            nums[j] = nums[i];
        }
        nums[j] = pivot;
        if((j - start) == k-1){
            return pivot;
        }
        else if ((j - start) > k-1){
            return partition(nums,start,j-1,k);
        }
        else{
            return partition(nums,j+1,end,k-j+start-1);
        }
    }
    
    public int findKthLargest(int[] nums, int k) {
        return partition(nums,0,nums.length-1,k);
    }
}

lintcode 399.Nuts & Bolts Problem

题目

给定一组 n 个不同大小的 nuts 和 n 个不同大小的 bolts。nuts 和 bolts 一一匹配。 不允许将 nut 之间互相比较，也不允许将 bolt 之间互相比较。也就是说，只许将 nut 与 bolt 进行比较， 或将 bolt 与 nut 进行比较。请比较 nut 与 bolt 的大小

样例

给出 nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC']
你的程序应该找出bolts和nuts的匹配。
一组可能的返回结果是：
nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG']

分析

因为nuts和bolts两个数组在各自的内部不能互相比较，只能在两个数组之间的元素进行比较。所以这就需要利用一个array中的元素对另一个array进行partition，并反过来重复这一个过程，最终让两个array都满足comparator所定义的相同顺序。

代码

/**
 * public class NBCompare {
 *     public int cmp(String a, String b);
 * }
 * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
public class Solution {
    /**
     * @param nuts: an array of integers
     * @param bolts: an array of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
     public void quicksort(String[] nuts,String[] bolts,NBComparator compare,int start,int end){
         if(start >= end) return;
         //选取bolts中的第一个元素作为pivot，计算在nuts中对应的元素的位置
         int nuts_pivotidx = partition(nuts,bolts[start],compare,start,end);
         //利用nuts中的pivot对bolts中元素排序
         partition(bolts,nuts[nuts_pivotidx],compare,start,end);
         //对picot左边右边分别排序
         quicksort(nuts, bolts, compare, start, nuts_pivotidx - 1);
         quicksort(nuts, bolts, compare, nuts_pivotidx + 1, end);
     }
     
     //输入nuts和bolts中的pivot,对nuts排序，返回对应元素的位置
     //输入bolts和nuts中的pivot,对bolts排序，返回对应元素的位置
     public int partition(String[] str,String pivot,NBComparator compare,int start,int end){
         //在另一个数组中找到对应的螺丝或者螺母
         for(int i = start;i <= end;i++){
             if(compare.cmp(str[i],pivot) == 0 || 
             compare.cmp(pivot,str[i]) == 0){
                 swap(str,i,start);
                 break;
             }
         }
         //快速排序
         String pivotTemp = str[start];
         int left = start;
         int right = end;
         while(left < right){
             while(left < end && (compare.cmp(str[right], pivot) == -1 || 
            compare.cmp(pivot,str[right]) == 1)){
                right--;
            }
            str[left] = str[right];
             while(left < end && (compare.cmp(str[right], pivot) == 1 || 
            compare.cmp(pivot, str[right]) == -1)){
                left++;
            }
            str[right] = str[left];
        }
        str[left] = pivotTemp;    
        return left;
     }
     
     //交换元素
     public void swap(String[] strings,int i,int j){
         String temp = strings[i];
         strings[i] = strings[j];
         strings[j] = temp;
     }
     
     
    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
        // write your code here
        if(nuts == null || bolts == null) return;
        if(nuts.length != bolts.length) return;
        quicksort(nuts,bolts,compare,0,nuts.length-1);
    }
};

2.窗口类

Minimum Size Subarray Sum

题目

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

返回数组中元素和>=s的最长子数组的长度

分析

两指针控制滑动窗口类问题，当窗口内元素和<s时右指针向右滑动，更新最大长度

当窗口内元素和>=s时，左指针向右滑动至<s，无需更新最大长度

代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int minLen = Integer.MAX_VALUE;
        int i = 0;
        int sum = 0;
        for(int j = 0;j < nums.length;j++){
            sum += nums[j];
            while(sum >= s){
                minLen = Math.min(minLen,j-i+1);
                sum -= nums[i];
                i++;
            }
        }
        return minLen == Integer.MAX_VALUE?0:minLen;
    }
}

Longest Substring Without Repeating Characters

题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

查找字符串中没有重复元素的最长子串

思路

记录窗口中出现过哪些字母，当遇到重复字母的时候窗口缩小

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256];//相当于hashmap
        int i = 0;
        int j = 0;
        int maxlen = 0;
        while(j < s.length()){
            if(map[s.charAt(j)] == 0){
                map[s.charAt(j)] = 1;
                maxlen = Math.max(maxlen,j-i+1);
                j++;
            }
            //map[s.charAt(j)] == 1
            else{
                while(s.charAt(j) != s.charAt(i)){
                    map[s.charAt(i)] = 0;
                    i++;
                }
                i++;
                j++;
            }
        }
        return maxlen;
    }
}

Minimum Window Substring

题目

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

返回s中能够包含t的最短子串

思路

滑动窗口+hashtable的思想

首先需要两个hash表，一个存储t中的字母，一个存储s中子串的字母，还需要一个能够判别s中的子串是否能够包含t的函数。

然后两指针滑动窗口，右指针向右滑动，当滑窗中的子串能够包含t时，窗口缩小，左指针右移，更新最短窗口，直到窗口内子串不足以包含t中全部字母，此时右指针继续向后移动，重复上述过程。

代码

class Solution {
    //判断s是否包含t
    public boolean isContain(int[] mapT,int[] mapS){
        for(int i = 0;i < mapT.length;i++){
            if(mapS[i] < mapT[i]){
                return false;
            }
        }
        return true;
    }

    public String minWindow(String s, String t) {
        int[] mapT = new int[256];
        int[] mapS = new int[256];
        int minlen = Integer.MAX_VALUE;
        StringBuilder minWindow = new StringBuilder();
        for(char ch : t.toCharArray()){
            mapT[ch]++;
        }
        int i = 0;
        for(int j = 0;j < s.length();j++) {
            mapS[s.charAt(j)]++;
            while(isContain(mapT,mapS)){
                if(minlen > j-i+1){
                    minlen = j-i+1;
                    minWindow = new StringBuilder(s.substring(i,j+1));
                }
                mapS[s.charAt(i)]--;
                i++;
            }
        }
        if(minlen == Integer.MAX_VALUE){
            return "";
        }
        else return minWindow.toString();
    }
}

Longest Substring with At Most K Distinct Characters

题目

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

在字符串中找到一个子串，最多包含k个不同的字母，返回满足这样条件的子串的最大长度。

分析

还是滑窗+hash表

用hash表存储当前子串中字母，用charNum存储子串中的不同字母个数

1. 当窗口内字母个数<=k时右指针向右滑动，扩大窗口，更新窗口大小
2. 当窗口内字母个数>k时，左指针右移，缩小窗口，

代码

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] map = new int[256];
        int charNum = 0;
        int i = 0;
        int maxlen = 0;
        for(int j = 0;j < s.length();j++){
            //之前已经出现过这个字母了
            if(map[s.charAt(j)]>0){
                map[s.charAt(j)]++;
                maxlen = Math.max(maxlen,j-i+1);
            }
            //之前没出现过这个字母,但出现的字母数<k
            else if (charNum < k){
                map[s.charAt(j)]++;
                charNum++;
                maxlen = Math.max(maxlen,j-i+1);
            }
            //之前没出现过这个字母,但出现的字母数==k
            else {
                map[s.charAt(j)]++;
                charNum++;
                while(charNum > k){
                    if(map[s.charAt(i)] == 1){
                        map[s.charAt(i)]--;
                        charNum--;
                    }
                    else {
                        map[s.charAt(i)]--;
                    }
                    i++;
                }
            }
        }
        return maxlen;
    }
}

两个数组两个指针

最小差

题目

给定两个整数数组（第一个是数组 A，第二个是数组 B），在数组 A 中取 A[i]，数组 B 中取 B[j]，A[i] 和 B[j]两者的差越小越好(|A[i] - B[j]|)。返回最小差。

样例

给定数组 A = [3,4,6,7]， B = [2,3,8,9]，返回 0。

给定两个数组，返回两个数组元素之间的最小差

分析

baseline:双层for循环，A中循环一遍B中循环一遍，计算每两个元素之间的差值取最小，时间复杂度：$O(n^2)$

优化：

先排序，排序之后遍历A中元素，用二分查找的思路在B中寻找与元素A[i]差值最小的元素，时间复杂度：$O(nlogn)$

骚操作：

两指针ij分别指向AB，更新A[i]和B[j]的差值

当A[i]<B[j]时，i后移，反之j后移

代码

public int smallestDifference(int[] A, int[] B) {
    // write your code here
    Arrays.sort(A);
    Arrays.sort(B);
    int i = 0;
    int j = 0;
    int min = Integer.MAX_VALUE;
    while(i < A.length && j < B.length){
        min = Math.min(min,Math.abs(A[i]-B[j]));
        if(A[i] < B[j]){
            i++;
        }
        else {
            j++;
        }
    }
    return min;
}

Smallest Range

题目

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

> Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
> Output: [20,24]
> Explanation: 
> List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
> List 2: [0, 9, 12, 20], 20 is in range [20,24].
> List 3: [5, 18, 22, 30], 22 is in range [20,24].
>

给定k个数组，找到最短的区间，该区间需满足包含来自每个数组的至少一个元素

分析

k个数组k个指针，k个指针中的最大最小即是当前情况下的区间。

每次将值最小的指针向后移动，更新当前情况下的区间长度。

这里就需要找到哪个指针所指的值是最小的了，所以我们需要一个最小堆来维护k个指针中的最小值。

另外，我们还需要计算k个指针中的最大值，这个最大值用一个变量max维护就可以了，每次入堆的元素都跟当前max比较更新一下就好。

代码

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class SmallestRange {
  //定义结构Node，存储节所在的数组idx和值
    class Node{
        int idx;
        int val;
        Node(int idx,int val){
            this.idx = idx;
            this.val = val;
        }
    }
    public int[] smallestRange(List<List<Integer>> nums) {
        int[] idx = new int[nums.size()];//代表指针指向每一个数组
        Comparator<Node> cmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.val - o2.val;
            }
        };
        PriorityQueue<Node> minheap= new PriorityQueue<>(cmp);//最小堆
        int max  = Integer.MIN_VALUE;//存储当前遇到的最大值
        int minRangeLen = Integer.MAX_VALUE;//存储最小区间的长读
        int[] minRange = new int[2];//存储最小区间
        //先把所有list第一个元素先入堆，同时记录最大值
        for(int i = 0;i < idx.length;i++){
            int val = nums.get(i).get(idx[i]);
            minheap.add(new Node(i,val));
            max = Math.max(max,val);
        }
        //出堆
        while (!minheap.isEmpty()){
            //取堆顶元素
            Node temp = minheap.poll();
            //更新当前最小区间的长度
            if(max-temp.val < minRangeLen){
                minRangeLen = max-temp.val;
                minRange[0] = temp.val;
                minRange[1] = max;
            }
            //堆顶元素所在的区间指针后移一位
            idx[temp.idx]++;
            //如果对顶元素所在的区间指针溢出了，跳出
            if(idx[temp.idx] == nums.get(temp.idx).size()){
                break;
            }
          //找到下一个值，更新max，入堆
            int nextval = nums.get(temp.idx).get(idx[temp.idx]);
            max = Math.max(max,nextval);
            minheap.add(new Node(temp.idx,nextval));
        }
        return minRange;
    }
}

Partition Labels

题目

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

> Input: S = "ababcbacadefegdehijhklij"
> Output: [9,7,8]
> Explanation:
> The partition is "ababcbaca", "defegde", "hijhklij".
> This is a partition so that each letter appears in at most one part.
> A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
>

给定一个字符串，要求将字符串分割，保证每个字母只出现在一个子串中，最终返回分割的字符串长度

分析

由于每个字母只能出现在一个字符串中，比如第一个字母a，其所在的子串至少要从第一个a到最后一个a。
S = "ababcbacadefegdehijhklij"
     ↑       ↑
     i       maxRight
但此时并不一定找到第一个合适的分割点了，因为在这两个a中其他字母，有可能出现在后半段中，所以我们还需要遍历这两个指针中间的字母，确定每一个字母在字符串中出现的最后位置，在这个过程中，前后两个指针的距离可能会变得更远，中间的每一个元素都需要遍历到。所以我们用maxRight来存储当前遍历过的字母的最远位置，则i的遍历区间应该是while (i <= maxright)。

代码

class Solution {
    List<Integer> result = new ArrayList<>();
    public void partition(String s,int start,int end){
        if(start > end){
            return;
        }
        int i = start;
        int j = end;
        int maxright = i;//初始化maxright
        while (i <= maxright){
            char ch = s.charAt(i);
            while (s.charAt(j) != ch){
                j--;
            }//找到ch出现的最后一个位置
            maxright = Math.max(maxright,j);//更新最远距离
            if(i == maxright){//找到了最后一个，跳出
                break;
            }
            i++;
            j = end;
        }
      //更新结果集，继续分割右边
        result.add(maxright-start+1);
        partition(s,maxright+1,end);
    }
    public List<Integer> partitionLabels(String S) {
        partition(S,0,S.length()-1);
        return result;
    }
}