2024-11-28
897 字
3 分钟
摆动序列
题目
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
例如，[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]
输
2024-11-28
967 字
3 分钟
贪心算法-分发饼干
什么是贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如有一堆不同数额的钞票，每次只能拿一张，怎么拿能取得最大数额的钞票。
方法：将钞票从大到小进行排序，每次都拿走当前堆里最大面额的钞票，即可在指定拿取次数中获得最大数额的钞票。
例如：[100, 100, 50, 20, 50, 1, 10]
排序后为：[100, 100, 50, 50, 20, 10, 1]
依次取数组中的最大值进行累加
取完指定次数后，累加值即为最优解
在这个过程中，每次取最大面额的钞票为局部最优，通过每次获得局部最优得到的结果即为全局最优。
注意：贪心算法并没有固定套路，也没有固
2024-11-27
483 字
2 分钟
修剪二叉搜索树
题目
给定一个二叉搜索树，同时给定最小边界low和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中(high>=low) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例1
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例2
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
《代码随想录》算法视频公开课
力扣题目链接
思路
题目所给二叉树为搜索二
