# 刷題記錄

### 424. Longest Repeating Character Replacement (🎗️:Medium)

[題目連結](https://leetcode.com/problems/longest-repeating-character-replacement/)

#### 題目分類:Sliding Window

參考作法:https://www.youtube.com/watch?v=SLAKjysDODM

CODE: with javascript

var characterReplacement = function(s, k) {
    let strLength = s.length; //字串長度
    let maxLength = 0; //最多重複字串長度紀錄(return)
    let maxCount = 0; //window內最頻繁字母出現次數
    let left = 0; //window左邊界
    let right = 0; //window右邊界
    
    //做一個元素都為0長度26的array來計算每個字母出現次數，index=0的元素，代表的是a出現次數，index=1則是b出現次數...
    let charCount = new Array(26).fill(0);
    
    
    //right最大值:strLength-1 ，故while迴圈如下
    
    while(right < strLength) {
        //先找出window內最多出現次數的字母
        const charIndex = s.charCodeAt(right) - 'A'.charCodeAt(0);
        //計算目前right這個字母對應的index
        charCount[charIndex]++;//確定該字母index後，在出現次數array裡+1

        //對每個字母的出現次數maxCount做計算
        maxCount = Math.max(maxCount,charCount[charIndex])
        right++;

        //停止條件: 當window大小(right-left) 大於 同個字母最多出現數量maxCount + 可替換次數k ，因為代表這樣就沒辦法合成一個連續相同字母的字串了
        if(right-left > maxCount + k) {
            //因為window的left要往右移一格，剔除left在charCount內的計數一次，否則會多計算到前一個left字母的出現次數
            const leftIndex = s.charCodeAt(left) - 'A'.charCodeAt(0);//找出left字母代表的index;
            charCount[leftIndex]--;
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left);
    }
    return maxLength;
};

#### 時間複雜度 :
主要時間會花在while迴圈上，假如輸入的str長度為n，則這個迴圈最多會執行n次，需要線性時間O(n)，而迴圈內的操作只有包含加,減,比較大小，均是Constant time: O(1)，因此這整個算法的時間複雜度是O(n)

Performance:

---

### 567. Permutation in String (🎗️:Medium)

[題目連結](https://leetcode.com/problems/permutation-in-string/description/)

#### 題目分類:Sliding Window

CODE: with javascript

//先寫一個比較兩個array值是否都相同的函數arraysAreEqual
//補充: 不能用"==="來比較，因為"==="比較的會是該兩個array的引用，而不是值，如果用"==="，即便兩個array一模一樣也會是false;

function arraysAreEqual(arr1, arr2) {
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
};


var checkInclusion = function(s1, s2) {
    //s2<s1就結束
    if(s1.length > s2.length) {
        return false;
    }

    //做一個array來計算s1頻率，做一個array來計算窗口內字母頻率
    let s1Freq = new Array(26).fill(0);
    let windowFreq = new Array(26).fill(0);

    //初始話s1頻率array
    for(let i=0; i<s1.length;i++) {
        s1Freq[s1.charCodeAt(i) - 'a'.charCodeAt()]+=1;
    }

    //初始話第一個窗口頻率array
    for(j=0; j<s1.length;j++) {
        windowFreq[s2.charCodeAt(j) - 'a'.charCodeAt()]+=1;
    }
    //對s2 while迴圈
    let left = 0;
    let right = s1.length-1;
    while(right < s2.length) {
        if(arraysAreEqual(s1Freq,windowFreq)) {
            return true;
        }

        //剔除窗口左邊界的字母在windowFreq的計數，增加right+1項字母在windowFreq的計數
        windowFreq[s2.charCodeAt(left) - 'a'.charCodeAt()]-=1;
        windowFreq[s2.charCodeAt(right+1) - 'a'.charCodeAt()]+=1;

        //window左移
        left++;
        right++;

    }

    return false;

};

#### 時間複雜度 :
因為s1的長度是固定的，而窗口的長度也是，因此對它們進行迴圈的複雜度是O(1)，所以主要的算法時間會花在對s2的while迴圈，假設s2長度是n，那整體的算法時間複雜度就是O(n)

Performance:

---

### 76. Minimum Window Substring (🎗️:Hard)

[題目連結](https://leetcode.com/problems/minimum-window-substring/description/)

#### 題目分類:Sliding Window

CODE: with javascript

//先寫一個函式來驗證win這個map是否包含在ori內
//ori代表t字串的字母出現 類型:次數 的map
//win則是窗口的... map
function checkMap() {
    for (const [key,value] of ori.entires()) {
        if((win.get(key) || 0) < value) {
            return false;
        }
    }
    return true;
}


var minWindow = function(s, t) {

    let ori = new Map();//代表t字串內的 字母種類:次數 的map
    let win = new Map();//代表window字串內的 ...

    // 對t這個str做遍歷 把ori這個map做好
    for(let i=0;i<t.length;i++) {
        let charCurrent = t.charAt(i)
        ori.set(charCurrent, (ori.get(charCurrent)||0)+1);
    };
    //窗口左右邊界
    let left = 0;
    let right = -1;
    //紀錄子字串的最小值，因為要比大小所以一開始先設定最大的數infinity
    let minLength = Infinity;
    //ansL,R是最後要來把s內子字串取出所需的index，起始點是-1是為了防止整個迴圈跑完都找不到子字串時，要回傳空字串的情況，
    let ansL = -1;
    let ansR = -1;
    let sLen = s.length;
    let requiredCount = ori.size; // 起始值是t字串內字母種類的數量，這個變數用來計算還有多少種字母在window中沒有被滿足，如果=0時就是，window內已經包含t所需要的所有字母種類及數量，因此可以開始減少左邊界以求最小的子字串長度

    //對s迴圈，主要是逐漸擴張右邊界，然後到最大之後開始縮小左邊界，最後找出最小長度的子字串
    while(right < sLen) {
        right++;
        //我們要先往右擴張完成最大子字串的map，
        if (ori.has(s.charAt(right))) {
            //win代表的是window內 字母:出現次數 的map
            win.set(s.charAt(right), (win.get(s.charAt(right)) || 0) + 1);
            //下方if條件代表window內已經滿足s.charAt(r)這個字母所需的最少數目
            if (win.get(s.charAt(right)) === ori.get(s.charAt(right))) {
                //因此還缺少的字母種類-1
                requiredCount--; 
            }
        }

        //第一個迴圈停止條件:已經找齊所需字母及數量，此時reuqiredCount=0，所以當滿足此條件時要記錄minLength並減少左邊界
        while (requiredCount === 0 && left <= right) {
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                ansL = left;
                ansR = left + minLength;
            }
            if (ori.has(s.charAt(left))) {
                win.set(s.charAt(left), win.get(s.charAt(left)) - 1);
                //如果減少左邊界之後會導致左邊界的那個字母數量不夠，那requiredCount就要+1，就會跳出這個減少左邊界第二迴圈，回到要擴張右邊界的第一迴圈
                if (win.get(s.charAt(left)) < ori.get(s.charAt(left))) {
                    requiredCount++; 
                }
            }
            //最後left都要左移一格
            left++;
        }
    }

    return ansL == -1 ? "" : s.slice(ansL,ansR);

};

#### 時間複雜度 :
假設s字串的長度是n，因為使用sliding window，逐漸往右遍歷整個字串s，所以第一個while迴圈的複雜度是O(n)，而內層又包含了一個while迴圈，但它的執行條件是當window內滿足s所需的字母種類和數目時才會執行，第二個while迴圈不是每次都會觸發，所以應該把它看成if的情況，是常數級時間，而worst case會發生在s,t長度相等的時候，base case是s長度n大於t，t是某一常數，承上，假設s字串的長度是n，t字串長度是t，這整個算法的time complecity是 f(n) = n+t , big O notation = O(N)

Performance:

---

### 239. Sliding Window Maximum (🎗️:Hard)
#### 最佳做法: Deque 待補齊

[題目連結](https://leetcode.com/problems/sliding-window-maximum/description/)

#### 題目分類:Sliding Window

CODE: with javascript

var maxSlidingWindow = function(nums, k) {
    let left = 0;
    let right = left + k - 1;
    let maxNumber = -Infinity; //紀錄當前window的最大值
    let maxIndex = -1;//紀錄最大值的那個index
    let arr = [];

    // 先找到第一个窗口的最大值，push進去
    for (let i = left; i <= right; i++) {
        if (nums[i] > maxNumber) {
            maxNumber = nums[i];
            maxIndex = i;
        }
    }
    arr.push(maxNumber);

    //right最大會在第 nums.length-1 項 但由於我們一開始就會right++所以要提前在num.length-2停止(也就是nums.length-2是right的最大index值)
    while (right < nums.length-1) {
        left++;
        right++;

        // 如果最大值不再窗口内，重新計算窗口內最大值
        if (maxIndex < left) {
            maxNumber = -Infinity;
            for (let i = left; i <= right; i++) {
                if (nums[i] > maxNumber) {
                    maxNumber = nums[i];
                    maxIndex = i;
                }
            }
        } else {
            // 否則就只要比現在的max跟右邊新進來的數就好，如果right比較大max就要改，right比較小那就只要直接再push一次
            if (nums[right] > maxNumber) {
                maxNumber = nums[right];
                maxIndex = right;
            }
        }

        arr.push(maxNumber);
    }

    return arr;
};

#### 時間複雜度
這題的時間主要是在while迴圈上，假設nums的長度為n，而k是window的長度，我們採用sliding window作法，總共會執行n-k次，然後如果最大值不在窗口内，while迴圈內還會遍歷一次window來找出新的最大值，此操作的複雜度為窗口長度k，剩下的operation皆為比大小或是加減，因此整體算法的時間複雜度是f(n)= O(n-k) + O(k)，big O notation是 O(n)

Performance:

---

### 206. Reverse Linked List (🎗️:Easy)

[題目連結](https://leetcode.com/problems/reverse-linked-list/description/)

#### 題目分類:Linked List

CODE: with javascript

//先做一個Node class
class Node {
    //因為Node建立時通常只有value沒有next，所以要預設next = null
    constructor(val, next=null) { 
        this.value = val;
        this.next = next;
    }

}



var reverseList = function(head) {
    if( head === null || head.next === null) {
        //如果沒有head 或 只有head自己一個就不用反轉，但在reversListBack中linked list的最後一個node的next也等於null，所以會在這個條件停止回傳head
        return head;
        
    }

    const reverseNext = reverseList(head.next);
    //在當前節點把下個節點當成head(反轉)
    head.next.next = head;
    //此時的head是linked list的最後一個node所以要清除原本的next 執行下個reversList
    head.next = null;
    

    return reverseNext;

};

#### 時間複雜度:
假設linked list內有n個node，則時間複雜度是O(n)

Performance:


---

### 21. Merge Two Sorted Lists (🎗️:Easy)

[題目連結](https://leetcode.com/problems/merge-two-sorted-lists/submissions/)

#### 題目分類:Linked List

CODE: with javascript

var mergeTwoLists = function(list1, list2) {
    let dummyHead = new ListNode(-1);
    //用dummyHead這個變數來標記整個合併list的頭部，因為最後我們需要回傳合併list的頭部
    let current = dummyHead;

    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            // 把 list1 設為 current.next，把當前的 list1 指針指向 list1 的一個節點
            current.next = list1;
            list1 = list1.next; // list1 調整完了
        } else {
            current.next = list2;
            list2 = list2.next; // list2 調整完了
        }
        current = current.next; // current 做完了
    }
    
    // 如果 list1 或 list2 其中一個列表已經遍歷完了，那就要把 current.next 指向另一個 list
    current.next = list1 !== null ? list1 : list2;
    //dummyHead.next指的就是這個mergeLinkedList的第一個node
    return dummyHead.next;
};

#### 時間複雜度:
假設list1長度為n，list2長度為m，則時間複雜度f(n) = O(n+m)，bigO Notation: O(n)

Performance:

#### 補充觀念

#### 原地演算法 [維基百科](https://zh.wikipedia.org/zh-tw/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)

**這題合併兩個linked list的方法，主要是更改list1,list2內每個node的next，並沒有額外開新的記憶體來儲存新的mergeLinkedList，所有的node仍在原來的記憶體空間上，我們只有開了dummyHead這個輔助變數，因此符合原地演算法的定義**

合併排序法有著許多優點： 時間複雜度勝過泡沫排序法、選擇排序法； 執行效能相較快速排序法更穩定一些； 記憶體存取相較於堆積排序法更連續一些； 甚至因為遞迴方式穩定，可以根據硬體特性特化出許多專門的晶片來處理小數列排序、平行排序等等，也可以讓編譯器預先優化。

當然，在實作合併兩個排好序的陣列時，總是得開一塊新的記憶體空間，然後把資料騰過去1，然後合併完再騰寫回來。 感覺很浪費記憶體啊。 如果我們有辦法就地移動資料本身，不仰賴大量額外的記憶體的話，這類型的演算法通常被稱為原地演算法（In-Place Algorithms）。 最嚴格的原地演算法定義，是規定只能使用常數2數量的記憶體空間（用來存放註標、或某些計數器等等資料）。

#### Class & Constructor Funtion

Class是在ES6之後才引進的語法，這題我們寫了ListNode這個class來建構物件範本，在構造函數中，建立了val和next這兩個屬性，以便繼承給之後的instance，**所以這題其實乍看之下list1,list2是陣列 但其實兩者都是ListNode的實例，這題的node,linked list在定義上其實都是物件**，**在物件的情況下也就要想到他傳參考的特性，由於物件在指派時是傳參考，所以在記憶體空間表現上會比較好，不會另開新的記憶體空間，也是我們能達成原地演算法的原因**

---

### 143. Reorder List (🎗️:Medium)

[題目連結](https://leetcode.com/problems/reorder-list/description/?source=submission-noac)

#### 題目分類:Linked List

結合第206題reverseList函數

CODE: with javascript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

//這是第206題的reverseList函數
const reverseList = (head) => {
    if (!head || !head.next) {
        return head;
    }
    const reversedNext = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    
    return reversedNext;
};

//firs是前半段,second是後半，我們以前半段為主，然後把後半段一個個加到前半
const mergeLists = (first, second) => {
    //用來記錄當前next node
    let next = null;



    //當second後半list不為null(還沒交換完成)就執行while
    while (second !== null) {
      //假設前半當前節點為A,下一個節點為B
      //假設後半當前節點為C,下一個節點為D
      //前半
      next = first.next;//先記錄 未交換前的前半next : 紀錄B
      first.next = second; //交換 前半&後半節點 : AC交換
      first = next;//更改當前的 前半 至下一個node : 目前的fisrt就是B

      //後半
      next = second.next; //先記錄 未交換前的後半next : 紀錄D
      second.next = first; //此時的first是B節點，C節點交換過去之後的next就是B
      second = next;//更改當前的 後半 至下一個node : 目前的second就是D
    }
};




var reorderList = function(head) {
  if (!head || !head.next) {
    return head; // 如果鏈表為空或只有一個節點，無需重新排列
  }

  //利用快慢指針方法找到linked list中點 & 終點(最後一個node)
  let fast = head;
  let slow = head;

  while(fast.next && fast.next.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  //此時slow是中點的node ， fast是最後一個node
  let firstHalf = head;
  let secondHalf = slow.next;
  slow.next = null; //要切掉前半段最後一個node(slow)的next

  //反轉後半段的linked list
  const reversedSecondHalf = reverseList(secondHalf);

  //merge前半跟反轉後的後半list
  mergeLists(firstHalf,reversedSecondHalf);

  return head;
};

#### 時間複雜度:
第一個輔助函數reverseList，時間複雜度是O(n)，第二個輔助函數mergeLists，主要是遍歷後半段second，假設題目input head的長度是n，則second長度可以簡單視為1/2n，故mergeLists時間複雜度是O((1/2)n)

reorderList由三個部分組成: 快慢指針+reverseList+mergeLists，快慢指針部分，假設head長度為n，時間複雜度為:O(n)，這三部分相加的時間複雜度是O(n)+O((1/2)n)+O(n)，則整體算法的big O notation為O(n)

Performance:

---

### 19. Remove Nth Node From End of List (🎗️:Medium)

[題目連結](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

#### 題目分類:Linked List

CODE: with javascript

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

var removeNthFromEnd = function(head, n) {

    
    const dummy = new ListNode(0);
    dummy.next = head;
    let fast = dummy;
    let slow = dummy;

    //先讓fast走n步
    for(i=0;i<=n;i++) {
        fast = fast.next;
    }

    //fast和slow一起走，最後fast會停在最後一個node
    while(fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }

    //而slow停的位置是在要被換掉的前一node，把它的next改成next.next
    slow.next = slow.next.next;

    return dummy.next;


};

#### 時間複雜度:
假設輸入的head長度為n，輸入的n改為m來表示，而m是一個常數，第一部分的時間複雜度為O(m)，但bigO值可記為O(1)，第二部分迴圈的時間複雜度為O(n)，
故整體算法時間複雜度為O(m+n)，bigO notation為O(n)

Performance:


---

### 138. Copy List with Random Pointer (🎗️:Medium)

[題目連結](https://leetcode.com/problems/copy-list-with-random-pointer/)

#### 題目分類:Linked List

CODE: with javascript

class Node {
    constructor(val,next=null,random=null) {
        this.val = val;
        this.next = next;
        this.random = random;
    }
}



var copyRandomList = function(head) {
    if(!head) {
        return null;
    }

    let current = head;
    //1.遍歷一遍head把原始的val作為val創建新的節點，然後在每個原始節點後都接上新的node
    //結果:  原node1 -> 新node1 -> 原node2 -> 新node2...

    while(current) {
        const newNode = new Node(current.val);
        newNode.next = current.next; 
        current.next = newNode;
        current = newNode.next;
    }

    //2.針對原始節點做遍歷 來調整新節點的random和next
    current = head;
    while (current) {
        //只有原始節點有random，所以把後者原始節點的next(由於第一個迴圈此時後者必定是新節點，也符合題意) 賦值 給 前者新節點的random
        if (current.random) {
            current.next.random = current.random.next; 
        }
        //跳到下一個原始節點
        current = current.next.next;
    }

    //3.斷開兩個鏈表(更改新舊節點的next)
    current = head;
    let newHead = head.next;//第一個新節點
    let newCurrent = newHead;
    while(current) {
        current.next = current.next.next;
        current = current.next;
        if(newCurrent.next) { //這邊檢查next屬性是因為括號內的等號左側涉及到next屬性，因此要提前檢查next屬性是否存在
            newCurrent.next = newCurrent.next.next;
            newCurrent = newCurrent.next;
        }
    }
    
    return newHead;
};

#### 時間複雜度:
假設head長度為n，則第一、第二、第三部份的時間複雜度皆為O(n)，整體時間複雜度是O(3n)，big O notation為O(n)

Performance:


---

### 2. Add Two Numbers (🎗️:Medium)

[題目連結](https://leetcode.com/problems/add-two-numbers/description/)

#### 題目分類:Linked List

CODE: with javascript

class ListNode {
    constructor(val,next=null) {
        this.val = val;
        this.next = next;
    }
}

var addTwoNumbers = function(l1, l2) {
    // 2->4->3
    // 5->6->4
    // 個位數相加 -> 十位數相加 -> 百位數相加...
    let dummyHead = new ListNode(0);
    let current = dummyHead;
    let carry = 0;//進位

    //遍歷，這邊有carry>0的條件是防止最後l1,l2都跑完但還有進位的情況，此時仍然要再正常跑一次迴圈內的操作，並新增一個node來解決這個進位
    while(l1 || l2 || carry > 0) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;

        carry = Math.floor(sum / 10); //取得sum除10的商，進位
        current.next = new ListNode(sum%10); //sum除10的餘數，留下

        //l1,l2++
        if(l1) l1=l1.next;
        if(l2) l2=l2.next;
        //current++
        current = current.next;
    }



    return dummyHead.next;
};

#### 時間複雜度:
假設l1長度為n，l2長度為m，迴圈部分的時間複雜度就是O(ceil(n,m))，bigO notation為O(n)

Performance:


---

### 141. Linked List Cycle (🎗️:Easy)

[題目連結](https://leetcode.com/problems/linked-list-cycle/description/)

#### 題目分類:Linked List

CODE: with javascript

class ListNode {
    constructor(val, next=null) {
        this.val = val;
        this.next = next;
    }
}


var hasCycle = function(head) {
    //假設list長度為n 則pos範圍: 0 <= pos <= n-2(不會指向自己)

    //遍歷整個list，

    //到了最後一個node檢查next屬性是否存在於hash table內

    let current = head;
    const visited = new Set();
    while(current) {
        //檢查最後一個節點
        if(visited.has(current)) {
            return true;
        }
        //如果沒有就把新節點加進去
        visited.add(current);

        current = current.next;

    }

    return false;
};

快慢指針法:題目不把pos做為參數，因此用快慢指針法只需考慮快指針和慢指針相遇的情況(return true)，這樣做可以節省空間複雜度，不用另開hash table

class ListNode {
    constructor(val, next=null) {
        this.val = val;
        this.next = next;
    }
}


var hasCycle = function(head) {
    if(!head || !head.next) {
        return false;
    }

    let slow = head;
    let fast = head.next;
    while(slow !== fast) {
        if (!fast || !fast.next) {
            return false;
        }

        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
};

#### 時間複雜度:
假設head長度是n，則只需要遍歷整個head就可以完成，時間複雜度是O(n)，bigO notation也是O(n)

Performance:

基本做法:

快慢指針法:

---

### 287. Find the Duplicate Number(🎗️:Medium)

[題目連結](https://leetcode.com/problems/find-the-duplicate-number/description/)

#### 題目分類:LinkedList

CODE: with javascript

var findDuplicate = function(nums) {
    let slow = nums[0];
    let fast = nums[0];
    
    //重點在於我們把節點的值設為nums[i]，並把nums[i]這個節點的next設為nums[nums[i]]，依照這個邏輯來走快慢指針，所以第一個迴圈最後會停在相遇點

    //找到快慢指針相遇點，並把快指針留下標記
    while(true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        if(slow === fast) {
            break;
        }
    }

    
    // 第二個慢指針從數組第一個數出發，快指針從相遇點出發，會在環的起始點相遇
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
};

#### 時間複雜度:
假設nums長度為n，則第一個迴圈和第二個迴圈時間複雜度皆為O(n)，而我們只使用了fast和slow兩個變數，且他們大小不被nums長度影響，空間複雜度只有O(1)

Performance:

---

### 23. Merge k Sorted Lists(🎗️:Hard)

[題目連結](https://leetcode.com/problems/merge-k-sorted-lists/description/)

#### 題目分類:LinkedList

CODE: with javascript

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

// 合併兩個排序的鏈表
function mergeTwoSortedList(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;

    //當l1,l2存在: 比val大小，小的成為current.next並迭代到下一個node
    while (l1 && l2) {
        if (l1.val < l2.val) {
            current.next = l1;//l1進入current
            l1 = l1.next;//l1迭代
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;//current迭代
    }

    //l1單獨存在，那就直接current.next = l1，因為l1本身就排好了，l2同理
    if (l1) {
        current.next = l1;
    }
    if (l2) {
        current.next = l2;
    }

    //最後回傳dummy.next
    return dummy.next;
}
//用來拆分linked list用，假設lists長度是k，第一次會從中間拆成left1 right1，第二次left1和right1又會各自拆成left2 right2...，
var mergeKLists = function(lists) {
    let k = lists.length;
    //當k=0，lists沒有任何linked list，但我們最後return的是dummy.next(節點)，所以應該以return null來表示沒有node存在的情況
    if (k === 0) {
        return null;
    } //當k=1，只有包含一個linked liist，此時已經拆分完成，回傳該linked list
    if (k === 1) {
        return lists[0];
    }

    let mid = Math.floor(k / 2);
    let left = lists.slice(0, mid);
    let right = lists.slice(mid);

    return mergeTwoSortedList(mergeKLists(left), mergeKLists(right));
};

#### 時間複雜度:
首先要看在括號內層的函數mergeKLists，假設lists內有k個list，則左半加右半要merge log以2為底的k次，需要O(logn)的時間複雜度，還要在乘上外層mergeTwoSortedList內的執行次數，假設lists內總共有n個節點，則需要O(n)的時間複雜度，所以整體算法時間複雜度是O(n*logn)

Performance:


---

### 25. Reverse Nodes in k-Group (🎗️:Hard)

[題目連結](https://leetcode.com/problems/reverse-nodes-in-k-group/)

#### 題目分類:LinkedList

CODE: with javascript

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

//stop = 是反轉鏈表的最後一個node的下一個node = 下一個反轉鏈表的 head
var reverseList = function(head, stop) {
    var prev = stop;//標記stop
    while (head !== stop) {
        var next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev; //回傳stop
} 


//分組 並回傳鏈表最後一個node
var getGroupEnd = function(head, k) {
    //停止條件 : head不存在 且 k=1 (因為行道樹問題 有k個節點代表要有k-1個間距)
    while (head && k > 1) {
        head = head.next;
        k--;
    }
    return head;
}

var reverseKGroup = function(head,k) {
    var dummy = new ListNode(0);
    dummy.next = head;
    var prevGroupTail = dummy;

    while(head) {
        var groupStart = head;
        var groupEnd = getGroupEnd(groupStart, k);

        if (!groupEnd) break;

        //由於要反轉到end，所以()內stop要設為 groupEnd.next，最後回傳stop做為prevGroupTail.next
        prevGroupTail.next = reverseList(groupStart, groupEnd.next);
        prevGroupTail = groupStart;
        head = prevGroupTail.next;
    }
    var newHead = dummy.next;
    return newHead;
}

#### 時間複雜度:
假設一共有n個節點，要被分成k個一組然後反轉，首先要反轉的次數是n/k次取高斯，然後在組內的反轉操作複雜度是k，因為鏈表長度是k要遍歷一遍，所以整體算法複雜度是O((n/k)*k) = O(n)，big O值為O(n)

Performance:

---

### 226. Invert Binary Tree (🎗️:Easy)

[題目連結](https://leetcode.com/problems/invert-binary-tree/)

#### 題目分類:Tree

CODE: with javascript

function invertTree(root) {
    if(!root) {
        return null;
    }

    const temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

#### 時間複雜度:

假設總共有n個節點，我們會對每個節點調用invertTree函數兩次，所以時間複雜度是O(2n)，big o notation為O(n)

Performance:


---

### 104. Maximum Depth of Binary Tree(🎗️:Easy)

[題目連結](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

#### 題目分類:Tree

CODE: with javascript

var maxDepth = function(root) {
    if(root === null) {
        return 0;
    }

    const rootLeft = maxDepth(root.left);
    const rootRight = maxDepth(root.right);

    return Math.max(rootLeft, rootRight) + 1;
};

#### 時間複雜度:

假設總共有n個節點，我們會對每個節點調用invertTree函數兩次，所以時間複雜度是O(2n)，big o notation為O(n)

Performance:

---

### 543. Diameter of Binary Tree(🎗️:Easy)

[題目連結](https://leetcode.com/problems/diameter-of-binary-tree/)

#### 題目分類:Tree

CODE: with javascript

//用dfs概念
var diameterOfBinaryTree = function(root) {
    let diameter = 0;

    function calculateDepth(node) {
        if (node === null) {
            return 0;
        }
        //遞迴到最深處
        const leftDepth = calculateDepth(node.left);
        const rightDepth = calculateDepth(node.right);

        //左右長度相加
        const temp = leftDepth + rightDepth;

        //對比紀錄
        diameter = Math.max(diameter, temp);

        //
        return 1 + Math.max(leftDepth, rightDepth);//加1是考慮自己跟母節點的距離
    }

    //一開始就會走到最深處然後慢慢往上推
    calculateDepth(root);

    return diameter;
};

#### 時間複雜度:
假設總共有n個節點，而我們會為每個節點執行calculateDepth，因為有左右子樹，所以會執行兩次，則時間複雜度為O(2n)，big o notation為O(n)

Performance:

---

### 110. Balanced Binary Tree (🎗️:Easy)

[題目連結](https://leetcode.com/problems/balanced-binary-tree/description/)

#### 題目分類:Tree

CODE: with javascript

var isBalanced = function(root) {
    //沒有子節點只有母節點 return 高度1 
    if(!root) return 1;

    let depthL = isBalanced(root.left);
    let depthR = isBalanced(root.right);
    
    if(depthL === false || depthR === false) return false;

    //主要檢查是這行 只要左右高度差大於1，就回傳哪一邊的長度是false
    if((Math.abs(depthL - depthR)) > 1) return false;
    
    //往上移動一層
    return Math.max(depthL, depthR) + 1;
};

#### 時間複雜度:

假設總共有n個節點，而我們會對每個節點執行isBalanced兩次，因為有左右子樹，所以時間複雜度是O(2n)，big o notation是O(n)

Performance:


---

### 100. Same Tree (🎗️:Easy)

[題目連結](https://leetcode.com/problems/same-tree/description/)

#### 題目分類:Tree

CODE: with javascript

class TreeNode {
    constructor(val= 0 , left=null , right=null) {
        this.val = val
        this.left = left;
        this.right = right;
    }
}

var isSameTree = function(p, q) {
    
    //兩個都是null
    if(!p && !q) {
        return true;
    }
    //其中一個是null
    if(!p || !q) {
        return false;
    }
    //如果值不相等
    if(p.val !== q.val) {
        return false;
    }

    //遞迴
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

};

#### 時間複雜度:
假設p,q加起來總共有n個節點，而我們會對每個節點執行isSameTree，裡面會進行三次比較然後在迭代，因此時間複雜度是O(3n)，big o notation是O(n)

Performance:


---

### 102. Binary Tree Level Order Traversal (🎗️:Medium)

[題目連結](https://leetcode.com/problems/binary-tree-level-order-traversal/description/)

#### 題目分類:Tree

CODE: with javascript

var levelOrder = function(root) {
    //因為root有可能是空陣列，所以要再檢查root.length === 0，然後回傳[]
    if(!root || root.length === 0) {
        return [];
    } 

    const queue = [];
    const result = [];
    queue.push(root);

    //用bft
    while(queue.length>0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for(let i = 0; i<levelSize;i++) {
            const node = queue.shift();

            currentLevel.push(node.val);

            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        result.push(currentLevel);
    }

    return result;
};

#### 時間複雜度:
我們使用了廣度優先演算法，假設整個tree有n個節點，則時間複雜度為O(n)

Performance:


---

### 199. Binary Tree Right Side View (🎗️:Medium)

[題目連結](https://leetcode.com/problems/binary-tree-right-side-view/description/)

#### 題目分類:Tree

CODE: with javascript

var rightSideView = function(root) {
    if(!root || root.legnth === 0) {
        return [];
    }

    const queue = [];
    const result = [];

    queue.push(root);
    
    //因為要針對每一層檢查，所以用bft
    while(queue.length>0) {
        const levelSize = queue.length;
        let rightMost = null

        for(let i = 0;i<levelSize;i++) {
            const node = queue.shift();

            rightMost = node.val;
            
            //下面兩個if函式的順序很重要，一定是要right在後面，要保證左邊先於右邊，這樣rightMost才會取到每一層的最右邊node.val
            if(node.left) {
                queue.push(node.left);
            }
            if(node.right) {
                queue.push(node.right);
            }
        }
        result.push(rightMost);

    }
    return result;
};

#### 時間複雜度:
我們這題用的是BFT演算法，假設這個Tree有n個節點，則時間複雜度為O(n)

Performance:


---

### 1448. Count Good Nodes in Binary Tree(🎗️:Medium)

[題目連結](https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/)

#### 題目分類:Tree

CODE: with javascript

var goodNodes = function(root) {
    if(!root) return;
    let count = 0;

    //用dfs
    const findMax = function(node,maxValue) {
        if(!node) return;
        let current = node.val;

        if(current >= maxValue) {
            maxValue = current;
            count++;
        }

        findMax(node.left,maxValue);
        findMax(node.right,maxValue);
    };

    findMax(root,root.val);

    return count;
};

#### 時間複雜度:
因為我們用的是DFT，且已知為Binary Tree，對左右子樹值的大小沒有嚴格條件，假設整棵樹總共有N個節點，則時間複雜度為O(n)

Performance:


---

### 98. Validate Binary Search Tree (🎗️:Medium)

[題目連結](https://leetcode.com/problems/validate-binary-search-tree/description/)

#### 題目分類:Tree

CODE: with javascript

var isValidBST = function(root) {

    //要紀錄每個node個別的合理區間在哪 所以用min,max
    function isBST(node,min,max) {
        //全部跑完(跑到最深處)回傳true
        if(!node) {
            return true;
        }

        //不符合條件回傳false
        if(node.val <= min || node.val >= max) {
            return false;
        }
        //如果有效就再對左右子樹同時執行isBST，左子樹的最大值就是上一個節點，柚子樹的最小值也是上一個節點，遞迴
        return isBST(node.left,min,node.val) && isBST(node.right,node.val,max)
    }

    //從root開始遞迴完整棵樹，把isBST結果回傳
    return isBST(root, -Infinity,Infinity);
};

#### 時間複雜度:
對於一個Binary Search Tree，要討論時間複雜度時要考慮它是否平衡，通常平衡的情況是指左右子樹高度差不超過1，這種情況下的時間複雜度是O(logn)，而如果是不平衡的情況下，最壞的情況時間複雜度為O(n)，則big O notation為O(n)

Performance:


---

### 230. Kth Smallest Element in a BST (🎗️:Medium)

[題目連結](https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/)

#### 題目分類:Tree

CODE: with javascript

var kthSmallest = function(root, k) {
    //要把node從最小排到最大: 再整個tree中，由最左邊節點走到最右邊
    //可以把bst視為一個排序好的資料結構，由左至右就是由小到大
    let count = 0;
    let result = null;

    //我們用inOrder因為是要從最小開始算第k個
    //利用 左子節點 <　根節點　＜　右子節點　這個特性就能按照順序由小到大遍歷
    //1.先跑左子節點,count++ 2.再跑根節點 count++ 3.再跑右節點 count++ 
    function traversalK(node) {
        if(!node) return;

        traversalK(node.left);

        //計數
        count++;
        if(count===k) {
            result = node.val;
            return;
        }

        traversalK(node.right);
    }

    traversalK(root);
    return result;
};

#### 時間複雜度:
這題我們使用的是深度優先演算法裡的InOrder，假設n為Tree中所有節點的數量，假設k非常接近n，則意味著我們要由左子樹至右子樹遍歷大部分的節點才能找到第k小的節點，最壞情況n=k時，則時間複雜度會是O(n)，最好情況是k=1，我們只需要走到Tree內最左側的節點即可，此時時間複雜度為O(logn)，當然BST問題也要考慮樹的平衡性，就算左子樹高度遠大於右子數(極不平衡)，但k=1，那也只需遍歷logn個節點而已，所以這題時間複雜度在O(logn)~O(n)之間，big o notation為O(log n)

Performance:


---

### 105. Construct Binary Tree from Preorder and Inorder Traversal (🎗️:Medium)

[題目連結](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/)

#### 題目分類:Tree

附圖1: 遞迴中slice的左右子樹範圍

CODE: with javascript

var buildTree = function(preorder, inorder) {
    if(preorder.length===0 || inorder.length===0) {
        return null;
    }

    //pre的第一個值樹就是整棵樹的根節點
    let rootVal = preorder[0];
    //把他設定為root節點
    let rootNode = new TreeNode(rootVal);
    //在in找到root節點的index
    let rootIndex = inorder.indexOf(rootVal);

    //對於左節點部分，我們照著buildTree的形式，以當前根節點為中心，對pre和in兩個array切成左右子樹，範圍參考附圖1

    rootNode.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex));
    rootNode.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1));

    return rootNode;

};

#### 時間複雜度:

參考上方附圖，可以知道buildTree的執行次數和樹的左右子樹是否平衡有關，假設只有左子樹，那就代表前序數列必定是要一個節點一個節點來遍歷的，因此worse case的時間複雜度是O(n)，而best case則如同附圖，pre order的第一個節點在in order的中間，左右子樹是非常平衡的(左右半邊的節點數量差不多)，因此best case的時間複雜度為O(logn)，所以這題時間複雜度在O(logn)~O(n)之間，big o notation為O(logn)

Performance:


---

### 155. Min Stack (🎗️:Medium)

[題目連結](https://leetcode.com/problems/min-stack/submissions/)

#### 題目分類:Stack 先進後出 stack就是那個餅乾筒的感覺

CODE: with javascript

class MinStack {
    constructor(val) {
        //建立兩個棧堆，minStack是專門用來最小值的棧堆
        this.stack = [];
        this.minStack = [];
    }
    
    //push方法，先把val推進去stack，然後檢查在minStack是否也需要把val也推進去，如果minStack沒有東西或是當前的val比minStack的棧頂元素還小，那就要更新minStack棧頂(最小值)
    push(val) {
        this.stack.push(val);
        
        if(!this.minStack.length || val <= this.minStack[this.minStack.length-1]) {
            this.minStack.push(val);
        }
    }
    
    //pop方法，如果stack內沒東西就回傳null(題目要求)，如果val和minStack棧頂元素相等，則兩個都需要被pop()，因為最小值被誼除了所以兩個都要同步移除，正常就pop出stack的棧頂元素
    pop() {
        if(this.stack.length === 0) return;

        if(this.stack[this.stack.length-1] === this.minStack[this.minStack.length-1]) {
            this.minStack.pop();
        }

        this.stack.pop();
    }

    //只有回傳不改變stack，針對stack做判斷即可
    top() {
        if(this.stack.length===0) return null;
        return this.stack[this.stack.length-1];
    }


    //由於push跟pop方法已經確保minStack的棧頂永遠是stack內的最小值，所以直接判斷+回傳即可
    getMin() {
        if(this.minStack.length===0) return null;
        return this.minStack[this.minStack.length-1];
    }

}

#### 時間複雜度:
對於push方法，時間複雜度為O(1)，對於pop方法，時間複雜度為O(1)，對於top方法，時間複雜度為O(1)，對於getMin方法，時間複雜度為O(1)

Performance:


---

### 22. Generate Parentheses (🎗️:Medium) Backtracking 需複習!

[題目連結](https://leetcode.com/problems/generate-parentheses/description/)

#### 題目分類:Stack/Backtracking

決策樹如下


遞歸過程如下，紅色是執行，藍色是回朔


CODE: with javascript

var generateParenthesis = function(n) {
    let result = [];
    let stack = [];
    //open,close是指當前"("和")"的個數
    function backtrack(open, close) {
        // 如果stack長度是2n則滿足長度回傳
        if (stack.length === n * 2) {
            result.push(stack.join(''));
            return;
        }

        //由於open的最大值是n所以讓他open<n就執行，
        //當open=n時就會執行下面的第二個if
        if (open < n) {
            stack.push('(');
            backtrack(open + 1, close);
            stack.pop(); // 回溯，移除最后一个元素
        }

        //停止條件是close=open，此時就會開始回朔，不斷pop")"
        if (close < open) {
            stack.push(')');
            backtrack(open, close + 1);
            stack.pop(); // 回溯，移除最后一个元素
        }
    }

    // 初始化
    backtrack(0, 0);

    return result;
};

#### 時間複雜度:
這個演算法的時間複雜度取決於產生的括號組合數量，它與卡特蘭數有關。 卡特蘭數的計算複雜度是 O(4^n / n^(3/2))，因此產生有效的括號組合的時間複雜度也是 O(4^n / n^(3/2))。

Performance:


---

### 739. Daily Temperatures (🎗️:Medium)

[題目連結](https://leetcode.com/problems/daily-temperatures/submissions/)

#### 題目分類:Stack

解題概念:

CODE: with javascript

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = [];//此為單調遞減Stack，用來儲存當前溫度index
    
    for(let currentDay = 0; currentDay<n; currentDay++) {
        const currentTemperature = temperatures[currentDay];

        //stack是用來記錄 上一個溫度至下一個更高溫的index經過過程
        //當只要stack裡面還有東西，代表前面還有某些天的result還沒確定
        //這時就會把stack內的top拿出來和當前溫度比較
        while(stack.length>0) {
            const preDay = stack.pop();//preDay前項溫度的index，把他取出來做比較
            const preDayTemperature = temperatures[preDay];//前項溫

            //如果當前溫度大於前項，則可以確定目前前項的dayWait
            if(currentTemperature > preDayTemperature) {
                const dayWait = currentDay - preDay;
                result[preDay] = dayWait;//更新至result
            } else { 
                //如果當前溫度等於或小於前項，則放回去
                stack.push(preDay)
                break;
            }
        }
        //如果stack內沒有東西則push
        stack.push(currentDay);

    }
    

   return result;
};

#### 時間複雜度:
假設temperature長度為n，for迴圈的時間複雜度是O(n)，但內層的while迴圈性質類似於if，只有當遲遲找不到更高溫時才會執行比較多次，而判斷條件的stack跟輸入的temperatures並沒有直接關係，因此整體算法複雜度為O(n)

Performance:


---

### 853. Car Fleet (🎗️:Medium)

[題目連結](https://leetcode.com/problems/car-fleet/description/)

#### 題目分類:Stack?

CODE: with javascript

var carFleet = function(target, position, speed) {
    const cars = [];
    
    //先建立一個 位置 和 到終點需要多少時間的array
    for (let i = 0; i < position.length; i++) {
        const timeToTarget = (target - position[i]) / speed[i];
        cars.push({ position: position[i], timeToTarget });
    }

    // 依離終點的距離由小排到大 (離終點近 ~ 離終點遠)
    cars.sort((a, b) => b.position - a.position);

    let fleets = 0;
    let prevTimeToTarget = 0;//初始化前車速度，讓第一台車形成車隊

    //cars順序是由終點到起點，所以如果現在這台車的timeToTarget大於上一台(跑在他前面的那台車)，這台車追不上跑在他前面的那台車，那就會自己一個車隊 fleets++，如果追得上的話那車隊數量就不會增加
    for (let i = 0; i < cars.length; i++) {
        if (cars[i].timeToTarget > prevTimeToTarget) {
            fleets++;
            prevTimeToTarget = cars[i].timeToTarget;
        }
    }

    return fleets;
};

#### 時間複雜度:
假設有n台車，時間複雜度為O(2n)，big o notation為O(n)

Performance:


---

### 84. Largest Rectangle in Histogram(🎗️:Hard)

[題目連結](https://leetcode.com/problems/largest-rectangle-in-histogram/)

#### 題目分類:Stack

#### 暴力解(時間複雜度O(n^2)，空間複雜度O(1)

#### 正規解法:單調遞增Stack

解題概念:

CODE: with javascript

function largestRectangleArea(heights) {
    const stack = []; //建立一個單調遞增棧
    let maxArea = 0; // 紀錄最大長方形面積

    // 遍歷每個柱子
    for (let i = 0; i < heights.length; i++) {
        // 棧不為空是確保前面有柱子比當前柱子矮或是等於，這樣才能形成長方形
        // 第二個條件是如果後項柱子低於前項柱子則前項柱子高度的長方形面積可以確定，而且會一直往前迭代到有前項柱子的高度等於或低於當前柱子高度為止(這樣才能封閉一個長方形面積)
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            const height = heights[stack.pop()]; //彈出棧頂高度
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; // 計算寬度
            maxArea = Math.max(maxArea, height * width);//更新最大面積
        }
        stack.push(i); //不管如何都會push新的柱子index進去(因為我們本來就是要逐一檢查)
    }

    // 處理剩餘的柱子，這個情況代表剩下的柱子肯定是最矮的，因為如果前面還有柱子高於後面的柱子，那前面柱子高度的長方形就可以成立，反之前面的柱子是最矮的(沒有柱子比他矮的話)，那他自己高度的長方形就沒辦法建立，就會剩下最矮的柱子
    while (stack.length > 0) {
        const height = heights[stack.pop()]; //彈出棧頂高度
        //而最矮的柱子也有可能有很多個，所以在最後的寬度條件，當我們知道stack為空，也就是最後一個柱子時，我們直接把長度設成heights的長度，以得到最低高度的最大長方形
        const width = stack.length === 0 ? heights.length : heights.length - stack[stack.length - 1] - 1;
        maxArea = Math.max(maxArea, height * width); //更新最大面積
    }

    return maxArea; 
}

#### 時間複雜度:
假設一共有n個柱子我們只需要遍歷一次heights，則時間複雜度為O(n)，但空間複雜度為O(n)，因為我們要建立一個stack來記錄每個柱子的index

Performance:


---

### 981. Time Based Key-Value Store (🎗️:Medium)

[題目連結](https://leetcode.com/problems/time-based-key-value-store/submissions/)

#### 題目分類:binary search

CODE: with javascript

class TimeMap {
    constructor() {
        this.map = {};
    }


    set(key, value , timestamp) {
        //初始化bucket這個陣列，裡面會push一個value對timestamp的物件
        const bucket = this.map[key] || [];//如果找不到對應的key就是空陣列
        this.map[key] = bucket;
        bucket.push([value, timestamp]);//push新資料進去
    }
    /**
        this.map = {
            "key1" : [["value1", 10] , ["value2", 12]],
            "key2" : [["value3", 8] , ["value4", 5]],
        }
     */ 

    get(key, timestamp) {
        //找到相對應key的陣列
        let bucket = this.map[key];
        //找不到直接回傳"""
        if(!bucket) {
            return "";
        }
        //對這個陣列用binary search，題目已經說All the timestamps timestamp of set are strictly increasing.，所以可用
        let [left, right] = [0, bucket.length - 1];
        //如果完全找不到比garget大的stamp還是要回傳"""
        let result = "";


        while(left <= right) {
            const mid = Math.floor((left+right)/2);
            const [guessValue, guessTimeStamp] = bucket[mid];
            if(guessTimeStamp <= timestamp) {
                result = guessValue;
                left = mid+1;
            } else {
                right = mid-1;
            }
            
        }

        return result;
    }
}

#### 時間複雜度:

set方法的時間複雜度為O(1)，因為只需要查找並push(在JavaScript中，物件（Object）和字典（Dictionary）使用哈希表來實現鍵值對的存儲，因此查找特定鍵對應的值的時間複雜度通常是O(1))

get方法的時間複雜度為O(logn)，因為題目已經說過input中的timestamp會依照嚴格遞增的順序來做set，可以視為this.map[key]陣列內的stamp都是由小到大排序好的，則對陣列使用binary search的時間複雜度為O(logn)

Performance:


---

### 146. LRU Cache (🎗️:Medium)

[題目連結](https://leetcode.com/problems/lru-cache/description/)

[LRU是?](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)

#### 題目分類:

CODE: with javascript

class ListNode {
    constructor(key,value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.head = new ListNode();
        this.tail = new ListNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    //移動到鏈表頭部，用來把最多使用的資料拉到最前面
    moveToHead(node) {
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }

    //刪除節點
    removeNode(node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
    }

    get(key) {
      if(this.cache.has(key)) {
        const node = this.cache.get(key);
        //因為最近訪問了這個節點，要把它移到最前面
        this.removeNode(node);
        this.moveToHead(node);
        return node.value;
      }
      return -1;
    }


    // cache = { {1 : 1} , {2 : 2}}
    put(key, value) {
      //如果該key已經存在就只需要修改value，當然也要更新到最前面
      if(this.cache.has(key)) {
        const node = this.cache.get(key);
        node.value = value;
        this.removeNode(node);
        this.moveToHead(node);
      } else {
          //如果已經達到capacity，就要移除尾部的節點(最久沒使用)
          if(this.cache.size >= this.capacity) {
            const tailNode = this.tail.prev;
            this.removeNode(tailNode);
            this.cache.delete(tailNode.key)
          }
          //如果還沒滿就正常set新節點
          const newNode = new ListNode(key,value);
          this.cache.set(key, newNode);
          this.moveToHead(newNode);
      }
    }
}

#### 時間複雜度:

這題我們用雙向鏈表來儲存節點，我們用map來實例化cache，因為map可以執行set,get,delete,has等方法，方便我們查詢跟修改，在moveToHead，時間複雜度是O(1)，我們只需要把當前節點移動到虛擬頭部的next，在removeNode，時間複雜度是O(1)，我們只需要把該節點的前節點next和後節點prev做調整即可，在get方法中，我們用map的has方法來查詢，所以時間複雜度是O(1)，在put方法中我們也是先用has來查詢然後再使用removeNode,delete,set,moveToHead等操作，這些在map中時間複雜度都是O(1)

Performance:


---

### 124. Binary Tree Maximum Path Sum (🎗️: Hard)

[題目連結](https://leetcode.com/problems/binary-tree-maximum-path-sum/description/)

#### 題目分類:Tree

CODE: with javascript (post order)

var maxPathSum = function(root) {
    let max = -Infinity;

    
    //用post order算法 先處理左右後處理根節點並往上回傳

    const findSum = (node) => {
      //如果節點不存在，或是是最下方的節點
      if(!node) return 0;

      //left代表當前節點往左子樹遍歷完的最大值
      let left = findSum(node.left);
      //right代表當前節點往右子樹遍歷完的最大值
      let right = findSum(node.right);
      //allSum 就是當前節點+left+right，這有可能是答案，但不能回傳給當前節點的根節點，因為如果要左邊又要右邊那就代表path會是左子樹->root->右子樹，這時候不能再往上走了
      let allSum = left + right + node.val;
      //left+當前節點值 ， 這個可以往上回傳
      let leftSum = left + node.val;
      //right+當前節點值 ， 這個也可以往上回傳
      let rightSum = right + node.val;

      //比較這五種候選人的大小
      max = Math.max(max, node.val, allSum,leftSum,rightSum);
      //但只能回傳 左路徑or右路徑or當前節點 給上一層
      return Math.max(leftSum,rightSum, node.val);
    }

    findSum(root);

    return max;
};

#### 時間複雜度:
我們使用的是深度優先演算法的Post Order，假設這個Tree有n個節點，且為平衡二叉樹，則時間複雜度為O(logn)，若是這個樹有n個節點且高度為n-1(只有單邊)，則時間複雜度為O(n)

Performance:


---

### 297. Serialize and Deserialize Binary Tree (🎗️:Hard)

[題目連結](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/)

#### 題目分類:Tree

CODE: with javascript (和範例一樣使用廣度優先)

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

//我們使用廣度優先演算法來建立 序列化字串
function serialize(root) {
    if(!root) return "null";
    
    //為最後要轉換的字串陣列，用array的方式比較好記錄，最後再把它轉成str即可
    const result = [];
    //遍歷用
    const queue = [];

    queue.push(root);

    while(queue.length > 0) {
        const node = queue.shift();
        if(node) {
            result.push(node.val.toString());
            queue.push(node.left);
            queue.push(node.right);
        } else {
            result.push("null");
        }

    }

    return result.join(",");
}

//反序列化
function deserialize(seriString) {
    const values = seriString.split(",");
    if(values[0] === "null") return null;

    //為字串符第一項(樹的根節點)的值建立一個新節點
    const root = new TreeNode(parseInt(values[0]));
    //一樣使用bfs來建立樹
    const queue = [root];
    let i = 1;

    //初始化i=1，所以還有n-1個節點要跑，結束條件為1+n-1，values長度剛好是n，故如下
    while(i < values.length) {
        const node = queue.shift();

        //建立左右子節點如下
        //1.先找出在values字串中對應的值 2.檢查是否為null(如果是null代表沒有結點) 3.如果不為空則用該值建立新的節點，並推入queue

        let leftVal = values[i++];
        if(leftVal !== "null") {
            let newLeftNode = new TreeNode(parseInt(leftVal));
            node.left = newLeftNode;
            queue.push(newLeftNode);
        }

        let rightVal = values[i++];
        if(rightVal !== "null") {
            let newRightNode = new TreeNode(parseInt(rightVal));
            node.right = newRightNode;
            queue.push(newRightNode);
        }

    }


    return root;
}

#### 時間複雜度:

我們使用的是廣度優先演算法，也就是從原點開始依序往左節點跟右節點一直遍歷下去，假設Tree總共有n個節點，則serialize和deserialize的時間複雜度為O(n)

Performance:


---

### 219. Contains Duplicate II (🎗️: Easy)

[題目連結](https://leetcode.com/problems/contains-duplicate-ii/description/)

#### 題目分類:Arrays & Hashing

CODE: with javascript

var containsNearbyDuplicate = function(nums, k) {
    let map = new Map();


    for (let i = 0; i < nums.length; i++) {
        //如果已經存在nums[i]，就比較條件
        //因為i-j是要越小越好 所以最好更新到map.get(nums[i]這個array的最後兩個值就可以了 也就是比較 當前i 跟 之前已經存在最後一個的index
        if (map.has(nums[i]) && (i - map.get(nums[i]) <= k)) {
            return true;
        }
        map.set(nums[i], i);
    }

    return false;
};

#### 時間複雜度:
只有遍歷nums這個array，並建立對應的map(hash table)，所以時間複雜度為O(n)，空間複雜度為O(n)

Performance:


---

### 220. Contains Duplicate III (🎗️:Hard) 桶排序 需複習!!

[題目連結](https://leetcode.com/problems/contains-duplicate-iii/description/)

#### 題目分類:Arrays & Hashing/Bucket Sort

CODE: with javascript

var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {

    if(!nums|| indexDiff <=0 || valueDiff < 0) {
        return false;
    }

    const window = new Map();

    for (let i = 0 ; i<nums.length ; i++) {
        const num = nums[i];
        
        //以valueDiff+1為區間來對每個數分配相對應的桶子
        const bucket = Math.floor( num/(valueDiff+1));

        //如果當前窗口或相鄰窗口有元素存在，檢查相鄰的元素是否符合條件，返回true
        if(window.has(bucket) || (window.has(bucket-1) && num - window.get(bucket-1) <= valueDiff) || (window.has(bucket+1) && window.get(bucket+1) - num <= valueDiff)) {
            return true
        }

        // 如果窗口大於等於indexDiff這個區間，那就移除最舊的元素
        if (i >= indexDiff) {
            //nums[i - indexDiff]是最舊的元素，我們要找到他對應的桶子刪除掉(同時也刪除掉這個元素了)
            window.delete(Math.floor(nums[i - indexDiff] / (valueDiff + 1)));
        }

        //建立相對應的桶子放入值 key-value是 => "bucket" : num
        window.set(bucket, num);
    }

    return false;
};

#### 時間複雜度:

對整個陣列進行了一次線性遍歷，因此時間複雜度是 O(n)，其中 n 是陣列的長度。
在遍歷過程中，你對每個元素進行了桶的計算、桶的檢查、桶的新增和刪除操作。 這些操作的時間複雜度都可以看作是常數等級的，因為桶的數量通常是有限的，與陣列大小無關。
因此，整體來說，演算法的時間複雜度是 O(n)

Performance:


---

### 18. 4Sum(🎗️:Medium)

[題目連結](https://leetcode.com/problems/4sum/submissions/)

#### 題目分類:Arrays & Hashing

CODE: with javascript

var fourSum = function(nums, target) {
    //先對數組sort，由小到大
    nums.sort((a,b) => a-b);
    const result = [];
    
    let L = nums.length;
    //雙套迴圈來固定兩個數，對於這兩個數如果有連續(一樣)就要跳過，另外兩個數用左右指針，然後判斷4sum來找
    //因為i走到最後要留三個空位，所以是 L-3，j走到最後要留兩個空位，所以L-2
    for(let i=0; i < L-3 ;i++) {
        for(let j=i+1; j < L-2;j++) {
            let left = j+1;
            let right = L-1;

            //雙指針
            while(left < right) {
                const sum = nums[i]+nums[j]+nums[left]+nums[right];
                if(sum===target) {
                    //找到答案push
                    result.push([nums[i],nums[j],nums[left],nums[right]]);
                    //檢查左右指針是否有連號，有就跳過
                    //記得要用while，因為連號可能有好幾個，所以要直到不連耗材繼續
                    while(nums[left] === nums[left+1]) left++;
                    while(nums[right] === nums[right-1]) right--;

                    //左右都符合那就往中間縮
                    left++;
                    right--;
                } else if(sum<target) {
                    //當sum<target代表左邊指針的值太小了要往右邊走一格
                    left++
                } else {
                    //當sum>target，代表右邊太大，要減一格
                    right--;
                }
            }
            
            while(nums[j] === nums[j + 1]) j++;
        }
        while(nums[i] === nums[i + 1]) i++;
    }


    return result;
};

#### 時間複雜度:
外面兩個迴圈，加上內層的雙指針，所以整體時間複雜度是O(n^3)

Performance:


---

### 438. Find All Anagrams in a String (🎗️:Medium)

[題目連結](https://leetcode.com/problems/find-all-anagrams-in-a-string/description/)

#### 題目分類:Arrays & Hashing

CODE: with javascript

//檢查兩個map是否相等
function sameMaps(m1,m2) {
    if(m1.size !== m2.size) {
        return false;
    }

    for(let [key, value] of m1) {
        if(value !== m2.get(key)) {
            return false;
        }
    }
    return true;
}



var findAnagrams = function(s, p) {

    //建立一個p的map來存放 字母:出現次數
    let map = new Map();

    let splitP = p.split('');
    for(let i=0;i<p.length;i++) {
        if(map.has(splitP[i])) {
            map.set(splitP[i], map.get(splitP[i])+1);
        } else {
            map.set(splitP[i], 1);
        }
    }

    //遍歷S，p長度的sliding window，然後去檢查map內的出現次數是否符合
    let left = 0;
    let splitS = s.split('');
    const windowMap = new Map();

    //output
    let result = [];

    for(let right =0; right<splitS.length; right++) {
        const charRight = splitS[right];

        //建立一個窗口內的map
        windowMap.set(charRight,  (windowMap.get(charRight)||0)+1);

        //如果窗口大小超過p長度，那左邊界右移，同時移除在windowMap內相對應的key-value
        if(right-left+1 > p.length) {
            const windowLeft = splitS[left];
            //修改map
            windowMap.set( windowLeft, windowMap.get(windowLeft)-1);
            if(windowMap.get(windowLeft) === 0) {
                windowMap.delete(windowLeft);
            }
            left++;
        }
        
        if(right-left+1 === p.length && sameMaps(map,windowMap)) {
            //因為要回傳anagram的開頭所以是回傳left
            result.push(left);
        }
    }    

    return result;

};

#### 時間複雜度:
假設s長度為m，p長度為n，在第一個遍歷p的迴圈中，時間複雜度是O(n)，在第二個sliding window的迴圈中，時間複雜度為O(m)，所以整體算法的時間複雜度為O(m+n)，取決於輸入的s,p的長度大小，而空間複雜度亦是O(m+n)

Performance:


---

### 152. Maximum Product Subarray(🎗️:Medium)

[題目連結](https://leetcode.com/problems/maximum-product-subarray/description/)

#### 題目分類: 1-D Dynamic Programming

CODE: with javascript

var maxProduct = function(nums) {
    let prevMax = nums[0];
    let prevMin = nums[0];
    let result = nums[0];

    for(let i=1;i<nums.length;i++) {
        //你可以想像subArray有兩種 ，一種是正整數連續，一種是負整數連續，我們只要追蹤這兩個可能即可

        //遍歷一個數有三種情況有最大值
        //1.當前的數乘上 最大值紀錄 2.當前的數乘上 最小值紀錄(可能負負得正) 3.自己就是最大值

        currentMax = Math.max(nums[i] * prevMax, nums[i], nums[i]*prevMin);
        currentMin = Math.min(nums[i] * prevMax, nums[i], nums[i]*prevMin);

        //設定max,min紀錄
        prevMax = currentMax;
        prevMin = currentMin;

        result = Math.max(currentMax, result);
    }


    return result;
};

#### 時間複雜度:
因為只要遍歷nums而已，假設nums長度為n，則這題的時間複雜度為O(n)

Performance:


---

### 81. Search in Rotated Sorted Array II(🎗️:Medium)

[題目連結](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/)

#### 題目分類:binary search

CODE: with javascript

//因為這題的nums有可能有很多重複元素，所以先找到旋轉點的方法不太適用(index會亂掉)，就算找到旋轉點也無法確定target在哪一半邊

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;


    while (left <= right) {
        const middle = Math.floor((left + right) / 2);

        if (nums[middle] === target) {
            return true;
        }

        // 如果左半邊是遞增
        if (nums[left] < nums[middle]) {
            if (nums[left] <= target && target < nums[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        // 如果右半邊是遞增(旋轉點在左半邊)
        else if (nums[left] > nums[middle]) {
            if (nums[middle] < target && target <= nums[right]) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        // left和middle是重複元素，無法確定遞增遞減，就縮減left範圍
        else {
            left++;
        }
    }

    return false;
};

#### 時間複雜度:

假設nums長度是n，我們使用二分法來找target，則時間複雜度為O(logn)

Performance:


---

### 5. Longest Palindromic Substring (🎗️:Medium)

[題目連結](https://leetcode.com/problems/longest-palindromic-substring/)

#### 題目分類:Dynamic programming

CODE: with javascript

var longestPalindrome = function(s) {
    let n = s.length;
    let dp = new Array(n).fill(null).map(() => new Array(n).fill(false));
    
    let start = 0;
    let maxLength = 1;

    //針對每個字符都是自己的回文
    for(let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    //檢查每個長度為2的字串是不是回文，如果是就往外推: i-1 j+1
    for(let len = 2; len <= n ; len++) { //len: 代表的是回文長度 範圍: 2~n
        for(let i=0; i < n - len + 1; i++) { //i的max是n-1 ， 因為 i最大是n-1要等於n-2 + x ，所以這個x是+1
            const j = i + len -1;//j從1開始
            if(s[i] === s[j] && (len === 2 || dp[i+1][j-1])) { //檢查回文長度等於2 和 2以上
            //假設這邊迴圈走到 i=0,j=2(回文長度=3) 其實要檢查dp[2][0]是否回文(ij要反過來)，這樣才能確定dp[0][2]是回文的， 而如果長度剛好是2就直接確定回文
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }

    return s.substring(start, start + maxLength)


};

#### 時間複雜度:

假設s長度是n，外圈迴圈要跑n-1次，內圈迴圈要跑n-len+1，時間複雜度就是O(n^2)

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---

### 第幾題 (🎗️:Medium)

[題目連結]()

#### 題目分類:

CODE: with javascript

#### 時間複雜度:

Performance:

---