对于这道题的一些思考
来源: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
可以的,你要是面试时候也写了这么多种解法,面试官一定会对你刮目相看
00
相似问题