上一主题 下一主题
ScriptCat,新一代的脚本管理器脚本站,与全世界分享你的用户脚本油猴脚本开发指南教程目录
返回列表 发新帖

最长公共子序列分析

[复制链接]
  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-16 01:21:15 | 显示全部楼层 | 阅读模式

    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

    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-16 01:29:32 | 显示全部楼层
    说白了就是一句话
    两个字符串里
    每个字符都可选可不选
    如果相等的话就都选
    如果不相等的话,在两个之中挑一个可以构成最长的选

    那接下来就是看是否有dp状态的延续了

    这部分我是靠感性了
    字符的每次匹配得到的都是目前所能得到的最长的顺序
    每次构建都不会打破,无法构造出来反例
    所以感性上可以构成状态的转移
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-16 01:59:27 | 显示全部楼层

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

    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)
    };
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

  • TA的每日心情
    开心
    2024-3-13 10:14
  • 签到天数: 211 天

    [LV.7]常住居民III

    305

    主题

    4170

    回帖

    4040

    积分

    管理员

    积分
    4040

    管理员荣誉开发者油中2周年生态建设者喜迎中秋油中3周年挑战者 lv2

    发表于 2024-9-17 02:41:45 | 显示全部楼层
    之前感觉做过,但是现在已经一点印象都没了
    上不慕古,下不肖俗。为疏为懒,不敢为狂。为拙为愚,不敢为恶。
    回复

    使用道具 举报

    该用户从未签到

    0

    主题

    25

    回帖

    20

    积分

    助理工程师

    积分
    20
    发表于 2024-9-17 10:15:53 | 显示全部楼层

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

    Array 方式创建
    image.png

    Array.from 方式创建

    image.png

    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-17 19:38:41 | 显示全部楼层
    wuxin0011 发表于 2024-9-17 10:15
    [md]同样代码 就因为数组创建方式不一样 效率差这么多

    **Array**  方式创建

    不同方式竟然差20ms...
    我没认真凹过执行
    现在能过都谢天谢地了
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-17 19:38:50 | 显示全部楼层
    王一之 发表于 2024-9-17 02:41
    之前感觉做过,但是现在已经一点印象都没了

    哥哥也认真刷过lc啊
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-17 19:39:34 | 显示全部楼层
    王一之 发表于 2024-9-17 02:41
    之前感觉做过,但是现在已经一点印象都没了

    https://leetcode.cn/u/codfrm/
    闭上眼睛都能猜到你号
    hhh
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5894

    回帖

    6713

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6713

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-17 19:44:00 | 显示全部楼层

    这题看答案研究了一天

    /**
     * @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;
    };
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

    发表回复

    本版积分规则

    快速回复 返回顶部 返回列表