今日主題，雙指針。

11. 盛最多水的容器

問題描述

給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器。

解題思路-暴力解法

將數(shù)組中的元素兩兩組合，求出所有組合構(gòu)成的容器可以容納的水量。取其中的最大值返回。

代碼實現(xiàn)-暴力解法

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        for(int i = 0; i < height.length - 1; i++){
            for(int j = i + 1; j < height.length; j++){
                int area = Math.min(height[i], height[j]) * (j - i);
                if(area > maxArea){
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }
}

• 時間復(fù)雜度O(n^2)
• 空間復(fù)雜度O(1)

解題思路-雙指針

經(jīng)過觀察可以發(fā)現(xiàn)，能容納水的高度由較小的邊界值決定。
我們可以利用頭尾指針對數(shù)組進行遍歷，然后每次都將較小的指針往內(nèi)移動。
這是因為如果將較大的指針往內(nèi)移動的話，所容納的水量一定不會變多（最大高度不會超過較小的邊界值，左右的寬度一定會縮?。?。

代碼實現(xiàn)-雙指針

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

75. 顏色分類

問題描述

給定一個包含紅色、白色和藍(lán)色，一共 n 個元素的數(shù)組，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。

解題思路

兩次遍歷。首先，統(tǒng)計nums數(shù)組中0、1、2的個數(shù)；然后，將元素0、1、2填入nums數(shù)組中的相應(yīng)位置

代碼實現(xiàn)

class Solution {
    public void sortColors(int[] nums) {
        //統(tǒng)計nums數(shù)組中0、1、2的個數(shù)
        int[] colorNums = new int[3];
        for(int i = 0; i < nums.length; i++){
            colorNums[nums[i]]++;
        }
        //重新將元素0、1、2填入nums數(shù)組
        int index = 0;
        while(colorNums[0] > 0){
            nums[index++] = 0;
            colorNums[0]--;
        }
        while(colorNums[1] > 0){
            nums[index++] = 1;
            colorNums[1]--;
        }
        while(colorNums[2] > 0){
            nums[index++] = 2;
            colorNums[2]--;
        }
    }
}

解題思路2-雙指針

也可以利用雙指針實現(xiàn)一趟掃描。在遍歷過程中不斷將0交換至數(shù)組頭部，將2交換至數(shù)組尾部

代碼實現(xiàn)2-雙指針

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p2 = nums.length -1;
        int i = 0;
        while(i <= p2){
            //將0交換至數(shù)組頭部
            if(nums[i] == 0){
                swap(nums, i, p0++);
                i++;
            }else if(nums[i] == 2){
                //將2交換至數(shù)組尾部
                //此時索引不自增，因為如果原來的nums[p2]==2時，需要繼續(xù)將其交換至尾部
                swap(nums, i, p2--);
            }else{
                i++;
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        if(i == j){
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

19. 刪除鏈表的倒數(shù)第 N 個結(jié)點

問題描述

給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結(jié)點，并且返回鏈表的頭結(jié)點。
進階：你能嘗試使用一趟掃描實現(xiàn)嗎？

解題思路

此題的關(guān)鍵在于如何通過一趟掃描找到第n個節(jié)點的前驅(qū)節(jié)點。
首先，讓快指針比慢指針先走n個節(jié)點；然后fast、slow同時出發(fā)，fast到尾節(jié)點時，slow剛好在倒數(shù)第n-1個節(jié)點。

代碼實現(xiàn)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //添加虛擬頭節(jié)點dummyHead
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;


        ListNode fast = dummyHead, slow = dummyHead;

        //fast節(jié)點先走n步
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        //fast、slow同時出發(fā)，fast到尾節(jié)點時，slow剛好在倒數(shù)第n-1個節(jié)點
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummyHead.next;
    }
}

234. 回文鏈表

問題描述

請判斷一個鏈表是否為回文鏈表。

解題思路

首先，利用快慢指針，拿到后半部分鏈表的頭節(jié)點slow；
然后，反轉(zhuǎn)后半部分鏈表；
最后，比較前后鏈表是否相同；

代碼實現(xiàn)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
       //1.利用快慢指針，拿到后半部分鏈表的頭節(jié)點slow
       ListNode slow = head, fast = head;
       while(fast != null && fast.next != null){
           slow = slow.next;
           fast = fast.next.next;
        }
        if(fast != null){
            slow = slow.next;
        }
        //2.反轉(zhuǎn)后半部分鏈表
        ListNode tail = reverse(slow);

        //3.做比較
        boolean isPalindrome = true;
        while(tail != null){
            if(head.val != tail.val){
                isPalindrome = false; 
            }
            head = head.next;
            tail = tail.next;
        }
        return isPalindrome;
    }

    //反轉(zhuǎn)鏈表
    public ListNode reverse(ListNode head){
        ListNode prev = null,cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        } 
        return prev;
    }
}