30-Day LeetCode Challenge - Week2

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: trueExplanation: Both S and T become "ac".

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

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

Example 4:Input: S = "a#c", T = "b"Output: falseExplanation: 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   5ans :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: 1Explanation: 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: 2Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]Output: 2Explanation: [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("")    };