逐类击破 leetcode - 算法篇 - 贪心算法(一) 先导篇
先导:
现实收益角度看,无论你是算法、数据、前端、后端工程师等等,目前大厂互联网公司面试肯定要考察的,国外google和facebook等等更盛 。都是从leetcode或者类似的网站上出题,如果不熟练,一面都过不了,与心仪的公司失之交臂。
我认为它的价值在哪呢?做题本身就可以锻炼解决问题的思维能力、逻辑能力。leetcode题目虽然是小问题,正是这种小问题让你把精力集中在问题本身,而不是去理解繁琐的处理或者业务逻辑(你不关心的逻辑),是希望找到时间复杂度足够低的解决方法,一种‘快’感,最大化发挥计算机资源,你会渐渐形成这种意识,慢慢的可以提升对代码性能的理解。
当然提升代码性能是重要的,可能提高用户友好带来的收益更好,或者代码简洁、可维护、安全都非常重要,只是我认为提升算法性能是最纯粹的。
重点要关注的肯定是思路方法,语言没那么重要,不过通常来说类似c语言比较底层,细节都要从头实现,类似python就会有很多现成的模块可以调用,好模块开发出来就是给你用的,方便又好用,只是用爽的同时可以深入理解或者实现下就更好了。我是选择python,应该是比较好看懂的,可以看懂思路后,用自己熟悉的语言实现一下。
另外啰嗦下:无论你是算法工程师、数据挖掘工程师、自然语言处理工程师还是推荐工程师等等,首先你得是工程师,我们不谈需要多丰富的工程能力,什么高并发多协程各种框架工具分布式,最基础的就是必须有扎实的编程功底。机器学习算法工程师在工程实践中真正花在研究实现算法的时间少之又少,面向应用来说,这就是一个工程问题,工程问题上的改进带来的收益可能更大,当然去理解业务往往带来的效果很显著。总结来说,想要解决好问题,很需要工程能力,过硬的功底是基础。
做leetcode题,一定要有章法可循,否则看着题目也无从下手。根据开源大佬的总结,我合并后如下图,按顺序逐类击破leetcode题,敬请期待,喜欢就关注下。话不多说,开始分享。
贪心策略:保证每次操作都是局部最优的,从而使最后得到的结果是全局最优的。算是一种比较容易想到比较直观的方法吧。
题目理解:
有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个大小。每个孩子只能吃最多一个饼干,且只有饼干的大小大于孩子的饥饿度时,这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
示例:
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
1. 因为饥饿度最小的孩子最容易满足,所以先满足最小饥饿度的。
2. 为了尽量能满足后面饥饿度高的孩子,给予满足孩子的所有饼干中最小的饼干。
这就是贪心策略,也就是说给予目前饥饿度最小的孩子能吃饱的最小饼干。
比较方便的实现是,把孩子和饼干按饥饿度和大小排序,初始化第一个孩子和第一块饼干为起始点(指针),如果孩子饥饿度小于等于饼干大小,指向孩子和饼干的点(指针)都往后移动,也就是满足了这个孩子;否则饼干丢弃,指向饼干的点(指针)往后移,再继续比较和循环下去。
python代码:
class Solution:
def findContentChildren(self, g, s):
g.sort()
s.sort()
child = 0
cookies = 0
while child < len(g) and cookies < len(s):
if g[child] <= s[cookies]:
child += 1
cookies += 1
return child
import heapq
class Solution:
def findContentChildren(self, g, s):
heapq.heapify(g)
heapq.heapify(s)
child = 0
while g and s:
if g[0] <= s[0]:
heapq.heappop(g)
heapq.heappop(s)
child += 1
else:
heapq.heappop(s)
return child
解题思路:
python代码:
class Solution:
def candy(self, ratings):
ratings_size = len(ratings)
if ratings_size < 2:
return ratings_size
candy = [1] * ratings_size
for i in range(ratings_size - 1):
if ratings[i] < ratings[i + 1]:
candy[i + 1] = candy[i] + 1
for i in range(ratings_size - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candy[i] = max(candy[i], candy[i+1] + 1)
return sum(candy)
还有后续,敬请期待!