2

## 1.Product of Array Except Self

Example

``````Input:  [1,2,3,4]
Output: [24,12,8,6]
``````

Solution 則是利用一左一右的陣列來處理這問題，首先要建立兩個陣列，`L``R`

nums 1 2 3 4
L 1 1 2 6
numsR 4 3 2 1
R 1 4 12 24

`R`需要再反轉一次`R.revserse`，真正的`R`為：

nums 1 2 3 4
R 24 12 4 1

`L[lastIndex]`的值就是除了`nums[lastIndex]`的所有值相成。
`R[firstIndex]`的值就是除了`nums[firstIndex]`以外相成的值。

Ans

``````var productExceptSelf = function(nums) {

let L = [1]
let R = [1]
let startNum = 1
for(let i = 0 ; i < nums.length-1; i++){
L[i+1] = (L[i+1-1] * nums[i])
}
let numsR = nums.reverse()
for(let i = 0 ; i < nums.length-1 ; i++){

R[i+1] = R[i+1-1] * numsR[i]

}
R = R.reverse()

for(let i = 0 ; i < nums.length; i++){
}

};
``````

## 2.Valid Parenthesis String

Example 1

``````Input: "()"
Output: True
``````

Example 2

``````Input: "(*)"
Output: True
``````

Example 3

``````Input: "(*))"
Output: True
``````

`*`可以代表任一括號，也可以是空字串。

`lo``hi`代表左右括號的數量

• `lo` += `(``+1`否則`-1`
• `hi` += `)``+1`否則`-1`

( 1 -1 false
()) 1 -2 false
(** -1 -2 true
(**) -2 -2 true

Ans

``````var checkValidString = function(s) {
let lo = 0
let hi = 0

for(let i = 0; i < s.length ; i ++){
lo += s[i] == "(" ? 1 : -1
hi += s[i] != ")" ? 1 : -1
if(hi < 0)  break
lo = Math.max(lo,0)
}

return lo == 0
};
``````

## 3.Number of Islands

Example 1:

``````Input:
11110
11010
11000
00000

Output: 1
``````

Example 2:

``````Input:
11000
11000
00100
00011

Output: 3
``````

`DFS`適合用來探尋未知的節點，`DFS`會反覆的搜尋任何可達到的節點直到所有節點被發現為止。

`recusion`遞迴適合做`DFS`的基底

`leetcode`普遍解法是在二維陣列的索引範圍內遇到1先算+1並開始從這個`array[i][j]`的節點開始走訪在陣列的範圍內不斷尋找上下左右是`1`的節點，找到後改成0。

``````const dfs = (i,j,grid) =>{

if(i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0){
return 0
}

grid[i][j] = 0

dfs(i+1,j,grid)
dfs(i-1,j,grid)
dfs(i,j-1,grid)
dfs(i,j+1,grid)

return 1
}
``````

Ans

``````var numIslands = function(grid) {

const dfs = (i,j,grid) =>{

if(i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0){
return 0
}

grid[i][j] = 0

dfs(i+1,j,grid)
dfs(i-1,j,grid)
dfs(i,j-1,grid)
dfs(i,j+1,grid)

return 1
}

for(let i = 0 ; i < grid.length  ; i++){
for(let j = 0 ; j < grid[i].length ; j++){
if(grid[i][j] == 1)  answer += dfs(i,j,grid)
}
}

};
``````

### 4. Minimum Path Sum

Example:

``````Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

``````

1.第一列的每個元素要加前一個元素和。
2.第一行的每個元素要加前一個元素和。
3.中間的梯形路徑要加前一格元素和。

``````[
[1,3,1],
[2,5,1],
[6,2,1]
]

``````

``````[
[1,4,5],
[2,5,1],
[6,2,1]
]
``````

``````[
[1,  4  ,  5  ],
[2,(2+5),(1+5)],
[6,(2+6),(1+6)]
]
min : 7
``````

Ans

``````var minPathSum = function(grid) {
const row = grid.length
const col = grid[0].length
// 第一列
for(let i = 1 ; i < row ; i++){
grid[i][0] += grid[i-1][0]
}
// 第一行
for(let j = 1 ; j < col ; j++){
grid[0][j] += grid[0][j-1]
}
// 中間梯形路徑
for(let i = 1 ; i < row ; i++){
for(let j = 1 ; j < col ; j++){
grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1])
}
}

return grid[row-1][col-1]

};
``````

### 5.Search in Rotated Sorted Array

Example 1:

``````Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

``````

Example 2:

``````Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
``````

1.找出`target`的索引值，沒有就回傳`-1`
2.但如果`target`是陣列中的元素就要回傳索引值。如`arr = [1,4],target =4 ,ans =1`

Ans

``````
var search = function(nums, target) {
if(nums.some(num => num == target)){
if(target === nums.find(num => num === target) ){
return nums.findIndex(num => num === target)
}else{
return nums[target]
}

}else{
return -1
}
};

``````

### 6.Construct Binary Search Tree from Preorder Traversal

Example 1:

``````Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

``````

``````[8,5,1,7,10,12], //建立root = 8;
[5,1,7], root = 8 ,left tree
[10,12], root = 8 ,right tree
[1],     root = 5 ,left tree
[7]      root = 5 ,right tree
[]       roor = 10,left tree
[12],    root = 10,right tree

``````

Ans

``````
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var bstFromPreorder = function(preorder) {
if(preorder.length === 0) return null
if(preorder.length === 1) return new TreeNode(preorder[0])
let root =  new TreeNode(preorder[0])
let left  = bstFromPreorder(preorder.slice(1).filter(ele => ele < preorder[0]))
let right = bstFromPreorder(preorder.slice(1).filter(ele => ele > preorder[0]))
if(root) root.left = left
if(root) root.right = right
return root
};

``````