2

## 30-Day LeetCode Challenge - Week2

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

2.Recusion

Matters-野生的工程師

## 題目

### 1.Middle of the 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.
``````

``````var middleNode = function(head) {
let listLength = 1
let a = 0

while(test.next){
test = test.next
listLength += 1
}

let mid = Math.floor(listLength / 2) + 1

mid--
}

};
``````

### 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".
``````

``````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

``````
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.
``````

``````/**
* 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
``````

``````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.
``````

``````/**
* @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

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.
``````

``````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"
``````

``````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("")

};
``````