最长公共子序列分析
https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked这题是真没压住，dp还是不熟
假设两个字串一个为n，一个为m
dp时i为n的0-i位置，j为m的0-j位置
当n和j相等时，状态转移为n-1,j-1的数据+1即可
假设不等，就涉及到了到底选择哪个变量
这个时候就引入了几个子问题
1.是否应该选择i-1,j-1？
不应该，假设字符串是
ABC D
ABD K
此时i，j-1才是最大的，而最坏情况也是
ABC D
ABC K
此时选择i，j-1或i-1，j都等于i-1，j-1，所以无需选择i-1，j-1
2.如果i位跟j-1的出现重叠匹配怎么办？会不会导致最大长度出问题？
如
ABDE D
ABD
而dp会遍历所有可能性，如果一个较前的字符跟一个较后的字符相匹配
随着顺序的逐渐增加
最后会导致较前的还没有到结尾，而较后的字符已经结束了，无法成为dp的i,j的结果
其次dp每一次比对的都是对于当前ij位置结尾的字符串，属于最后一个字符，应当选择最后一个
3.如果i位跟j-1不重叠
如
ABE D
ABD
此时应该进行计算最大位置
综上所述
如果i跟j位不相等
则无需计算i-1及j-1
但需计算i，j-1以及j，i-1 说白了就是一句话
两个字符串里
每个字符都可选可不选
如果相等的话就都选
如果不相等的话，在两个之中挑一个可以构成最长的选
那接下来就是看是否有dp状态的延续了
这部分我是靠感性了
字符的每次匹配得到的都是目前所能得到的最长的顺序
每次构建都不会打破，无法构造出来反例
所以感性上可以构成状态的转移
不划出来表，靠缓存的代码如下
```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)
};
``` 之前感觉做过，但是现在已经一点印象都没了 同样代码 就因为数组创建方式不一样 效率差这么多
**Array**方式创建
!(data/attachment/forum/202409/17/101442qk09pmtuka4uop4x.png)
**Array.from**方式创建
!(data/attachment/forum/202409/17/101530tle9jhhh766r62jy.png) wuxin0011 发表于 2024-9-17 10:15
同样代码 就因为数组创建方式不一样 效率差这么多
**Array**方式创建
不同方式竟然差20ms...
我没认真凹过执行
现在能过都谢天谢地了 王一之 发表于 2024-9-17 02:41
之前感觉做过，但是现在已经一点印象都没了
哥哥也认真刷过lc啊 王一之 发表于 2024-9-17 02:41
之前感觉做过，但是现在已经一点印象都没了
https://leetcode.cn/u/codfrm/
闭上眼睛都能猜到你号
hhh 这题看答案研究了一天
```js
/**
* @param {number[]} nums
* @Return {number}
*/
var findDuplicate = function (nums) {
let l = 0;
let r = nums.length - 1;
const getCount = (pos) => {
let ret = 0;
for (let index = 0; index < nums.length; index++) {
const num = nums;
if (num <= pos) {
ret++;
}
}
return ret;
};
let ans = undefined;
while (l <= r) {
const center = Math.floor((r + l) / 2);
const count = getCount(center);
if (count <= center) {
l = center + 1;
} else {
ans = center;
r = center - 1;
}
}
return ans;
};
```
页:
[1]