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.
提示：
- 1 <= g.length <= 3 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <= 2^31 - 1
思路：
一开始理解错题意，以为一个小孩子可以拿到多块饼干，原来只能拿一块，审题不仔细。核心思路是，将小孩胃口和饼干从小到大排序，然后将最小的饼干开始尝试分给小朋友，记录小朋友胃口被满足的下标，如果饼干大于等于胃口则下标右移，继续遍历饼干，如果小于胃口无法满足，则下标不变，继续遍历寻找当前饼干值直到可以满足【未被满足胃口的最小胃口小朋友】。
代码实现如下：
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
cur = 0
for i in s:
if cur>=len(g):
return len(g)
#g[cur] -= i
#if g[cur] <= 0:
# cur += 1
if g[cur] <= i:
cur += 1
return cur规范代码：
贪心 大饼干优先（注意这里遍历的是胃口，不是饼干）
class Solution:
def findContentChildren(self, g, s):
g.sort() # 将孩子的贪心因子排序
s.sort() # 将饼干的尺寸排序
index = len(s) - 1 # 饼干数组的下标，从最后一个饼干开始
result = 0 # 满足孩子的数量
for i in range(len(g)-1, -1, -1): # 遍历胃口，从最后一个孩子开始
if index >= 0 and s[index] >= g[i]: # 遍历饼干
result += 1
index -= 1
return result376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
- 输入: [1,7,4,9,2,5]
- 输出: 6
- 解释: 整个序列均为摆动序列。
示例 2:
- 输入: [1,17,5,10,13,15,10,5,16,8]
- 输出: 7
- 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
- 输入: [1,2,3,4,5,6,7,8,9]
- 输出: 2
思路：
核心是当遍历的方向发生改变的时候记录峰值，产生一个峰值则res++，原本设置了cur记录最近一个产生峰值的位置，但发现并不需要关注峰值位置，所以这部分可以去除。重点在于对方向的判断，如果是初始状态，产生上升或是下降时需要色湖之方向。之后：直线（nums[i+1]==nums[i])，直接进入下一个节点，无需操作；如果方向相同（前后两数差值和当前方向相乘为正，根据正负关系可知：正正得正，负负得负），继续寻找下一个点，不做操作。如果方向相反（前后两数差值为负），产生峰值，记录结果+1。
初始代码如下：
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
#cur = 0 # cur记录上一个峰值点
res = 1
direction = 0 # 方向初始为0 向上为1 向下为-1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]: # 取横线的最右点为峰值
#cur += 1
continue
elif direction == 0: # 初始情况
if nums[i] > nums[i-1]:
direction = 1
else:
direction = -1
#cur = i
res += 1
else:
if (nums[i]-nums[i-1]) * direction < 0: # 说明与当前方向反向，产生峰值，改变方向
direction *= -1
res += 1
#cur += 1
return res规范代码：（对于个人而言，以下方法不适合我自己，个人感觉以上我自己想的思路会更适合自己也更容易理解，以下仅做记录）
贪心（版本一）
class Solution:
def wiggleMaxLength(self, nums):
if len(nums) <= 1:
return len(nums) # 如果数组长度为0或1，则返回数组长度
curDiff = 0 # 当前一对元素的差值
preDiff = 0 # 前一对元素的差值
result = 1 # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）
for i in range(len(nums) - 1):
curDiff = nums[i + 1] - nums[i] # 计算下一个元素与当前元素的差值
# 如果遇到一个峰值
if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
result += 1 # 峰值个数加1
preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiff
return result # 返回最长摆动子序列的长度贪心（版本二）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums) # 如果数组长度为0或1，则返回数组长度
preDiff,curDiff ,result = 0,0,1 #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度
for i in range(len(nums) - 1):
curDiff = nums[i + 1] - nums[i]
if curDiff * preDiff <= 0 and curDiff !=0: #差值为0时，不算摆动
result += 1
preDiff = curDiff #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值
return result动态规划（版本一）
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
# 0 i 作为波峰的最大长度
# 1 i 作为波谷的最大长度
# dp是一个列表，列表中每个元素是长度为 2 的列表
dp = []
for i in range(len(nums)):
# 初始为[1, 1]
dp.append([1, 1])
for j in range(i):
# nums[i] 为波谷
if nums[j] > nums[i]:
dp[i][1] = max(dp[i][1], dp[j][0] + 1)
# nums[i] 为波峰
if nums[j] < nums[i]:
dp[i][0] = max(dp[i][0], dp[j][1] + 1)
return max(dp[-1][0], dp[-1][1])动态规划（版本二）
class Solution:
def wiggleMaxLength(self, nums):
dp = [[0, 0] for _ in range(len(nums))] # 创建二维dp数组，用于记录摆动序列的最大长度
dp[0][0] = dp[0][1] = 1 # 初始条件，序列中的第一个元素默认为峰值，最小长度为1
for i in range(1, len(nums)):
dp[i][0] = dp[i][1] = 1 # 初始化当前位置的dp值为1
for j in range(i):
if nums[j] > nums[i]:
dp[i][1] = max(dp[i][1], dp[j][0] + 1) # 如果前一个数比当前数大，可以形成一个上升峰值，更新dp[i][1]
for j in range(i):
if nums[j] < nums[i]:
dp[i][0] = max(dp[i][0], dp[j][1] + 1) # 如果前一个数比当前数小，可以形成一个下降峰值，更新dp[i][0]
return max(dp[-1][0], dp[-1][1]) # 返回最大的摆动序列长度53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：
一开始尝试用将数组转化为前缀和数组的方式，用最大前缀和减去最小前缀和来得到最大的中间连续子序列，但发现解答错误。思考了一下可能错的几点：首先，最大前缀和可能出现在最小前缀和之前，这样会导致出错。其次，最大前缀和可能会出现相等的几个，取最靠后的一个有可能可以取得更好的结果，但还是会出错。
附上错误代码以后用于鞭尸自己。。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
cur = 0
while cur < len(nums) and nums[cur] <= 0: # 忽略数组最初的所有负数
cur +=1
if cur == len(nums): # 全非正数，取数组最大值
nums.sort()
return nums[-1]
#newnums = nums[cur:]
newnums = [0] + nums[cur:] # 需要考虑第一个元素的前缀和
max_index = 0
for i in range(1, len(newnums)):
newnums[i] += newnums[i-1]
if newnums[i] >= newnums[max_index]:
max_index = i
min_index = 0
for i in range(max_index+1):
if newnums[i] < newnums[min_index]:
min_index = i
return newnums[max_index] - newnums[min_index]
以上错误思路其实比较接近于代码随想录提供的动态规划，但在更新数值方面我做的不对，附上正确代码供自己对照学习：
class Solution {public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
}
return result;
}};记录一下代码随想录提供的思路：
贪心解法
贪心贪的是哪里呢？
如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
规范代码：
class Solution {public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count;
}
if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}};Python实现如下：
class Solution:
def maxSubArray(self, nums):
result = float('-inf') # 初始化结果为负无穷大
count = 0
for i in range(len(nums)):
count += nums[i]
if count > result: # 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count
if count <= 0: # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
count = 0
return result而以上办法和Kadane算法类似，在这做一个补充（AI提供）
Kadane算法是一种用于解决最大子数组和问题的有效算法。它的核心思想是遍历数组，同时维护两个变量：一个用于记录当前子数组的最大和（max_current），另一个用于记录迄今为止遇到的最大子数组和（max_global）。以下是Kadane算法的具体实现步骤和代码示例：
实现步骤：
初始化：将max_current和max_global都初始化为数组的第一个元素。
遍历数组：从数组的第二个元素开始遍历，对于每个元素：
更新max_current为当前元素和max_current加上当前元素中的较大者。这一步是关键，它意味着我们可以选择从当前位置开始一个新的子数组，或者将当前元素添加到之前的子数组中。
如果max_current大于max_global，则更新max_global。
返回结果：遍历结束后，max_global就是整个数组的最大子数组和。
代码如下：
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 检查数组是否为空
if not nums:
return 0
# 初始化max_current和max_global
max_current = max_global = nums[0]
# 遍历数组，从第二个元素开始
for num in nums[1:]:
# 更新max_current为当前元素和max_current加上当前元素中的较大者
max_current = max(num, max_current + num)
# 如果max_current大于max_global，则更新max_global
if max_current > max_global:
max_global = max_current
# 返回最大子数组和
return max_global