1

## 1.Subarray Sum Equals K

Example 1:

``````Input:nums = [1,1,1], k = 2
Output: 2
``````

``````  var subarraySum = function(nums, k) {
let sum = k

for(let i = 0; i < nums.length ; i ++){
let sum = 0
for(let j = i ; j < nums.length;j++){
sum += nums[j]
}
}

};
``````

``````var subarraySum = function(nums, k) {
let sum = 0
let hash = new Map()
hash.set(0,1)

for(let i = 0 ; i < nums.length ; i++){
sum += nums[i]
if(hash.has(sum - k)){
}
hash.set(sum, (hash.get(sum) || 0) + 1)
}

};
``````

## 2.Bitwise AND of Numbers Range

5 101
6 110
7 111

``````var rangeBitwiseAnd = function(m, n) {
let nums = []

let bitwise = (a,b) =>{
if(b > n) return
}
if (m==n) return m & n

bitwise(m,m+1)

};
``````

5 >>=1 10
7 >>=1 11

2 >>=1 1
3 >>=1 1

``````var rangeBitwiseAnd = function(m, n) {
let count = 0;

while (m != n) {
count++;
m >>= 1;
n >>= 1;
}

return m << count;
};
``````

## 3.LRU Cache

Example:

``````LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4
``````

``````var LRUCache = function(capacity) {
this.capacity =capacity
this.hash = new Map()
};

/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if(!this.hash.get(key)){
return -1
}
const value = this.hash.get(key);
this.hash.delete(key);
this.hash.set(key, value);
return value;
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {

if(this.hash.has(key)) this.hash.delete(key)

this.hash.set(key,value)
// 超過就把第一個value刪掉。
if(this.hash.size > this.capacity){
const ind =this.hash.keys().next().value
this.hash.delete(ind)
}

};

``````

## 4.Jump Game

Example 1:

``````Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
``````

Example 2:

``````Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it
``````

``````var canJump = function(nums) {
const canJumpFormPosition = (position, nums) => {
if(position == nums.length -1 ){
return true
}
const furthestJump = Math.min( position + nums[position] , nums.length -1)

for(let nextPosition = furthestJump ; nextPosition > position ; nextPosition --){
if(canJumpFormPosition(nextPosition ,nums))  return true
}

return false
}
return canJumpFormPosition(0,nums)
};

``````

``````
var canJump = function(nums) {
const type ={
Good:"G",
Unknown:"U",

}

let memo = new Array(nums.length)

for(let i = 0 ; i < nums.length ; i++){
memo[i] = type.Unknown
}
memo[nums.length - 1] = type.Good

const canJumpFormPosition = (position, nums) => {
if(memo[position] !== type.Unknown){
return  memo[position] == type.Good ? true : false;
}
const furthestJump = Math.min( position + nums[position] , nums.length -1)

for(let nextPosition = furthestJump ; nextPosition > position ; nextPosition --){
if(canJumpFormPosition(nextPosition ,nums)){
memo[position] = type.Good
return true
}
}
return false
}

return canJumpFormPosition(0,nums)
};
``````

``````
var canJump = function(nums) {
let lastInd = nums.length - 1
for(let i = lastInd ; i >= 0 ; i--){
if(i + nums[i] >= lastInd){
lastInd = i
}
}

return lastInd == 0
};

``````

## 5.Longest Common Subsequence

Example 1:

``````Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
``````

Example 2:

``````Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
``````

Example 3:

``````Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
``````

1 dp[1,1] [A,G] Max(0,0)
2 dp[1,2] [A,A] 1
3 dp[1,3] [A,C] Max(0,1)
4 dp[2,1] [G,G] 1
5 dp[2,2] [G,A] Max(1,1)
6 dp[2,3] [G,C] Max(1,1)
7 dp[3,1] [C,G] Max(1,0)
8 dp[3,2] [C,A] Max(1,1)
9 dp[3,3] [C,C] 2

``````var longestCommonSubsequence = function(text1, text2) {
const dp = [];
let m = text1.length;
let n = text2.length;

for (let i = 0; i <= m; i++) {
dp[i] = new Array(n + 1).fill(0);
}

for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1.charAt(i - 1) != text2.charAt(j - 1)) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
}

return dp[m][n];
};

``````

### 6. Maximal Square

Example:

``````Input:

1 0  1 0  0
1 0 `1 1` 1
1 1 `1 1` 1
1 0  0 1  0

Output: 4
``````

`````` let rows = matrix.length
let cols = row !== 0 ? 0 : matrix[0]
``````

``````
for(let i = 0 ; i < rows ; i++){
dp[i] = new Array(cols).fill(0)
}
for (let i = 0; i < rows; i++) {
dp[i][0] = Number(matrix[i][0]);
max = Math.max(max, dp[i][0]);
}
for (let j = 0; j < cols; j++) {
dp[0][j] = Number(matrix[0][j]);
max = Math.max(max, dp[0][j]);
}
``````
``````[ [ 1, 0, 1, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0 ] ]
``````

``````for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
if (matrix[i][j] === 1) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
``````

``````[ [ 1, 0, 1, 0, 0 ],
[ 1, 0, 1, 1, 1 ],
[ 1, 1, 1, 2, 2 ],
[ 1, 0, 0, 1, 0 ] ]
``````

`dp`的思維是把`dp[1][1]`當作是正方形的右下角，這樣就可以用`dp`的特性找出其他三角是否都有`1`，假設右下角為`1`再找`min(其他三角)`為多少，只要`其他三角都一樣長度`，那自然就能在`右下角`得到正方形的長寬。

## 7. Binary Tree Maximum Path Sum

``````sum = node.left + node.right + node.val
``````

Example 1:

``````Input: [1,2,3]

1
/ \
2   3

Output: 6
``````

Example 2:

``````Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
``````
node left right sum
-10 9 42 41
9 null null 9
20 15 7 42

``````var maxPathSum = function(root) {
let sum = root.val;
const dfs = (node) => {
if (!node) return 0;
const left = Math.max(dfs(node.left), 0),
right = Math.max(dfs(node.right), 0);
sum = Math.max(left + right + node.val, sum);
return Math.max(left, right) + node.val;
}
dfs(root);
return sum;
};
``````