李恒道 发表于 2024-9-19 02:41
1291!论坛竟然大佬恐怖如斯！
@王一之 快来围观
明天都打卡，太强了
https://leetcode.cn/problems/longest-palindromic-subsequence/submissions/566026987/?envType=study-plan-v2&envId=dynamic-programming
凭感觉秒的...
状态都没分析，离谱
```js
var longestPalindromeSubseq = function (s) {
s = s.split("")
const dp = new Array(s.length).fill(0).map(() => new Array(s.length).fill(0))
for (let index = 0; index < dp.length; index++) {
dp = 1
}
for (let index = s.length - 2; index >= 0; index--) {
for (let indey = index + 1; indey < s.length; indey++) {
if (s == s) {
dp = 2 + (index == indey - 1 ? 0 : dp)
} else {
dp = Math.max(dp,dp,dp)
}
}
}
return dp
};
```
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?envType=study-plan-v2&envId=dynamic-programming
这题没理明白，看的答案，太妙了
```js
var minimumDeleteSum = function (s1, s2) {
const dp = new Array(s1.length + 1).fill(0).map(() => new Array(s2.length + 1).fill(0))
for (let index = 1; index < dp.length; index++) {
dp = dp + s2.charCodeAt()
}
for (let index = 1; index < dp.length; index++) {
dp = dp + s1.charCodeAt()
}
for (let index = 1; index < dp.length; index++) {
for (let indey = 1; indey < dp.length; indey++) {
if (s1 == s2) {
dp = dp
} else {
dp = Math.min(dp + s2.charCodeAt(), dp+ s1.charCodeAt())
}
}
}
return dp
};```
李恒道 发表于 2024-9-20 04:57
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?env ...
该题的dfs解，练习思路用的，没缓存优化
```js
var minimumDeleteSum = function (s1, s2) {
const dfs = (x, y) => {
if (x >= s1.length && y >= s2.length) {
return 0
}
if (y >= s2.length) {
return dfs(x + 1, y) + s1.charCodeAt()
}
if (x >= s1.length) {
return dfs(x, y + 1) + s2.charCodeAt()
}
if (s1 === s2) {
return dfs(x + 1, y + 1)
} else {
return Math.min(dfs(x + 1, y) + s1.charCodeAt(), dfs(x, y + 1) + s2.charCodeAt())
}
}
return dfs(0, 0)
};
```
https://leetcode.cn/problems/distinct-subsequences/submissions/566282746/?envType=study-plan-v2&envId=dynamic-programming
缓存dp过了，动态依赖有点难分析，跟上一题一个套路
```js
var numDistinct = function (s, t) {
const cache = new Map()
const dfs = (x, y) => {
if (y >= t.length) {
return 1
}
if (x >= s.length) {
return 0
}
if(cache.has(`${x} ${y}`)){
return cache.get(`${x} ${y}`)
}
let result = 0
if (s === t) {
result = dfs(x + 1, y + 1) + dfs(x + 1, y)
} else {
result = dfs(x + 1, y)
}
cache.set(`${x} ${y}`, result)
return result
}
return dfs(0, 0)
};
```
李恒道 发表于 2024-9-20 04:57
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?env ...
构造两个字符串的价值 - 最长公共子序列 * 2
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/submissions/566636179/?envType=study-plan-v2&envId=dynamic-programming
这题边界问题很卡
怎么扣都不对
看了答案都没扣对...
最后一顿分析才解决
蛋疼
```js
var findNumberOfLIS = function (nums) {
const dp = new Array(nums.length).fill(1)
const dpNums = new Array(nums.length).fill(0)
dpNums=1
let maxIndex=0
for (let index = 1; index < dp.length; index++) {
const num = nums
for (let indey = 0; indey < index; indey++) {
const lastNum = nums
if (num > lastNum) {
dp = Math.max(dp, dp + 1)
}
}
let count = 0
for (let indey = 0; indey < index; indey++) {
const lastNum = nums
if (num > lastNum&&dp + 1 == dp) {
count += dpNums
}
}
dpNums=count==0?1:count
if(dp<dp){
maxIndex=index
}
}
let result=0
for (let index = 0; index < dp.length; index++) {
if(dp==dp){
result+=dpNums
}
}
return result
};
```
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/566662079/?envType=study-plan-v2&envId=top-interview-150
双指针，一次过！
```js
var removeDuplicates = function (nums) {
let left = 1, right = 1;
while (right < nums.length) {
if (nums == nums) {
//不拷贝，直接跳过
right++;
} else {
nums = nums
right++;
left++;
}
}
return left
};
```
https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/submissions/566710361/?envType=study-plan-v2&envId=top-interview-150
双指针改造一下秒了
```js
var removeDuplicates = function (nums) {
let left = 1, right = 1;
let temp = undefined
while (right < nums.length) {
if (nums == nums && nums == (right - 2 == left-1 ? temp : nums)) {
//不拷贝，直接跳过
right++;
} else {
temp = nums
nums = nums
right++;
left++;
}
}
return left
};
```
https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/566726965/?envType=study-plan-v2&envId=dynamic-programming
排序+dp过的
算是朴素直觉吧
```js
var findLongestChain = function (pairs) {
pairs=pairs.sort((a,b)=>a-b)
const dp = new Array(pairs.length)
let retLen = 0
for (let index = 0; index < pairs.length; index++) {
const pair = pairs;
let maxLen = 1
for (let indey = 0; indey < index; indey++) {
if (pairs < pair) {
maxLen = Math.max(maxLen, dp + 1)
}
}
dp = maxLen
retLen = Math.max(retLen, maxLen)
}
return retLen
};
```