- 贪心算法是算法设计中一种方法
- 期盼通过每个阶段的局部最优选择,从而达到全局的最优选择
- 结果不一定是最优的
leetcode:455 分饼干
- 解题思路
- 局部最优:技能满足孩子,还消耗最小
- 先将“较小的饼干”分给胃口最小的孩子
- 解题步骤
- 饼干数组和胃口数组进行生序排序
- 遍历饼干数组,找到能满足第一个孩子的饼干
- 然后继续遍历饼干数组,找到满足第二、三个、n个孩子的饼干
code
// s 饼干数组
// g 胃口数组
// 时间复杂度O(n*logN) 空间复杂度O(1)
var findContentChildren = function (g, s) {
// 升序排序
const sortFun = function(a, b) {
return a - b
}
g.sort(sortFun)
s.sort(sortFun)
let i = 0
s.forEach(n => {
if (n >= g[i]) {
i++
}
})
return i
}
leetcode:122. 买卖股票的最佳时机 II
- 解题思路
- 前提:上帝视角,知道未来的价格
- 局部最优:见好就收,见差就不动,不做任何长远打算
- 解题步骤
- 新建一个变量,用来总计总利润
- 遍历价格数组,如果当前价格比昨天高。就在昨天买,今天卖,否则就不交易
- 遍历结束后,返回所有利润之和
code
// 时间复杂度O(n), 空间复杂度O(1)
var maxProfit = function(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1]
}
}
return profit;
}