https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/submissions/566841289/?envType=study-plan-v2&envId=dynamic-programming
没逼出来转移
缓存给掏了
```js
var longestSubsequence = function (arr, difference) {
const dp = new Array(arr.length).fill(1)
let max = 0
const cache = new Map()
for (let index = 0; index < arr.length; index++) {
const num = arr;
if(cache.has(num-difference)){
dp =dp +1
}
cache.set(num, index)
max = Math.max(max, dp)
}
return max
};
```
https://leetcode.cn/problems/uncrossed-lines/submissions/566871965/?envType=study-plan-v2&envId=dynamic-programming
一开始没灵感
看下评论是最长子序列
秒了！
```js
var maxUncrossedLines = function (nums1, nums2) {
const dp = new Array(nums1.length + 1).fill(0).map(() => new Array(nums2.length + 1).fill(0));
for (let index = 1; index < dp.length; index++) {
for (let indey = 1; indey < dp.length; indey++) {
if (nums1 == nums2) {
dp = dp + 1
} else {
dp = Math.max(dp, dp)
}
}
}
return dp
};
```
https://leetcode.cn/problems/longest-arithmetic-subsequence/submissions/567002873/?envType=study-plan-v2&envId=dynamic-programming
这题理清也花了挺久的
主要能感觉到是多维
但是搞了半天等差也没解决
最后发现原来根据数据范围定义
精妙
```js
var longestArithSeqLength = function (nums) {
const minv = _.min(nums);
const maxv = _.max(nums);
const sep = maxv - minv;
let ans = 0
for (let index = -sep; index <= sep; index++) {
if(index==-5){
debugger
}
const cache = new Map()
for (const num of nums) {
if (num >= 0 && num - index <= maxv) {
if (cache.has(num - index)) {
cache.set(num, cache.get(num - index) + 1)
} else {
cache.set(num, 1)
}
ans=Math.max(ans,cache.get(num))
}else{
cache.set(num, 1)
}
}
}
return ans;
};
```
https://leetcode.cn/problems/russian-doll-envelopes/submissions/567169728/?envType=study-plan-v2&envId=dynamic-programming
抬手打上了一波dp，dp超时了
以为是贪心，贪心g了
又试二分，边界没扣明白也g了...
```js
var maxEnvelopes = function (envelopes) {
envelopes = envelopes.sort((a, b) => {
if (a == b) {
return b - a
}
return a - b
})
const arr = []
const findIndex = (num) => {
let left = 0, right = arr.length - 1;
while (left < right) {
const center = left + Math.floor((right-left) / 2)
if (arr < num) {
left = center + 1
} else {
right = center
}
}
return left
}
for (let index = 0; index < envelopes.length; index++) {
const envelop = envelopes;
if (arr < envelop) {
arr.push(envelop)
} else {
const index= findIndex(envelop)
arr=envelop
}
}
return arr.length
};
```
https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/submissions/567246405/?envType=study-plan-v2&envId=dynamic-programming
本来理清了，感觉是二分
还是不熟练
二分被我写错了好多边界炸了
```js
var longestObstacleCourseAtEachPosition = function (obstacles) {
const arr = []
const findIndex = (num) => {
let left = 0, right = arr.length - 1;
while (left < right) {
const center = left + Math.floor((right - left) / 2)
if (arr < num) {
left = center + 1
} else if (arr == num) {
left = center + 1
} else{
right = center
}
}
return left
}
const result = []
for (let index = 0; index < obstacles.length; index++) {
const num = obstacles;
if (index == 8) {
debugger
}
if (arr.length == 0 || arr <= num) {
arr.push(num)
result.push(arr.length)
} else {
const index = findIndex(num);
result.push(arr == num ? index + 2 : index + 1);
arr = num;
}
}
return result
};
```
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/submissions/567248011/?envType=study-plan-v2&envId=dynamic-programming
困难题一波缓存秒了！
```js
var minInsertions = function (s) {
const cache=new Map()
const dfs = (l, r) => {
if(cache.has(`${l} ${r}`)){
return cache.get(`${l} ${r}`)
}
if (l == r || l > r) {
return 0
}
let result=0
if (s === s) {
result= dfs(l + 1, r - 1)
} else {
result= Math.min(dfs(l + 1, r), dfs(l, r - 1)) + 1
}
cache.set(`${l} ${r}`,result)
return result
}
return dfs(0, s.length - 1)
};
```
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/submissions/567260989/?envType=study-plan-v2&envId=dynamic-programming
动态规划版本
```js
var minInsertions = function (s) {
const dp = new Array(s.length).fill(0).map(() => {
return new Array(s.length).fill(0)
})
for (let index = s.length - 2; index >= 0; index--) {
for (let indey = index + 1; indey < s.length; indey++) {
if (s == s) {
dp = dp
} else {
dp = Math.min(dp, dp) + 1
}
}
}
return dp
};
```
https://leetcode.cn/problems/isomorphic-strings/submissions/567292154/?envType=study-plan-v2&envId=top-interview-150
简单题平复一下心情，今天收工
```js
var isIsomorphic = function (s, t) {
const cache1 = {
}
const cache2 = {
}
for (let index = 0; index < s.length; index++) {
const char1 = s;
const char2 = t;
if ((cache1 !== undefined && cache1 !== char2) || (cache2 !== undefined && cache2 !== char1)) {
return false
} else {
cache1 = char2
cache2=char1
}
}
return true
};
```
https://leetcode.cn/problems/word-pattern/submissions/567303904/?envType=study-plan-v2&envId=top-interview-150
过了！
```js
var wordPattern = function (pattern, s) {
s = s.split(" ");
const cache = new Map();
const reverseCache = new Map();
for (let index = 0; index < s.length; index++) {
const word = s;
const pChar = pattern;
if (cache.get(pChar) == undefined &&reverseCache.get(word) == undefined) {
cache.set(pChar, word)
reverseCache.set(word, pChar)
} else {
if (cache.get(pChar) != word) {
return false
}
if (reverseCache.get(word) != pChar) {
return false
}
}
}
for (let index = 0; index < pattern.length; index++) {
const char = pattern;
if (cache.get(char)== undefined) {
return false
}
}
for (let index = 0; index < s.length; index++) {
const word = s;
if (reverseCache.get(word)== undefined) {
return false
}
}
return true
};
```
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/submissions/567381052/?envType=study-plan-v2&envId=top-interview-150
贪心秒了！
```js
var findMinArrowShots = function (points) {
points = points.sort((a, b) => a - b)
let result = ]
for (let index = 1; index < points.length; index++) {
const point = points
const lastPoint = result
if (point<=lastPoint ) {
result.pop();
result.push(, lastPoint), Math.min(point, lastPoint)])
}else{
result.push(point)
}
}
return result.length
};
```