【当前无排名】挑战leetcode进入前1w名

王一之

李恒道 发表于 2024-9-19 02:41
1291!论坛竟然大佬恐怖如斯！
@王一之 快来围观

明天都打卡，太强了

李恒道

https://leetcode.cn/problems/longest-palindromic-subsequence/submissions/566026987/?envType=study-plan-v2&envId=dynamic-programming
凭感觉秒的...
状态都没分析，离谱

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[index][index] = 1
    }
    for (let index = s.length - 2; index >= 0; index--) {
        for (let indey = index + 1; indey < s.length; indey++) {
            if (s[index] == s[indey]) {

                dp[index][indey] = 2 + (index == indey - 1 ? 0 : dp[index +1][indey - 1])
            } else {
                dp[index][indey] = Math.max(dp[index + 1][indey - 1],dp[index ][indey - 1],dp[index+1][indey])
            }
        }
    }
    return dp[0][s.length-1]
};

李恒道

https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?envType=study-plan-v2&envId=dynamic-programming
这题没理明白，看的答案，太妙了

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[0].length; index++) {
        dp[0][index] = dp[0][index - 1] + s2[index - 1].charCodeAt()
    }
    for (let index = 1; index < dp.length; index++) {
        dp[index][0] = dp[index - 1][0] + s1[index - 1].charCodeAt()
    }
    for (let index = 1; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            if (s1[index - 1] == s2[indey - 1]) {
                dp[index][indey] = dp[index - 1][indey - 1]
            } else {
                dp[index][indey] = Math.min(dp[index][indey-1] + s2[indey - 1].charCodeAt(), dp[index-1][indey ]+ s1[index - 1].charCodeAt())
            }
        }
    }
    return dp[s1.length][s2.length]
};```

李恒道

李恒道 发表于 2024-9-20 04:57

[md]https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?env ...

该题的dfs解，练习思路用的，没缓存优化

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[x].charCodeAt()
        }
        if (x >= s1.length) {
            return dfs(x, y + 1) + s2[y].charCodeAt()
        }
        if (s1[x] === s2[y]) {
            return dfs(x + 1, y + 1)
        } else {
            return Math.min(dfs(x + 1, y) + s1[x].charCodeAt(), dfs(x, y + 1) + s2[y].charCodeAt())
        }
    }
    return dfs(0, 0)
};

李恒道

https://leetcode.cn/problems/distinct-subsequences/submissions/566282746/?envType=study-plan-v2&envId=dynamic-programming
缓存dp过了，动态依赖有点难分析，跟上一题一个套路

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

wuxin0011

李恒道 发表于 2024-9-20 04:57
[md]https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/566281267/?env ...

构造两个字符串的价值 - 最长公共子序列 * 2