455. Assign Cookies (Easy)
题目描述
有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃
最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩
子可以吃饱。
输入输出样例
输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数
量。
Input: [1,2], [1,2,3]
Output: 2
在这个样例中，我们可以给两个孩子喂[1,2]、[1,3]、[2,3] 这三种组合的任意一种。
题解
因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可
以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这
个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到
没有满足条件的饼干存在。
简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。
至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。
这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。
具体代码
耗时：40ms 61.49
内存消耗：13.8MB 88.75
def findContentChildren(g, s):
# 孩子数量/小饼干数量
# 一个孩子只能吃最多一个饼干
# 先对孩子和饼干的大小进行排序
g=sorted(g)
s=sorted(s)
child,cookie=0,0
while child<len(g) and cookie<len(s):
if g[child]<=s[cookie]:
child+=1
cookie+=1
else:
cookie+=1
return child
135. Candy (Hard)
题目描述
一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一
个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所
有孩子至少要有一个糖果。求解最少需要多少个糖果。
输入输出样例
输入是一个数组，表示孩子的评分。输出是最少糖果的数量。
Input: [1,0,2]
Output: 5
在这个样例中，最少的糖果分法是[2,1,2]。
题解
做完了题目455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一
道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为1；
先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的
糖果数加1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数
不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1。通过这两次遍历，
分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一
侧的大小关系。
在样例中，我们初始化糖果分配为[1,1,1]，第一次遍历更新后的结果为[1,1,2]，第二次遍历
更新后的结果为[2,1,2]。
具体代码
耗时：36ms 77.31%
内存消耗：15.4MB 18.49%
def candy(ratings):
if len(ratings)<2:
return len(ratings)
# 把所有孩子的糖果数初始化为1
n=[1]*len(ratings)
# 如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加1
for i in range(1,len(ratings)):
if ratings[i]>ratings[i-1]:
n[i]=n[i-1]+1
# 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数
# 不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1
for j in range(len(ratings)-1,0,-1):
if ratings[j]<ratings[j-1]:
n[j-1]=max(n[j-1],n[j]+1)
return sum(n)
435. Non-overlapping Intervals (Medium)
题目描述
给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
输入输出样例
输入是一个数组，数组由多个长度固定为2 的数组组成，表示区间的开始和结尾。输出一个
整数，表示需要移除的区间数量。
Input: [[1,2], [2,4], [1,3]]
Output: 1
在这个样例中，我们可以移除区间[1,3]，使得剩余的区间[[1,2], [2,4]] 互不重叠。
题解
在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间
就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区
间。具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选
择的区间不重叠的区间。我们这里使用C++ 的Lambda，结合std::sort() 函数进行自定义排
序。在样例中，排序后的数组为[[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间
[1,2]；由于[1,3] 与[1,2] 相交，我们跳过该区间；由于[2,4] 与[1,2] 不相交，我们将其保留。因
此最终保留的区间为[[1,2], [2,4]]。
具体代码
"""
执行耗时:248 ms,击败了81.74% 的Python用户
内存消耗:44.6 MB,击败了20.78% 的Python用户
"""
def eraseOverlapIntervals(intervals):
intervals = sorted(intervals, key=lambda x: x[1])
# 将排序后的第一个值取出来
new_erase=intervals[0]
cout=0
for i in intervals[1:]:
if i[0]>=new_erase[1]:
# 说明i在新区间右边
new_erase[1]=i[1]
elif i[1]<=new_erase[0]:
# 说明i在新区间左边
new_erase[0]=i[0]
else:
# 说明i不属于新区间
cout+=1
return cout
"""
执行耗时:228 ms,击败了93.38% 的Python用户
内存消耗:44.6 MB,击败了24.20% 的Python用户
"""
def eraseOverlapIntervals1(intervals):
if not intervals:
return 0
intervals = sorted(intervals, key=lambda x: x[1])
# 将排序后的第一个值取出来
new_erase=intervals[0]
cout=0
pre=new_erase[1]
for i in intervals[1:]:
if i[0]<pre:
cout+=1
else:
pre=i[1]
return cout
605. Can Place Flowers (Easy)
采取什么样的贪心策略，可以种植最多的花朵呢？
本题涉及到最优种花问题，使用贪心算法，每（0，0，0）可以种植一棵（边界除外）
解题技巧，在边界前和后再填充一个数，这样可以解决所有边界出现的特殊情况(如只有一个值等）
具体代码
"""
执行耗时:40 ms,击败了14.53% 的Python用户
内存消耗:13.5 MB,击败了73.31% 的Python用户
"""
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
flowerbed = [0] + flowerbed + [0]
for i in range(1, len(flowerbed) - 1):
if [flowerbed[i - 1], flowerbed[i], flowerbed[i + 1]] == [0, 0, 0]:
n -= 1
flowerbed[i] = 1 # 说明此位置已经种花了
if n > 0:
return False
else:
return True
452. Minimum Number of Arrows to Burst Balloons (Medium)
这道题和题目435 十分类似，但是稍有不同，具体是哪里不同呢？
首先排序，以第一个区间的右边界作为对比，如果下一个区间的左边界比它小，则说明用一支箭可以射中两个区间，否则，两个区间是不重叠的，需要两支箭。
具体代码
"""
执行耗时:212 ms,击败了95.12% 的Python用户
内存消耗:43.2 MB,击败了51.41% 的Python用户
"""
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
points = sorted(points, key=lambda x: x[1])
start_area = points[0][1]
cout = 1
for i in points[1:]:
# 如果后区间的第一个值大于等于标准区域的后一个值，说明是不同箭
# 如果小于则使用一个箭
if i[0] > start_area:
cout += 1
start_area = i[1]
return cout
763. Partition Labels (Medium)
为了满足你的贪心策略，是否需要一些预处理？
注意：
在处理数组前，统计一遍信息（如频率、个数、第一次出现位置、最后一次出现位置等）可
以使题目难度大幅降低。
解题思路：
对于这道题，一个关键点是利用字典key的唯一性来记载一个字母最大的index是几。
然后，遍历字符串并跟它比较，用max函数来康康是边界大还是当前遍历的这个字母的最大index大，
如果当前遍历字母的最大index大，那就说明超过了边界，那就要更新边界，大概就是这个思路。
结合我说的，康康下面的代码哈。
具体代码
# leetcode submit region begin(Prohibit modification and deletion)
# 解法1
"""
执行耗时:24 ms,击败了66.78% 的Python用户
内存消耗:12.9 MB,击败了81.82% 的Python用户
"""
class Solution(object):
def partitionLabels(self, s):
"""
:type s: str
:rtype: List[int]
"""
# 使用贪心的思想寻找每个片段可能的最小结束下标
last = [0] * 26
for i, ch in enumerate(s):
last[ord(ch) - ord("a")] = i
# print(last)
partition = list()
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ord(ch) - ord("a")])
# 由于每个片段访问结束的标志是访问到下标 end，因此对于每个片段，
# 可以保证当前片段中的每个字母都一定在当前片段中，不可能出现在其他片段，
# 可以保证同一个字母只会出现在同一个片段。
if i == end:
partition.append(end - start + 1)
start = end + 1
return partition
# leetcode submit region end(Prohibit modification and deletion)
# 解法2
"""
执行耗时:20 ms,击败了88.11% 的Python用户
内存消耗:12.9 MB,击败了86.01% 的Python用户
"""
class Solution(object):
def partitionLabels(self, s):
"""
:type s: str
:rtype: List[int]
"""
# 首先找到每个元素出现的最后位置,字典的形式，通过元素找到下标
last = {c: i for i, c in enumerate(s)}
# 保存字符串的长度
partition = list()
# 设置区间
start = end = 0
# 开始遍历元素"ababcbacadefegdehijhklij"
for i, ch in enumerate(s):
# 设置尾部
end = max(end, last[ch])
# 当区间里所有元素都遍历过
if i == end:
partition.append(end - start + 1)
start = end + 1
return partition
# leetcode submit region end(Prohibit modification and deletion)
122. Best Time to Buy and Sell Stock II (Medium)
股票交易题型里比较简单的题目，在不限制交易次数的情况下，怎样可以获得最大利润呢？
题目描述：
输入: prices = [7,1,5,3,6,4]
输出: 7 意思是：5-1+6-3=7
解题思路：
题目允许可以多次买卖，因此可以当天买进当天卖出或者是当天卖出当天买进。因此只要后一天的价格比前一天的价格高，就可以进行买卖。即设置一个变量，初始化为0，当后一天的价格比前一天的价格高时，变量累加两天价格的差值。
具体代码
# leetcode submit region begin(Prohibit modification and deletion)
"""
执行耗时:20 ms,击败了74.41% 的Python用户
内存消耗:13.7 MB,击败了89.73% 的Python用户
"""
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
minprice = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
minprice += prices[i] - prices[i - 1]
return minprice
# leetcode submit region end(Prohibit modification and deletion)
406. Queue Reconstruction by Height (Medium)
温馨提示，这道题可能同时需要排序和插入操作。
题目例子
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
题目解释
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
题目思路
- 分体题意：身高较高的同学我们先做插入操作，然后身高矮的同学按照k为索引，插入k位置上它前面肯定有k个高个子
- 排序规则：先按照身高降序排序，然后按照比高个数k升序排序
- 等排序遍历一遍之后，还有人没有落在最终的位置，我们按照他的k值作为索引插入
具体代码
# leetcode submit region begin(Prohibit modification and deletion)
"""
执行耗时:24 ms,击败了91.45% 的Python用户
内存消耗:13.5 MB,击败了82.66% 的Python用户
"""
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
# 身高越大在前面，身高相同则人数越少在前面-->第一个元素降序排序，第二个升序排序
people = sorted(people, key=lambda x: (-x[0], x[1]))
re = []
# 根据前面身高大于或等于自己身高的个数进行插入
for s in people:
re.insert(s[1], s)
return re
# leetcode submit region end(Prohibit modification and deletion)
665. Non-decreasing Array (Easy)
需要仔细思考你的贪心策略在各种情况下，是否仍然是最优解。
题目描述
给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
题目实例
示例 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
解法思路
遍历一遍，遍历的过程中可能会遇到两种情况需要修改，3 4 2和1 4 2，当遇到3 4 2这种情况时，需要把2改成4；当遇到1 4 2时，需要把4改成1或2。每遇到一次nums[i]>nums[i+1]时，就需要改一次，计数器加1，计数器大于1时则返回false。
具体代码
# leetcode submit region begin(Prohibit modification and deletion)
"""
执行耗时:32 ms,击败了48.24% 的Python用户
内存消耗:13.8 MB,击败了80.59% 的Python用户
"""
class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
cout = 0
for i in range(len(nums) - 1):
if nums[i + 1] < nums[i]:
# 则为递减
cout += 1
if cout > 1:
return False
if i - 1 >= 0:
# 针对342 将2改为4
if nums[i - 1] > nums[i + 1]:
nums[i + 1] = nums[i]
else:
# 针对142 将4改为1或者2
nums[i] = nums[i + 1]
return True
# leetcode submit region end(Prohibit modification and deletion)
