455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子?
i，都有一个胃口值?g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干?j，都有一个尺寸?s[j]?。如果?s[j]?>= g[i]，我们可以将这个饼干?j?分配给孩子?i?，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例?1:
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。
示例?2:
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
代码：
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
"""
对2个数组进行排序，将大尺寸的饼干优先分配给大孩子
"""
g = sorted(g)
s = sorted(s)
s_i = len(s)-1
g_i = len(g)-1
child_num = 0
while s_i >= 0 and g_i >= 0:
#当前最大值满足最大胃口的孩子，便把饼干分配给他
if g[g_i] <= s[s_i]:
child_num += 1
#同时向前移动
s_i -= 1
g_i -= 1
#当前饼干太小了，看下一个孩子的胃口是否满足
else:
g_i -= 1
return child_num
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，?[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3)?是正负交替出现的。
相反，[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：?输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
代码：
"""
二：采用贪心的方法求解
"""
lens = len(nums)
if lens <= 1:
return lens
#当前元素与上一个元素的差值
curDiff = 0
#上一个元素与上上个元素的差值------相当[2,5]是[2,2,5]的坡度就是0
preDiff = 0
#记录峰值的个数,默认最后一个元素是峰值
res = 1
for i in range(lens - 1):
curDiff = nums[i+1] - nums[i]
if (curDiff > 0 and preDiff <= 0) or (curDiff < 0 and preDiff >= 0):
res += 1
#这个地方比较巧妙，如果当前节点是峰值，那么当前节点和后一个节点的差值
#应该记录下来
preDiff = curDiff
return res
53. 最大子序和
给定一个整数数组?
nums?，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组?[4,-1,2,1] 的和最大，为?6 。示例 2：
输入：nums = [1] 输出：1
代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
lens = len(nums)
max_value = -float("inf")
counts = 0
for i in range(0,lens):
counts += nums[i]
if counts > max_value:
max_value = counts
if counts < 0:
#将当前和赋值为0
counts = 0
return max_value
122. 买卖股票的最佳时机 II
给定一个数组?
prices?，其中?prices[i]?是一支给定股票第?i?天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 ? 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
代码：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""
计算相邻2天的利润
"""
day_nums = len(prices)
now_profit = []
for i in range(0,day_nums-1):
now_profit.append(prices[i+1] - prices[i])
#统计相邻2天的利润为正的和
return sum([v for v in now_profit if v > 0])
55. 跳跃游戏
给定一个非负整数数组?
nums?，你最初位于数组的?第一个下标?。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例?1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
lens = len(nums)
index = 0
cover = 0
now_range = []
while index <= cover:
cover = max(cover,index+nums[index])
if cover >= lens-1:
#可以成功跳跃过去
return True
index += 1
return False
1005. K 次取反后最大化的数组和
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引?
i?并将?A[i]?替换为?-A[i]，然后总共重复这个过程?K?次。（我们可以多次选择同一个索引?i。）以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：A = [4,2,3], K = 1 输出：5 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
?代码：
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
"""
使用贪心：
局部最大值---当前每个元素进行反转，得到该元素的最大值
整体最大值---所有元素对应的nums达到最大值
"""
nums = sorted(nums,key = abs,reverse = True)
for index in range(len(nums)):
if nums[index] < 0 and k > 0:
nums[index] = nums[index]*-1
k -= 1
while k > 0:
nums[-1] = nums[-1]*-1
k -= 1
return sum(nums)134. 加油站
在一条环路上有?N?个加油站，其中第?i?个加油站有汽油?
gas[i]?升。你有一辆油箱容量无限的的汽车，从第?i?个加油站开往第?i+1?个加油站需要消耗汽油?
cost[i]?升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
示例?1:
输入:?
gas ?= [1,2,3,4,5]
cost = [3,4,5,1,2]输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
代码：
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
#若每个加油站的剩余油量的和小于0，那么便不能绕一周
#若大于0，可能可以绕一周
cur_sums = 0
start = 0
rest = []
for i in range(len(gas)):
"""
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，
说明[0, i]区间都不能作为起始位置，起始位
置从i+1算起，再从0计算curSum
"""
rest.append(gas[i] - cost[i])
cur_sums += rest[i]
if cur_sums < 0:
cur_sums = 0
#i+1之后的加油站出发才有机会完成任务
start = i+1
if sum(rest) < 0:
return -1
return start
860. 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为?
5?美元。顾客排队购买你的产品，（按账单?bills?支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付?
5?美元、10?美元或?20?美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付?5?美元。注意，一开始你手头没有任何零钱。
给你一个整数数组?
bills?，其中?bills[i]?是第?i?位顾客付的账。如果你能给每位顾客正确找零，返回?true?，否则返回?false?。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
代码：
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
"""
情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
注意：先后顺序
"""
bags = {5:0,10:0}
for val in bills:
if val == 5:
bags[val] += 1
if val == 10:
bags[5] -= 1
bags[val] += 1
if val == 20:
if bags[10] > 0 and bags[5] > 0:
bags[5] -= 1
bags[10] -= 1
else:
bags[5] -= 3
#若剩下5块与10块的零钱都大于0，那么便返回True
if bags[10] < 0 or bags[5] < 0:
return False
return True
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组?
people?表示队列中一些人的属性（不一定按顺序）。每个?people[i] = [hi, ki]?表示第?i?个人的身高为?hi?，前面?正好?有?ki?个身高大于或等于?hi?的人。请你重新构造并返回输入数组?
people?所表示的队列。返回的队列应该格式化为数组?queue?，其中?queue[j] = [hj, kj]?是队列中第?j?个人的属性（queue[0]?是排在队列前面的人）。
示例 1：
输入：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]] 是重新构造后的队列。
代码：
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (x[0], -x[1]),reverse = True)
que = []
for p in people:
que.insert(p[1], p)
return que
435. 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
代码：
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if len(intervals) == 0:
return 0
"""
先按照intervals左值排序
"""
intervals.sort(key = lambda x:x[1])
cur_right = intervals[0][1]
count = 1
for index in range(1,len(intervals)):
if intervals[index][0] >= cur_right:
count += 1
cur_right = intervals[index][1]
return len(intervals) - count
763. 划分字母区间
字符串?
S?由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
代码：
class Solution:
def partitionLabels(self, s: str) -> List[int]:
keys = set(s)
temp = {}
for key in keys:
temp[key] = 0
for index in range(len(s)):
temp[s[index]] = index
hash = []
for val in s:
hash.append(temp[val])
#找到已经遍历过字符的最大边界
max_len = -1
res = []
left = -1
for i in range(len(s)):
if hash[i] == i and hash[i] >= max_len:
res.append(i-left)
left = i
max_len = max(max_len,hash[i])
return res?
56. 合并区间
以数组?
intervals?表示若干个区间的集合，其中单个区间为?intervals[i] = [starti, endi]?。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
代码：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 0: return intervals
intervals.sort(key=lambda x: x[0])
result = []
result.append(intervals[0])
for i in range(1, len(intervals)):
last = result[-1]
if last[1] >= intervals[i][0]:
result[-1] = [last[0], max(last[1], intervals[i][1])]
else:
result.append(intervals[i])
return result
738. 单调递增的数字
给定一个非负整数?
N，找出小于或等于?N?的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字?
x?和?y?满足?x <= y?时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10 输出: 9
?代码：
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
a = list(str(n))
for i in range(len(a)-1,0,-1):
if int(a[i]) < int(a[i-1]):
a[i-1] = str(int(a[i-1]) - 1)
#从该位置往后都应该是0
a[i:] = '9' * (len(a) - i)
return int("".join(a))
