【当前无排名】挑战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

李恒道

https://leetcode.cn/problems/number-of-longest-increasing-subsequence/submissions/566636179/?envType=study-plan-v2&envId=dynamic-programming
这题边界问题很卡
怎么扣都不对
看了答案都没扣对...
最后一顿分析才解决
蛋疼

var findNumberOfLIS = function (nums) {
    const dp = new Array(nums.length).fill(1)
    const dpNums = new Array(nums.length).fill(0)
    dpNums[0]=1
    let maxIndex=0
    for (let index = 1; index < dp.length; index++) {
        const num = nums[index]
        for (let indey = 0; indey < index; indey++) {
            const lastNum = nums[indey]
            if (num > lastNum) {
                dp[index] = Math.max(dp[index], dp[indey] + 1)
            }
        }
        let count = 0
        for (let indey = 0; indey < index; indey++) {
            const lastNum = nums[indey]
            if (num > lastNum&&dp[indey] + 1 == dp[index]) {
                count += dpNums[indey]
            }
        }
        dpNums[index]=count==0?1:count
        if(dp[maxIndex]<dp[index]){
            maxIndex=index
        }
    }
    let result=0
    for (let index = 0; index < dp.length; index++) {
        if(dp[index]==dp[maxIndex]){
            result+=dpNums[index]
        }

    }
    return result
};

李恒道

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/566662079/?envType=study-plan-v2&envId=top-interview-150
双指针，一次过！

var removeDuplicates = function (nums) {
    let left = 1, right = 1;
    while (right < nums.length) {
        if (nums[right] == nums[right - 1]) {
            //不拷贝，直接跳过
            right++;
        } else {
            nums[left] = nums[right]
            right++;
            left++;
        }
    }
    return left
};

李恒道

https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/submissions/566710361/?envType=study-plan-v2&envId=top-interview-150
双指针改造一下秒了

var removeDuplicates = function (nums) {
    let left = 1, right = 1;
    let temp = undefined
    while (right < nums.length) {
        if (nums[right] == nums[right - 1] && nums[right] == (right - 2 == left-1 ? temp : nums[right - 2])) {
            //不拷贝，直接跳过
            right++;
        } else {
            temp = nums[left]
            nums[left] = nums[right]
            right++;
            left++;
        }
    }
    return left
};

李恒道

https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/566726965/?envType=study-plan-v2&envId=dynamic-programming
排序+dp过的
算是朴素直觉吧

var findLongestChain = function (pairs) {
    pairs=pairs.sort((a,b)=>a[0]-b[0])
    const dp = new Array(pairs.length)
    let retLen = 0
    for (let index = 0; index < pairs.length; index++) {
        const pair = pairs[index];
        let maxLen = 1
        for (let indey = 0; indey < index; indey++) {
            if (pairs[indey][1] < pair[0]) {
                maxLen = Math.max(maxLen, dp[indey] + 1)
            }
        }
        dp[index] = maxLen
        retLen = Math.max(retLen, maxLen)
    }
    return retLen
};