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

李恒道

https://leetcode.cn/problems/triangle/submissions/565938667/?envType=study-plan-v2&envId=dynamic-programming
基础dp，秒

var minimumTotal = function (triangle) {
    const dp = new Array(triangle[triangle.length - 1].length).fill(0)

    for (let index = triangle.length - 1; index >= 0; index--) {
        for (let pos = 0; pos <= index; pos++) {
            dp[pos] = Math.min(dp[pos], dp[pos + 1] ?? 0) + triangle[index][pos]
        }
    }
    return dp[0]
};

李恒道

wuxin0011 发表于 2024-9-18 23:59
这是我LC主页： https://leetcode.cn/u/agitated-curranfnd/

1291!论坛竟然大佬恐怖如斯！
@王一之 快来围观

李恒道

wuxin0011 发表于 2024-9-19 00:02
刷题也就图一乐

握草，大佬牛逼啊
我估计刷到年末才能勉强上500

李恒道

wuxin0011 发表于 2024-9-18 23:59
这是我LC主页： https://leetcode.cn/u/agitated-curranfnd/

冒昧问一嘴，哥哥大厂工作吗

李恒道

https://leetcode.cn/problems/minimum-falling-path-sum/submissions/565939151/?envType=study-plan-v2&envId=dynamic-programming
基础dp，秒

var minFallingPathSum = function (matrix) {
    const dp = new Array(matrix.length).fill(0).map(() => {
        return new Array(matrix[0].length).fill(0)
    })
    dp[matrix.length - 1] = matrix[matrix.length - 1]
    for (let index = matrix.length - 2; index >= 0; index--) {
        for (let indey = matrix[0].length - 1; indey >= 0; indey--) {
            const min = Math.min(dp[index + 1][indey], dp[index + 1][indey - 1] ?? Number.MAX_SAFE_INTEGER,
                dp[index + 1][indey + 1] ?? Number.MAX_SAFE_INTEGER
            )
            dp[index][indey] = min + matrix[index][indey]
        }
    }
    return Math.min(...dp[0])
};

李恒道

https://leetcode.cn/problems/maximal-square/submissions/565941333/?envType=study-plan-v2&envId=dynamic-programming
dp的转移方程没理明白
但是凭直觉过了
离谱

var maximalSquare = function (matrix) {
    const dp = new Array(matrix.length).fill(0).map(() => {
        return new Array(matrix[0].length).fill(0)
    })
    dp[0] = matrix[0].map((num) => parseInt(num))
    let maxReact = Math.max(...dp[0])
    for (let index = 1; index < matrix.length; index++) {
        for (let indey = 0; indey < matrix[0].length; indey++) {
            if (matrix[index][indey] == 1) {
                if (indey !== 0 && dp[index - 1][indey - 1] !== 0 && dp[index][indey - 1] !== 0 && dp[index - 1][indey] !== 0) {
                    const height = Math.min(dp[index - 1][indey - 1], dp[index][indey - 1])
                    const width = Math.min(dp[index - 1][indey - 1], dp[index - 1][indey])
                    dp[index][indey] = Math.min(height, width)+1
                    if (dp[index][indey] == 3) {
                        debugger
                    }
                } else {
                    dp[index][indey] = 1
                }
                maxReact = Math.max(maxReact, dp[index][indey])
            }
        }
    }
    return maxReact * maxReact
};

李恒道

https://leetcode.cn/problems/merge-sorted-array/submissions/565941857/?envType=study-plan-v2&envId=top-interview-150
简单题，放松一下

var merge = function (nums1, m, nums2, n) {
    n=n-1;
    m=m-1;
    let pos = nums1.length - 1
    while (m >= 0 || n >= 0) {
        if (m < 0) {
            nums1[pos] = nums2[n];
            pos--;
            n--;
            continue;
        }
        if (n < 0) {
            nums1[pos] = nums1[m];
            pos--;
            m--;
           break;
        }
        if (nums2[n] > nums1[m]) {
            nums1[pos] = nums2[n];
            pos--;
            n--;
            continue;
        } else {
            nums1[pos] = nums1[m];
            pos--;
            m--;
            continue;
        }
    }
};

wuxin0011

不是大佬，是菜鸡

李恒道

wuxin0011 发表于 2024-9-19 09:44
不是大佬，是菜鸡

哥哥还算菜鸡
我听说刷500道基本中厂面试medium无脑过，hard随缘秒
哥哥1300简直路人王了

李恒道

https://leetcode.cn/problems/count-square-submatrices-with-all-ones/
正方形的类似dp题
会了正方形的这题就好过了

var countSquares = function (matrix) {
    const dp = new Array(matrix.length).fill(0).map(() => {
        return new Array(matrix[0].length).fill(0)
    })
    dp[0] = matrix[0].map((num) => parseInt(num))
    let result = 0
    for (let index = 0; index < matrix[0].length; index++) {
        if (matrix[0][index] == 1) {
            result++
        }

    }
    for (let index = 1; index < matrix.length; index++) {
        for (let indey = 0; indey < matrix[0].length; indey++) {
            if (matrix[index][indey] == 1) {
                if (indey !== 0 && dp[index - 1][indey - 1] !== 0 && dp[index][indey - 1] !== 0 && dp[index - 1][indey] !== 0) {

                    dp[index][indey] = Math.min(dp[index - 1][indey - 1], dp[index][indey - 1], dp[index - 1][indey]) + 1
                    result+=dp[index][indey]
                } else {
                    dp[index][indey] = 1
                    result++
                }
            }
        }
    }
    return result
};