最长公共子序列分析

李恒道

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状态的延续了

这部分我是靠感性了
字符的每次匹配得到的都是目前所能得到的最长的顺序
每次构建都不会打破，无法构造出来反例
所以感性上可以构成状态的转移

李恒道

不划出来表，靠缓存的代码如下

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[x]===text2[y]) {
            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)
};

王一之

之前感觉做过，但是现在已经一点印象都没了

wuxin0011

同样代码 就因为数组创建方式不一样 效率差这么多

Array 方式创建

Array.from 方式创建

李恒道

wuxin0011 发表于 2024-9-17 10:15
[md]同样代码 就因为数组创建方式不一样 效率差这么多

**Array**  方式创建

不同方式竟然差20ms...
我没认真凹过执行
现在能过都谢天谢地了

李恒道

王一之 发表于 2024-9-17 02:41
之前感觉做过，但是现在已经一点印象都没了

哥哥也认真刷过lc啊

李恒道

王一之 发表于 2024-9-17 02:41
之前感觉做过，但是现在已经一点印象都没了

https://leetcode.cn/u/codfrm/
闭上眼睛都能猜到你号
hhh

李恒道

这题看答案研究了一天

/**
 * @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[index];
      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;
};