30-Day LeetCode Challenge, 第二週挑戰！！

總結兩個本週技巧，

1.Linked List
2.Recusion

兩個技巧的詳細介紹可參考
Matters-野生的工程師

題目

1.Middle of the Linked List

說明：找出Linked List 的中間節點,抓出中間節點以後的Linked List

Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

思維：
算出Linked List 長度 然後 /2 +1 ，＋1是因為題目有說如果是雙數的話就找第二個，
所以我用Math.floor 找最大整數 在 ＋１

Answer：

var middleNode = function(head) {
    let listLength = 1 
    let a = 0
    let test = head
    
    while(test.next){
        test = test.next
        listLength += 1
    }
    
    let mid = Math.floor(listLength / 2) + 1
    let answer = head
    
    while(mid > 0 && head){
        answer = head
        head = head.next
        mid--
    }
    
    return answer
};

2.Backspace String Compare

說明：遇到 # 就刪除前一個字

Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

思維：
我以為是要用Linked List 去處理，因為想說每週的題目應該會有相似的應用，
但其實就只是沒事就 push 遇到就pop 的觀念而已

Answer ：

const delStr = str =>{
   
    let arr =(str).split("")
    let del = []
    for(let i = 0 ; i < arr.length ; i++){
        if(arr[i] !== "#"){
            del.push(arr[i])
        }else{
            del.pop()
        }
    }
    return del.join("")
}
var backspaceCompare = function(S, T) {
    let del_s = delStr(S)
    let del_t = delStr(T)
    return del_s == del_t 
};

3.Diameter of Binary Tree

說明：設計一個function

Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

思維：
這題很簡單但很難意會是怎麼input ouput，可能從程式碼看比較清楚，
這題可以了解一下原形鍊的觀念，然後照需求return 每個function的結果

Answer：

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []
};
/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    return this.stack.push(x)
};
/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    return this.stack.pop()
};
/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};
/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return Math.min(...this.stack)
};
/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

4.Diameter of Binary Tree

說明：算出二元樹的長度

Example:
Given a binary tree
          1
         / \
        2   3
       / \     
      4   5
ans :3 

思維：
資料結構的問題，要先了解二元樹在程式碼中是怎麼運做並找出計算長度的規則，詳情要研究資料結構。
我看不懂js是怎麼跑節點的所以只好參考文件，有關LinkedList的問題，JS都是用遞迴來處理，
所以就是一直遞迴直到null，要多花時間研究JS怎麼處理LinkedList

Answer：

let max 
var diameterOfBinaryTree = function(root) {
    max = 1
    dfs(root)
    return max -1
};
const dfs = node =>{
    if(node === null) return 0
    let left = dfs(node.left)
    let right = dfs(node.right)
    max = Math.max(max,left + right + 1)
    return Math.max(left,right)  + 1
}

5.Last Stone Weight

說明：找出最重的兩顆石頭互敲，直到剩一顆石頭，給出最後一顆石頭的重量。

Example 1：

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

思維：
每次都排序石頭大小,拿頭兩顆相減在放進石頭堆排序，我覺得這方法比較笨

Answer：

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {

   let sortStones = stones.sort((a,b) => b - a )
   
   while(sortStones.length > 1){
       let heavist = sortStones.splice(0,2)
       let boob = heavist[0] - heavist[1]
       sortStones.push(boob)
       sortStones = stones.sort((a,b) => b - a )
   }  
 
   return sortStones[0]
};

6.Contiguous Array

說明：找出0與1數量相等的最大連續陣列長度

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

思維：
這題很難，去solution看理論理解正確的思路會比較有學習效果。
這題我認為對javascript來說不是很好，主要是判斷式如果習慣用全等判斷，那就沒辦法用hashmap。但如果是照範例的JAVA執行是可以的。

Answer：

var findMaxLength = function(nums) {
    let hash = {  0:  '-1'}
    let sum = 0
    let max = 0
    
    for(let i = 0 ; i < nums.length ; i++){
    
        if(nums[i] == 0) sum--
        else sum++
        // 一般習慣都會用 if(!hash[sum]) 或 if(hash[sum] !== null) 
        // 但hash[sum]是undefined 必須用「不太好的」作法 才能執行正確
   
        if(hash[sum] != null)  {
            max = Math.max(max,i - hash[sum])
        }
        else hash[sum] = i
    
    }
    return max
}

7. Perform String Shifts

說明：向左或向右位移字串

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

思維：
我用js的shift、push跟unshift、pop移動字串
向右就是把頭推到後面shift、push
向左就是吐出尾巴塞入前頭unshift、pop

Answer：

var stringShift = function(s, shift) {
     let str_arr = s.split('')
     
    for(let i = 0 ; i < shift.length ; i ++){
        
        let direction = shift[i][0]
        let amount = shift[i][1]
        
        if(direction == 0 ){
           for(let j = 0 ; j < amount;j++){
               let cut = str_arr.shift()
               str_arr.push(cut)
           }
        }
        if(direction == 1){
            for(let j = 0 ; j < amount;j++){
                let cut = str_arr.pop()
                str_arr.unshift(cut)
            }
        }
        
 
    }
    
    return str_arr.join("")
    
};