https://leetcode.cn/problems/maximum-product-subarray/submissions/564524554/?envType=study-plan-v2&envId=top-100-liked
这题卡了两天，是真做不出来
搞了两个dp，理清递增都搞了好久
太神奇了
```js
var maxProduct = function (nums) {
const max = new Array(nums.length)
const min = new Array(nums.length)
max = min = nums
let result=nums
for (let index = 1; index < nums.length; index++) {
const num = nums;
max = Math.max(num * max, num * min, num)
min = Math.min(num * max, num * min, num)
result=Math.max(result, max)
}
return result
};
```
https://leetcode.cn/problems/partition-equal-subset-sum/submissions/564526462/?envType=study-plan-v2&envId=top-100-liked
没憋出来dp
dfs秒的
执行很差
```js
var canPartition = function (nums) {
const total = nums.reduce((a, b) => {
return a + b
}, 0)
if (total % 2 !== 0) {
return false
}
let result = false
const map = new Map()
const dfs = (index, value) => {
if(map.has(index + '' + value)){
return
}
if (value < 0) {
return
}
if (value === 0) {
result = true;
return
}
if (index >= nums.length) {
return
}
(!result) && dfs(index + 1, value);
(!result) && dfs(index + 1, value - nums)
map.set(index + '' + value, false)
}
dfs(0, total / 2)
return result
};
```
原来跟我没什么太大关系
就是缓存或者dp
只不过我边界没扣好...
https://leetcode.cn/problems/longest-valid-parentheses/submissions/564751304/?envType=study-plan-v2&envId=top-100-liked
研究了答案
状态转移都扣了半天
这题我是真凹不出来
双指针那个邪道
```js
/**
* @param {string} s
* @Return {number}
*/
var longestValidParentheses = function (s) {
s = s.split("")
const dp = new Array(s.length).fill(0)
let max=0
for (let index = 0; index < s.length; index++) {
const char = s;
if (char == ')' && s === '(') {
dp = 2
if (index > 1) {
dp += dp
}
}elseif (char == ')' && s === ')') {
const lastIndex = index - dp - 1
if (s == '(') {
dp = index - lastIndex + 1
if (lastIndex > 1) {
dp += dp
}
}
}
max=Math.max(max,dp)
}
return max
};
```
https://leetcode.cn/problems/unique-paths/submissions/564754082/?envType=study-plan-v2&envId=top-100-liked
多维dp，一次过！
```js
var uniquePaths = function (m, n) {
const dp = new Array(m - 1).fill(0).map(() => new Array(n).fill(0))
dp.push(new Array(n).fill(1))
for (let index = m - 2; index >= 0; index--) {
for (let indey = n - 1; indey >= 0; indey--) {
const down = dp
const right = dp ?? 0
dp=down+right
}
}
return dp
};
```
https://leetcode.cn/problems/minimum-path-sum/submissions/564756268/?envType=study-plan-v2&envId=top-100-liked
一次过，99.5%
牛逼！
```js
var minPathSum = function (grid) {
const m = grid.length;
const n = grid.length;
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
for (let index = m - 1; index >= 0; index--) {
for (let indey = n - 1; indey >= 0; indey--) {
if(index==m - 1&&indey==n-1){
dp =grid
continue;
}
const down = dp?. ?? Number.MAX_SAFE_INTEGER
const right = dp ?? Number.MAX_SAFE_INTEGER
dp = Math.min(down, right) + grid
}
}
return dp
};
```
https://leetcode.cn/problems/longest-common-subsequence/?envType=study-plan-v2&envId=top-100-liked
这题研究了一天
```js
var longestCommonSubsequence = function (text1, text2) {
text1 = text1.split("")
text2 = text2.split("")
const cache = new Map()
const dfs = (x, y) => {
const flag = `${x} ${y}`
if (x >= text1.length || y >= text2.length) {
return 0
}
if(cache.has(flag)){
return cache.get(flag)
}
let maxLength = undefined
if (text1===text2) {
maxLength = dfs(x + 1, y + 1) + 1
} else {
maxLength = Math.max(dfs(x + 1, y),
dfs(x, y + 1))
}
cache.set(flag, maxLength)
return maxLength
}
return dfs(0, 0)
};
```
https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-100-liked
简单题
舒缓一下心情
```js
var majorityElement = function (nums) {
const times = {}
const border=Math.floor(nums.length/2)+1
for (const num of nums) {
times = (times ?? 0) + 1;
if(times>=border){
return num
}
}
};
```
https://leetcode.cn/problems/edit-distance/submissions/565048394/?envType=study-plan-v2&envId=top-100-liked
缓存大法好
```js
var minDistance = function (word1, word2) {
word1 = word1.split("")
word2 = word2.split("")
const cache = new Map()
const dfs = (index, indey) => {
if (indey >= word2.length) {
if (index >= word1.length) {
return 0
} else {
return word1.length - index
}
} else if (index >= word1.length) {
return dfs(index, indey + 1) + 1
}
const flag = `${index} ${indey}`
if (cache.has(flag)) {
return cache.get(flag)
}
let minStep = Number.MAX_SAFE_INTEGER
if (word1 === word2) {
minStep = dfs(index + 1, indey + 1)
} else {
const replace = dfs(index + 1, indey + 1);
if (replace !== undefined) {
minStep = Math.min(minStep, replace + 1)
}
const insert = dfs(index, indey + 1) + 1;
const del = dfs(index + 1, indey);
if (del !== undefined) {
minStep = Math.min(minStep, del + 1)
}
minStep = Math.min(minStep, insert)
}
cache.set(flag, minStep)
return minStep
}
return dfs(0, 0)
};
```
nb 都13页了