---
tags: DSA in JavaScript
---
# Ch.5 Problem Solving Patterns

本章開始介紹一些常見的問題模式，大部分的模式並非正式名稱，只是作者方便而取名的。
以下為作者列出的 4 種模式：
1. [Frequency Counters](#Frequency-Counters)
2. [Multiple Pointers](#Multiple-Pointers)
3. [Sliding Window](#Sliding-Window)
4. [Divide And Conquer](#Divide-And-Conquer)

以下來一一介紹

## Frequency Counters
- 使用物件 (object) 或集合 (set) 來記錄輸入的值與出現的頻率
- 可以省下使用巢狀迴圈或是其他會造成 O(n^2^) 的陣列或字串的方法
### 類似題目
**validAnagram**
> 比對兩個字串是否都有出現相同的字母與頻率 (不用照順序)

function validAnagram(str1, str2) {
    // 如果一模一樣的話就直接回傳 true
    if (str1 === str2) {
        return true
    }
    // 如果長度不一樣的話，直接回傳 false
    if (str1.length !== str2.length) {
        return false
    }
    
    // 建立一個物件來存放第一個字串的字母與出現頻率
    const lookup = {}
    for (const char of str1) {
        lookup[char] = (lookup[char] || 0) + 1
    }
    
    // 遍歷第二個字串，將 lookup 對應的字母減去
    // 若在 lookup 找不到字母，則直接回傳 false
    for (const char of str2) {
        if (!lookup[char]) {
            return false
        } else {
            lookup[char]--
        }
    }
    return true
}

## Multiple Pointers
- 建立一個指標，大多用來指向陣列或字串的位置 (index)
- 按照使用情境，這個指標會從不同地方 (前、中、後) 開始，也會往不同地方移動
- 在需要縮減空間複雜度的情境下非常實用
### 類似題目
**countUniqueValues**
> 給定一個由小到大排列的正整數陣列，算出陣列內有幾種不同的數字

function countUniqueValues (arr) {
  // 如果 arr 長度為 0 (空物件)，直接回傳 false
  if (arr.length === 0) {
    return 0
  }
  // 建立一個指標，起始位置為 arr[0]
  let ptr = 0

  // 開始遍歷陣列 arr
  for (const element of arr) {
    if (arr[ptr] !== element) {
      // 如果指標指向的元素與目前遍歷的元素不一樣，將指標往前一格
      ptr++
      // 然後將指標下的元素改為目前的元素
      arr[ptr] = element
    }
  }
  // 因為指標只有在數字'不一樣'的情況下才會移動
  // 因此可以直接回傳指標位置 + 1 (因為位置從 0 開始)
  return ++ptr
}

## Sliding Window
- 建立一個視窗 (window)，可以是一個陣列或數字
- 依據情況不同，視窗會有各種不同變化 (增加、減少，或重新賦值)
- 需要持續追蹤一串字串或陣列的子集合很有用
### 類似題目
**maxSubArraySum**
> 給定一個陣列與一個正整數 ***n***，找出陣列中連續 ***n*** 個數的最大和。
> 如果陣列長度小於 ***n*** ，則回傳 null

// 我還沒寫，不要打我

## Divide And Conquer
- 將量大的大資料切分成模式固定且可直接處理的多個小資料
- 重複這類個別擊破的步驟直到解決問題為止
- 可以大幅降低時間複雜度
### 類似題目
**Merge Sort**
> 作者會在排序的章節進行詳細解說
> ~~我大概知道這個在幹嘛，但我講不出來~~