[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用

天下武功, 無堅不破, 唯快不破 ——— 某功夫大佬

本文為我,

leetcode easy player

algorithm小xuo生

在刷題過程中對快慢指針的應用的總結

ps: 向

leetcode

裡耐心寫解題, 特别是畫圖解題的各位算法大佬們緻敬, 給大佬們遞茶🍵

什麼是快慢指針

快慢 說的是移動的速度, 即每次移動的步長的大小
指針 為記錄變量記憶體位址的變量, 用它能間接通路變量的值

為了更直覺的了解快慢指針, 請看如下

c++

demo

在記憶體中開辟容量為11個整型元素的數組存儲空間

初始化整型快慢指針變量都記錄數組第一個元素的記憶體位址

167 兩數之和

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while(left<right){
            int sum=numbers[left]+numbers[right];
            if(sum==target){
                return new int[]{left+1,right+1};
            }else if(sum>target){
                right--;
            }else{
                left++;
            }
        }
        return new int[]{-1,-1};

    }
}

26. 删除有序數組中的重複項

class Solution {
    public int removeDuplicates(int[] nums) {
      int slower=0,faster=0;
      while(faster<nums.length){
         if(nums[slower]!=nums[faster]){
             slower++;
             nums[slower]=nums[faster];
         }
         faster++;
      }
      return slower+1;

    }
}

使用雙指針實作字元串反轉

public static String reverseString(String str) {

if (str == null || str.length() == 0 || str.length() == 1) {

return str;

}

char[] chars = str.toCharArray();

//指向數組首元素

int start = 0;

//指向數組尾元素

int end = chars.length - 1;

char temp;

while (start < end) {

//字元互換

temp = chars[start];

chars[start] = chars[end];

chars[end] = temp;

//移動索引位置

start++;

end--;

}

return String.valueOf(chars);

}

public static void main(String[] args) {

String str = "gfedcba";

System.out.println("字元串:" + str);

System.out.println("反轉後:" + reverseString(str));

}

字元串:gfedcba

反轉後:abcdefg

判斷連結清單是否有環

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slower=head,faster=head;
        while(faster!=null&&faster.next!=null){
            faster=faster.next.next;
            slower=slower.next;
            if(faster==slower){
                return true;
            }
        }
        return false;
    }
}

快慢指針&雙指針[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用什麼是快慢指針判斷連結清單是否有環尋找連結清單的入環節點尋找重複數删除連結清單的倒數第N個元素連結清單的中間節點回文連結清單

無環的連結清單是長這樣的

有環的連結清單是長這樣的

染色标記法, 缺點: 改變了連結清單的結構, 若連結清單為隻可讀的則不可取, 而且此方法需開辟額外的 O(n)
存儲空間記錄标記資訊

var hasCycle = function(head) { let res = false while (head && head.next) { if (head.flag) { res = true break } else { head.flag = 1 head = head.next } } return res };
哈希表記錄法, 缺點: 哈希表需開辟額外的 O(n)
空間

var hasCycle = function(head) { const map = new Map() while (head) { if (map.get(head)) { return true } else { map.set(head, head) head = head.next } } return false }
快慢指針法, 兔子與烏龜同時在頭節點出發, 兔子每次跑兩個節點, 烏龜每次跑一個節點, 如果兔子能夠追趕到烏龜, 則連結清單是有環的

因為不管有沒有環, 以及進環前和進換後耗時都與資料規模成正比, 是以時間複雜度為

O(n)

, 因為隻需額外的常數級存儲空間記錄兩個指針, 是以空間複雜度為

O(1)

var hasCycle = function(head) {
  let slowPointer = head
  let fastPointer = head
  while (fastPointer && fastPointer.next) {
    slowPointer = slowPointer.next
    fastPointer = fastPointer.next.next
    if (fastPointer === slowPointer) {
      return true
    }
  }
  return false
}
複制代碼

尋找連結清單的入環節點

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode faster=head,slower=head;
        while(faster!=null&&faster.next!=null){
            faster=faster.next.next;
            slower=slower.next;
            if(faster==slower){
                slower=head;
                while(slower!=faster){
                    slower=slower.next;
                    faster=faster.next;
                }
                return faster;
            }
        }
        return null;
        
    }
}

此題也可用标記法和哈希表法解決, 用快慢指針法解決如下

還是前面的龜兔賽跑, 當兔子追到烏龜的時候, 假設有另外一隻烏龜從頭節點開始往前爬, 每次也隻爬一個節點, 那麼兩隻烏龜會在入環的節點相遇

這隻是一個巧合嗎, 我們來分析一下

假設入環之前的長度為 L , 入環之後快慢指針第一相遇時快指針比慢指針🐢多跑了 N 圈, 每一圈的長度為 C , 此時快指針🐰在環内離入環節點的距離為 C'
此時慢指針🐢走過的距離為: L + C'
此時快指針🐰走過的距離為: L + C' + N * C
因為快指針🐰的速度是慢指針🐢的兩倍, 是以有: 2 * (L + C') = L + C' + N * C
整理後得到: (N - 1) * C + (C - C') = L
由此可知, 若此時有兩個慢指針🐢同時分别從連結清單頭結點和快慢指針第一次相遇的節點出發, 兩者必然會在入環節點相遇

var detectCycle = function(head) {
  let slowPointer = head
  let fastPointer = head
  while (fastPointer && fastPointer.next) {
    slowPointer = slowPointer.next
    fastPointer = fastPointer.next.next
    if (slowPointer === fastPointer) {
      slowPointer = head
      while (slowPointer !== fastPointer) {
        slowPointer = slowPointer.next
        fastPointer = fastPointer.next
      }
      return slowPointer
    }
  }
  return null
};
複制代碼

尋找重複數

class Solution {
    public int findDuplicate(int[] nums) {
           	 int left=1,right=nums.length;
		 while(left<right){
			 int middle=(left+right)/2;
			 int sum=0;
			 for(int num :nums){
				 if(num<=middle){
					 sum++;
				 }
			 }
			 if(sum>middle){
				 right=middle;
			 }else{
				 left=middle+1;
			 }
		 }
		 return left;
    }
}

此題暴力解法為先排序再尋找重複的數字, 注意不同

JavaScript

引擎對

sort

的實作原理不一樣,

V8

引擎

sort

函數對數組長度小于等于 10 的用插入排序(時間複雜度

O(n^2)

, 空間複雜度

O(1)

)，其它的用快速排序(時間複雜度

O(nlogn)

, 遞歸棧空間複雜度

O(logn)

), 參考github.com/v8/v8/blob/…

這一題可以利用尋找連結清單的入環節點的思想, 把數組當成對連結清單的一種描述, 數組裡的每一個元素的值表示連結清單的下一個節點的索引

如示例1中的

[1, 3, 4, 2, 2]

把數組索引為0的元素當成連結清單的頭節點
索引為0的元素的值為1, 表示頭節點的下一個節點的索引為1, 即數組中的3
再下一個節點的索引為3, 即為第一個2
再下一個節點的索引為2, 即為4
再下一個節點的索引為4, 即為第二個2
再下一個節點的索引為2, 即為4
此時形成了一個環
而形成環的原因是下一節點的索引一緻, 即為重複的數字

var findDuplicate = function(nums) {
  let slowPointer = 0
  let fastPointer = 0
  while (true) {
    slowPointer = nums[slowPointer]
    fastPointer = nums[nums[fastPointer]]
    if (slowPointer == fastPointer) {
      let _slowPointer = 0
      while (nums[_slowPointer] !== nums[slowPointer]) {
        slowPointer = nums[slowPointer]
        _slowPointer = nums[_slowPointer]
      }
      return nums[_slowPointer]
    }
  }
};
複制代碼

删除連結清單的倒數第N個元素

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast=head,slow=head;
        ListNode result=new ListNode(0,head);
        ListNode dumpy=result;
        if(head.next==null&&n>0){
            return null;
        }
        while(n>0&&fast!=null){
            fast=fast.next;
            n--;
        }
      
        while(fast!=null){
            fast=fast.next;
            dumpy=dumpy.next;
        }
        dumpy.next=dumpy.next.next;
        return result.next;

    }
}

要删除連結清單的倒數第N個元素, 需要找到其倒數第N + 1個元素, 讓這個元素的next指向它的下下一個節點

此題可利用兩次正向周遊連結清單, 或者一次正向周遊的同時記錄前節點, 然後再反向周遊

題目的進階要求隻使用一趟掃描, 利用快慢指針可實作, 我們最終想要的烏龜和兔子的位置是這樣的, 它們之間相距

N + 1

個節點, 這樣烏龜所在的位置即為我們想要找的那個節點--被删除的節點前面的一個節點

為友善處理頭節點, 我們建立

dummy

虛拟頭節點

讓快指針🐰和慢指針🐰最開始都指向

dummy

節點

讓快指針🐰向前移動

N + 1

個節點, 慢指針保持原地不動

然後兩個指針以同樣的速度直至快指針🐰移動至

null

此時慢指針🐢移動到的位置即為被删除的指針前面的一個指針

var removeNthFromEnd = function(head, n) {
  const dummy = new ListNode(null)
  dummy.next = head
  let slowPointer = dummy
  let fastPointer = dummy
  while (n-- > -1) {
    fastPointer = fastPointer.next
  }
  while (fastPointer !== null) {
    slowPointer = slowPointer.next
    fastPointer = fastPointer.next
  }
  slowPointer.next = slowPointer.next.next
  return slowPointer === dummy ? slowPointer.next : head
};
複制代碼

連結清單的中間節點

快慢指針法, 快慢指針開始時都指向頭節點, 快指針每次移動一個節點, 慢指針每次移動兩個節點

對于奇數連結清單, 當快指針下一節點為

null

時, 慢指針指向的節點即為所求

對于偶數連結清單, 當快指針指向

null

時, 慢指針指向的節點即為所求

var middleNode = function(head) {
  let slowPointer = head
  let fastPointer = head
  while (fastPointer !== null && fastPointer.next !== null) {
    slowPointer = slowPointer.next
    fastPointer = fastPointer.next.next
  }
  return slowPointer
};
複制代碼

回文連結清單

把連結清單變成雙向連結清單, 并從兩端向中間比較

時間複雜度為

O(n)

, 因為要存儲

prev

指針, 是以空間複雜度為

O(n)

var isPalindrome = function(head) {
  if (head === null) {
    return true
  } else {
    let headPointer = head
    let tailPointer = head
    while (tailPointer.next) {
      tailPointer.next.prev = tailPointer
      tailPointer = tailPointer.next
    }
    while(headPointer !== tailPointer) {
      if (headPointer.next !== tailPointer) {
        if (headPointer.val === tailPointer.val) {
          headPointer = headPointer.next
          tailPointer = tailPointer.prev
        } else {
          return false
        }
      // 考慮偶數連結清單
      } else {
        return headPointer.val === tailPointer.val
      }
    }
    return true
  }
};
複制代碼

快慢指針

慢指針🐢依次通路下一個節點, 并翻轉連結清單
快指針🐰依次通路下下一個節點, 直到快指針🐰沒有下一個節點(奇數連結清單)或者快指針指向 null (偶數連結清單), 此時已完成了前半截連結清單的翻轉
依次比較前半截連結清單和後半截連結清單節點的值

對于奇數連結清單:

對于偶數連結清單:

時間複雜度

O(n)

, 空間複雜度

O(1)

var isPalindrome = function(head) {
  if (head === null) {
    return true
  } else if (head.next === null) {
    return true
  } else {
    let slowPointer = head
    let fastPointer = head
    let _head = null
    let temp = null
    // 找到中間節點, 并翻轉前半截連結清單,
    // 讓_head指向翻轉後的前半截連結清單的頭部,
    // 讓slow指向後半截連結清單的頭節點
    while (fastPointer && fastPointer.next) {
      _head = slowPointer
      slowPointer = slowPointer.next
      fastPointer = fastPointer.next.next
      _head.next = temp
      temp = _head
    }
    // 奇數連結清單跳過最中間的節點
    if (fastPointer) {
      slowPointer = slowPointer.next
    }
    while (_head) {
      if (_head.val !== slowPointer.val) {
        return false
      }
      _head = _head.next
      slowPointer = slowPointer.next
    }
    return true
  }
};
複制代碼

在一些場景, 如連結清單資料結構和判斷循環, 利用快慢指針創造的內插補點, 可節省記憶體空間, 減少計算次數

快慢指針, 一對快樂的指針, just be happy!

leetcode11 盛水最多的容器

class Solution {
    public int maxArea(int[] height) {
        int left=0,right=height.length-1,maxArea=0;
        if(height==null||height.length==0){
            return maxArea;
        }
        while(left<right){
            maxArea=Math.max(maxArea,Math.min(height[left],height[right])*(right-left));
            if(height[left]>height[right]){
                right--;
            }else{
                left++;
            }
        }
        return maxArea;
    }
    // public int maxArea(int[] height) {
    //     int maxArea=0;
    //     if(height==null||height.length==0){
    //         return maxArea;
    //     }
    //     for(int i=0;i<height.length-1;i++){
    //         int curHeight=height[i];
    //         for(int j=height.length-1;j>i;j--){
    //             if(height[j]>=height[i]){
    //                 maxArea=Math.max(maxArea,height[i]*(j-i));
    //                 break;
    //             }else{
    //                 maxArea=Math.max(maxArea,height[j]*(j-i));
    //             }
    //         }
    //     }
    //     return maxArea;
    // }
}

42. 接雨水

class Solution {
//     1.首先我們需要搞清楚，下标為i的雨水量是由什麼決定的.
// 是由i左右兩邊最大值中較小的那個減去height[i]決定的.例 [0,1,0,2,1,0,1,3,2,1,2,1]中，下标為2的位置 值為0，而它的用水量是由左邊的最大值1，右邊最大值3 中較小的那個 也就是1減去0得到的。

// 2.本題解的雙指針先找到目前維護的左、右最大值中較小的那個，例 目前 i 處左邊的最大值如果比右邊的小，那麼就可以不用考慮 i 處右邊最大值的影響了，因為 i 處 右邊真正的最大值絕對比左邊的最大值要大，在不斷周遊時，更新max_l和max_r以及傳回值即可。例 [0,1,0,2,1,0,1,3,2,1,2,1]中i=2時，值為0，此時max_l一定為1，目前max_r如果為2，即便max_r不是真正的i右邊的最大值，也可忽略右邊最大值的影響，因為右邊真正的最大值一定比左邊真正的最大值大。


   public int trap(int[] height) {
		 if(height==null||height.length==0){
			 return 0;
		 }
		 int result=0,left=0,right=height.length-1,leftMax=0,rightMax=0;
		 while(left<right){
			 int heightLeft=height[left];
			 int heightRight=height[right];
			 leftMax=Math.max(leftMax, heightLeft);
			 rightMax=Math.max(rightMax, heightRight);
			 if(leftMax<rightMax){
				 left++;
				 result+=(leftMax-heightLeft);
			 }else{
				 right--;
				 result+=(rightMax-heightRight);
			 }
		 }
		 return result;
		 
	 }


    // public int trap(int[] height) {
    //     if(height==null||height.length==0){
    //         return 0;
    //     }
    //     int result=0;
    //     Deque<Integer> stack=new LinkedList<Integer>();
    //     for(int i=0;i<height.length;i++){
    //         int curHeight=height[i];
    //         if(stack.isEmpty()){
    //             stack.push(i);
    //         }else{

    //             while(!stack.isEmpty()&&curHeight>height[stack.peek()]){
    //                 //當出現升高的柱子之後，低位柱子最右邊的索引
    //                 int rightIndex=stack.pop();
    //                 if(stack.isEmpty()){
    //                     break;
    //                 }
    //                 //最右邊柱子的左邊柱子可能之前已經被計算掉了一些，需要用左邊未計算的第一個柱子計算
    //                 //例如[4,2,0,3,2,5]  3時已經把之前2 0 就算，5時先把2計算，之後應該從4開始計算高度3的量
    //                 int leftIndex=stack.peek();
    //                 result+=(Math.min(curHeight,height[leftIndex])-height[rightIndex])*(i-leftIndex-1);
    //             }
    //             stack.push(i);
    //         }

    //     }
    //     return result;

    // }
}

原文在掘金: juejin.im/post/684490…

快慢指針&雙指針[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用什麼是快慢指針判斷連結清單是否有環尋找連結清單的入環節點尋找重複數删除連結清單的倒數第N個元素連結清單的中間節點回文連結清單

[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用

什麼是快慢指針

判斷連結清單是否有環

尋找連結清單的入環節點

尋找重複數

删除連結清單的倒數第N個元素

連結清單的中間節點

回文連結清單

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

LeetCode-110-平衡二叉樹-C語言

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

LeetCode OJ Binary Tree Right Side View

leetcode809

hdu7108哈希

快慢指針&amp;雙指針[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用什麼是快慢指針判斷連結清單是否有環尋找連結清單的入環節點尋找重複數删除連結清單的倒數第N個元素連結清單的中間節點回文連結清單

[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用

什麼是快慢指針

判斷連結清單是否有環

尋找連結清單的入環節點

尋找重複數

删除連結清單的倒數第N個元素

連結清單的中間節點

回文連結清單

繼續閱讀

快慢指針&雙指針[leetcode]靈魂畫師圖解🎨快慢指針在算法中的應用什麼是快慢指針判斷連結清單是否有環尋找連結清單的入環節點尋找重複數删除連結清單的倒數第N個元素連結清單的中間節點回文連結清單