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

李恒道

https://leetcode.cn/problems/maximum-product-subarray/submissions/564524554/?envType=study-plan-v2&envId=top-100-liked
这题卡了两天，是真做不出来
搞了两个dp，理清递增都搞了好久
太神奇了

var maxProduct = function (nums) {
    const max = new Array(nums.length)
    const min = new Array(nums.length)
    max[0] = min[0] = nums[0]
    let result=nums[0]
    for (let index = 1; index < nums.length; index++) {
        const num = nums[index];
        max[index] = Math.max(num * max[index - 1], num * min[index - 1], num)
        min[index] = Math.min(num * max[index - 1], num * min[index - 1], num)
        result=Math.max(result, max[index])
    }
    return result
};

李恒道

https://leetcode.cn/problems/partition-equal-subset-sum/submissions/564526462/?envType=study-plan-v2&envId=top-100-liked
没憋出来dp
dfs秒的
执行很差

var canPartition = function (nums) {
    const total = nums.reduce((a, b) => {
        return a + b
    }, 0)
    if (total % 2 !== 0) {
        return false
    }
    let result = false
    const map = new Map()
    const dfs = (index, value) => {
        if(map.has(index + '' + value)){
            return
        }
        if (value < 0) {
            return
        }
        if (value === 0) {
            result = true;
            return
        }
        if (index >= nums.length) {
            return
        }
        (!result) && dfs(index + 1, value);
        (!result) && dfs(index + 1, value - nums[index])
        map.set(index + '' + value, false)
    }
    dfs(0, total / 2)
    return result
};

李恒道

原来跟我没什么太大关系
就是缓存或者dp
只不过我边界没扣好...

李恒道

https://leetcode.cn/problems/longest-valid-parentheses/submissions/564751304/?envType=study-plan-v2&envId=top-100-liked
研究了答案
状态转移都扣了半天
这题我是真凹不出来
双指针那个邪道

/**
 * @param {string} s
 * @Return {number}
 */
var longestValidParentheses = function (s) {
    s = s.split("")
    const dp = new Array(s.length).fill(0)
    let max=0
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        if (char == ')' && s[index - 1] === '(') {
            dp[index] = 2
            if (index > 1) {
                dp[index] += dp[index - 2]
            }
        }else  if (char == ')' && s[index - 1] === ')') {
            const lastIndex = index - dp[index - 1] - 1
            if (s[lastIndex] == '(') {
                dp[index] = index - lastIndex + 1
                if (lastIndex > 1) {
                    dp[index] += dp[lastIndex-1]
                }
            }
        }
        max=Math.max(max,dp[index])
    }
    return max

};

李恒道

https://leetcode.cn/problems/unique-paths/submissions/564754082/?envType=study-plan-v2&envId=top-100-liked
多维dp，一次过！

var uniquePaths = function (m, n) {
    const dp = new Array(m - 1).fill(0).map(() => new Array(n).fill(0))
    dp.push(new Array(n).fill(1))
    for (let index = m - 2; index >= 0; index--) {
        for (let indey = n - 1; indey >= 0; indey--) {
            const down = dp[index + 1][indey]
            const right = dp[index][indey + 1] ?? 0
            dp[index][indey]=down+right
        }
    }
    return dp[0][0]
};

李恒道

https://leetcode.cn/problems/minimum-path-sum/submissions/564756268/?envType=study-plan-v2&envId=top-100-liked
一次过，99.5%
牛逼！

var minPathSum = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
    for (let index = m - 1; index >= 0; index--) {
        for (let indey = n - 1; indey >= 0; indey--) {
            if(index==m - 1&&indey==n-1){
                dp[index][indey] =grid[index][indey]
                continue;
            }
            const down = dp[index + 1]?.[indey] ?? Number.MAX_SAFE_INTEGER
            const right = dp[index][indey + 1] ?? Number.MAX_SAFE_INTEGER
            dp[index][indey] = Math.min(down, right) + grid[index][indey]
        }
    }

    return dp[0][0]
};

李恒道

https://leetcode.cn/problems/longest-common-subsequence/?envType=study-plan-v2&envId=top-100-liked
这题研究了一天

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://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-100-liked
简单题
舒缓一下心情

var majorityElement = function (nums) {
    const times = {}
    const border=Math.floor(nums.length/2)+1
    for (const num of nums) {
        times[num] = (times[num] ?? 0) + 1;
        if(times[num]>=border){
            return num
        }
    }
};

李恒道

https://leetcode.cn/problems/edit-distance/submissions/565048394/?envType=study-plan-v2&envId=top-100-liked
缓存大法好

var minDistance = function (word1, word2) {
    word1 = word1.split("")
    word2 = word2.split("")
    const cache = new Map()
    const dfs = (index, indey) => {
        if (indey >= word2.length) {
            if (index >= word1.length) {
                return 0
            } else {
                return word1.length - index
            }
        } else if (index >= word1.length) {
            return dfs(index, indey + 1) + 1
        }

        const flag = `${index} ${indey}`
        if (cache.has(flag)) {
            return cache.get(flag)
        }
        let minStep = Number.MAX_SAFE_INTEGER
        if (word1[index] === word2[indey]) {
            minStep = dfs(index + 1, indey + 1)
        } else {
            const replace = dfs(index + 1, indey + 1);
            if (replace !== undefined) {
                minStep = Math.min(minStep, replace + 1)
            }
            const insert = dfs(index, indey + 1) + 1;
            const del = dfs(index + 1, indey);
            if (del !== undefined) {
                minStep = Math.min(minStep, del + 1)
            }
            minStep = Math.min(minStep, insert)

        }
        cache.set(flag, minStep)
        return minStep
    }
    return dfs(0, 0)
};

王一之

nb 都13页了