iT邦幫忙

2021 iThome 鐵人賽

DAY 10
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 10

【第十天 - Two-pointer 介紹】

Q1. Two-pointer 是什麼?

  • 我個人認為雙指標 ( Two-pointer ) 比較像寫題目的技巧,一些演算法也會用到雙指標的概念,例如昨天介紹到的 Quick Sort,就有使用到雙指標的技巧
    • 雙指標主要可以分為兩種:
      • 快慢指標:兩個指標一起指向頭,或是一起指向尾,一個指標可能是按著順序走訪,一個是根據問題的需求來移動,讓指標會有快慢之分,他們都會一起向右移動,也稱為同向指標,類似 Quick Sort 的 Lomuto
        1

      • 左右指標:兩個指標一個指向頭,一個指向尾,k 會向右移動,j 向左移動,兩個指標會逐漸靠近,也稱為反向指標,類似 Quick Sort 的 Hoare
        2

Q2. 學會 Two-pointer 概念可以做什麼 ?

  • 可以在以下情境考慮 Two pointer:
    • 題目禁止使用額外空間,原地交換值、比較
    • 題目給已經排序過的資料,然後對此資料進行一些操作,例如刪掉重複的元素等...
  • 雙指標可以分為兩種:
    1. 快慢指標可以解決:

      • 將已經排序過的資料,把重複的元素刪掉

        1

      • 判斷 linked list 是否有環,若是兩個指標相遇,代表有環

      2

    2. 左右指標可以解決的題目類型:

      1. 反轉陣列,把 k 與 j 值交換

        3

      2. 檢查 string 是否回文,檢查 k 位置的值 是否等於 j 位置的值

        4

      3. 在已經排序過的資料中,題目會給一個 target ,找出資料中哪兩個數字相加為 target

        5

      4. Quick Sort 的 Hoare 方法就是使用左右指標的概念將數字進行排序

        6

Lab. 明天要解的題目:

  • 明天要解的題目有兩題,分別是:
      1. Remove Duplicates from Sorted Array
      1. Two Sum II - Input array is sorted

26. Remove Duplicates from Sorted Array

  • 題目連結:https://leetcode.com/problems/valid-parentheses/

  • 題目敘述:

    • 題目會給你一個從小排序到大的資料,但是裡面有重複的元素,你需要把他刪掉
    • 有些語言是不能把資料裡的元素刪掉 ( array 長度不能被改變),所以你需要把後面所有元素往前平移
    • 不過我們這邊使用的是 python,可以刪除任意位置的元素 ,所以只要遇到多餘的就刪掉即可,並且回傳刪完重複元素後的資料長度

    1

  • 測資的 Input/Output

    • 題目如果給你 [1,1,2] 那你要把多餘的元素刪掉,刪完重複元素後的資料長度

      2

  • 題目的條件

    • nums 裡的資料,會有 0~ 30000 個
    • 每一筆資料都會介於 -100~100
    • nums 裡的資料是經過排序的 (從小排到大)

    3

167. Two Sum II - Input array is sorted

  • 題目連結:https://leetcode.com/problems/valid-parentheses/

  • 題目敘述:

    • 題目會給你一個從小排序到大的資料,跟希望找到的兩數相加的和 (target)

    • 你需要找出哪兩個位置的值,相加會等於 target

    • 哪兩個位置的值相加為 target,只會有一種答案

    • 同一個元素不能加兩次

      1

  • 測資的 Input/Output

    • 題目會給你一個遞增的數列,跟希望找到的目標總和 (target)

    • 回傳一個 list 結構的資料,裡面要包含相加會等於 target 的 index

      2

  • 題目的條件

    • 資料長度為 2~30000

    • 每一筆資料介於 -1000~1000

    • 資料由小排序到大

    • 相加的目標 (target) 介於 -1000~1000

    • 只會有唯一解

      3


上一篇
【第九天 - Quick Sort 題目分析】
下一篇
【第十一天 - Two-pointer 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言