对于这道题的一些思考

来源:14-2 LeetCode:455. 分饼干

weixin_慕用7109063

2022-12-07

看完老师的解答之后,自己尝试写了一下,发现了一个很纠结的事情:在看到这道题之后,很难一下子就决定是从前往后还是从后往前遍历,遍历时候是遍历胃口还是遍历饼干。于是尝试写了一下,发现4种组合其实都可以,但是每种写法对应的思路是有差别的。从前往后遍历饼干(老师在视频里的写法),和从后往前遍历胃口的代码是最简洁的。从前往后遍历胃口和从后往前遍历饼干代码量会稍微多一点。最后我总结出2种自认为更容易理解的写法:

方法1:

var findContentChildren = function (g, s) {
    const sortHelper = function (a, b) {
        return a - b
    }
    g.sort(sortHelper)
    s.sort(sortHelper)
    let gIndex = 0
    let sIndex = 0
    let res = 0
    //当每个孩子都分到一块饼干,或饼干全部被分配时,结束循环
    while (gIndex < g.length && sIndex < s.length) {
        //sIndex对应饼干能满足gIndex对应胃口
        if (g[gIndex] <= s[sIndex]) {
            res++
            gIndex++
            sIndex++
            //sIndex对应饼干不能满足gIndex对应胃口,说明这个饼干连剩余孩子中胃口最小的孩子都无法满足,自然无法满足其他孩子,此饼干作废
        } else {
            sIndex++
        }
    }
    return res
}

方法2:

var findContentChildren = function (g, s) {
    const sortHelper = function (a, b) {
        return a - b
    }
    g.sort(sortHelper)
    s.sort(sortHelper)
    let gIndex = g.length - 1
    let sIndex = s.length - 1
    let res = 0
    //当每个孩子都分到一块饼干,或饼干全部被分配时,结束循环
    while (gIndex >= 0 && sIndex >= 0) {
        //sIndex对应饼干能满足gIndex对应胃口
        if (g[gIndex] <= s[sIndex]) {
            res++
            gIndex--
            sIndex--
            //sIndex对应饼干不能满足gIndex对应胃口,说明这个孩子胃口太大,连最大的饼干都无法满足,其他饼干自然也无法满足,不考虑给这个孩子分配饼干
        } else {
            gIndex--
        }
    }
    return res
}
写回答

1回答

lewis

2022-12-07

可以的,你要是面试时候也写了这么多种解法,面试官一定会对你刮目相看

0
0

JavaScript版数据结构与算法 轻松解决前端算法面试

夯实算法基础,填补技术短板,助力面试考题最后一公里

2421 学习 · 670 问题

查看课程