力扣练习题（2024/4/21）

news/2024/9/24 16:15:06/

      贪心算法是一种在每一步选择中都做出最佳选择的算法方法。它以尽量减少当前问题的复杂性为目标，在每一步选择中尽可能取得最佳结果。尽管贪心算法不能保证总是获得最优解，但在许多情况下，它是解决问题的高效方法。

1分发饼干

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

思路：

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

  1. 首先，对孩子的胃口数组和饼干数组进行排序，这样可以更容易地进行匹配。

  2. 接着，从胃口最大的孩子开始向前遍历，同时从饼干数组的最后一个位置向前匹配。这样做的原因是贪心地选择最大的孩子和最大的饼干进行匹配。

  3. 在遍历的过程中，如果当前的饼干满足当前孩子的胃口，则将结果计数加一，并将饼干的下标向前移动一位。

  4. 最终返回结果，即能满足的孩子数量。

代码：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 将孩子数组和饼干数组按照从小到大排序sort(g.begin(), g.end()); // 按照孩子的胃口排序sort(s.begin(), s.end()); // 按照饼干的大小排序int index = s.size() - 1; // 饼干数组的下标int result = 0; // 结果，能满足孩子的数量// 从胃口最大的孩子开始匹配饼干for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口// 如果还有饼干可用且当前饼干满足当前孩子的胃口if (index >= 0 && s[index] >= g[i]) { // 遍历饼干result++; // 满足一个孩子index--; // 使用了一个饼干，下标减一}}return result; // 返回满足孩子的数量}
};

2 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

思路：

解题关键点

关键在于识别何时一个数的加入可以形成摆动序列中的一个新的"峰"或"谷"。

分析步骤

  1. 初始化变量：

    • curDiff 记录当前差值（当前元素与下一个元素的差）。
    • preDiff 记录前一个差值，用于与当前差值比较。
    • result 初始化为1，至少有一个元素时，我们认为摆动序列至少为1。

  2. 遍历序列计算差值：

    • 对于数组中的每个元素（除最后一个），计算与下一个元素的差值 curDiff。
    • 这个差值用来确定当前元素的位置是在上升趋势还是下降趋势。

  3. 判断摆动条件：

    • 当 preDiff <= 0 && curDiff > 0 时，说明之前是下降趋势或持平，现在转为上升，当前元素形成一个谷。
    • 当 preDiff >= 0 && curDiff < 0 时，说明之前是上升趋势或持平，现在转为下降，当前元素形成一个峰。
    • 只有在这两种情况下，result 才会增加，因为我们找到了一个摆动。

  4. 更新 preDiff：

    • 只有在确定当前差值确实形成了一个新的摆动时，才更新 preDiff。这是为了确保不遗漏任何一个可能的摆动点。

特殊情况处理

  • 如果数组元素全相同或者整体趋势一致（只上升或只下降），摆动序列的长度将为1，因为没有真正的摆动发生。

代码：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size(); // 如果数组长度小于等于1，直接返回数组长度int curDiff = 0; // 当前一对差值int preDiff = 0; // 前一对差值int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值for (int i = 0; i < nums.size() - 1; i++) { // 遍历数组curDiff = nums[i + 1] - nums[i]; // 当前一对差值// 出现峰值if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {result++; // 峰值个数加一preDiff = curDiff; // 更新前一对差值}}return result; // 返回峰值个数}
};

3 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组

是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

贪心算法思路：

贪心算法是一种通过每一步的局部最优选择来达到全局最优解的算法。在解决最大子数组和问题时，贪心算法的思路是尝试寻找以每个元素结尾的所有子数组中和最大的那个子数组。具体来说，算法每次遍历数组中的一个元素，并更新两个变量：当前子数组的和 count 和最大子数组和 result。在遍历的过程中，如果当前子数组的和 count 大于 result，就更新 result 为 count，表示发现了一个更大的子数组和。如果 count 小于等于0，意味着当前子数组对最终结果没有正面贡献，因此将 count 重置为0，重新开始计算下一个子数组的和。

代码：

class Solution{
public:int maxSubArray(std::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; // 如果当前子数组和小于等于0，说明对结果无贡献，将当前和重置为0}}return result; // 返回最大和}
};

4. 买卖股票的最佳时机 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 。总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

贪心算法思路：

  1. 寻找价格上涨的区间：

    • 从第二天开始遍历价格数组，比较当前价格与前一天价格。
    • 如果当前价格高于前一天价格，则将当前价格区间标记为上涨区间的一部分。
    • 如果当前价格低于等于前一天价格，则结束上涨区间，将上涨区间的利润加入总利润中，并将下一个区间的起始点设为当前价格。

  2. 计算利润：

    • 对于每个上涨区间，利润等于区间终点的价格减去起始点的价格。
    • 如果某个上涨区间的利润为正，则将其加入总利润中。

  3. 累加利润：

    • 将每个上涨区间的利润累加起来，得到最大利润。

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

如图：

股票价格71510364
每天利润-645-73-2
每天只收集正利润4+5+3=12

代码：

#include <vector>
#include <algorithm> // 用于使用 max 函数class Solution {
public:int maxProfit(std::vector<int>& prices) {int result = 0; // 初始化最大利润为0for (int i = 1; i < prices.size(); i++) {// 计算当前交易的利润，如果利润为负数，则取0，表示不进行交易result += std::max(prices[i] - prices[i - 1], 0);}return result; // 返回最大利润}
};

5 指定日期的产品价格

产品数据表: Products

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| product_id    | int     |
| new_price     | int     |
| change_date   | date    |
+---------------+---------+
(product_id, change_date) 是此表的主键（具有唯一值的列组合）。
这张表的每一行分别记录了 某产品 在某个日期 更改后 的新价格。

编写一个解决方案，找出在 2019-08-16 时全部产品的价格，假设所有产品在修改前的价格都是 10 。

以 任意顺序 返回结果表。

结果格式如下例所示。

示例 1:

输入：
Products 表:
+------------+-----------+-------------+
| product_id | new_price | change_date |
+------------+-----------+-------------+
| 1          | 20        | 2019-08-14  |
| 2          | 50        | 2019-08-14  |
| 1          | 30        | 2019-08-15  |
| 1          | 35        | 2019-08-16  |
| 2          | 65        | 2019-08-17  |
| 3          | 20        | 2019-08-18  |
+------------+-----------+-------------+
输出：
+------------+-------+
| product_id | price |
+------------+-------+
| 2          | 50    |
| 1          | 35    |
| 3          | 10    |
+------------+-------+

思路：

  1. 第一个部分：选择在2019年8月16日之后有价格变动的产品：

    • 使用select语句选择产品ID和价格。价格设为10作为一个默认值。
    • 使用group by语句按产品ID进行分组。
    • 使用having子句筛选出变动日期在2019年8月16日之后的记录。
    • 结果是每个产品最早的价格变动记录，并将价格设为10。

  2. 第二个部分：选择在2019年8月16日之前最后一次价格变动的产品：

    • 使用子查询找到在2019年8月16日之前最后一次价格变动的产品及其最新价格。
    • 子查询中，先筛选出变动日期在2019年8月16日之前的记录，然后按产品ID分组，并选取每组中的最大变动日期。
    • 主查询中，根据子查询结果选择对应产品的最新价格。

通过以上两个部分的联合查询，可以得到在指定日期前后的产品价格变动情况，其中在指定日期之后没有变动的产品价格设为10，而在指定日期之前有变动的产品则显示最新价格。

代码：

-- 选择在2019年8月16日之后有价格变动的产品，并取每个产品最早的变动日期，价格设为10
select product_id,  -- 选择产品ID10 as price  -- 将价格设为10
from products  -- 选择产品表
group by product_id  -- 按产品ID分组
having min(change_date) > '2019-08-16'  -- 筛选出变动日期在2019年8月16日之后的记录union -- 选择在2019年8月16日之前最后一次价格变动的产品，并取最新价格
select product_id,  -- 选择产品IDnew_price as price  -- 取最新价格
from products  -- 选择产品表
where (product_id, change_date) in (-- 子查询：选择在2019年8月16日之前最后一次价格变动的产品select product_id,  -- 选择产品IDmax(change_date)  -- 取最大的变动日期from products  -- 选择产品表where change_date <= '2019-08-16'  -- 筛选出变动日期在2019年8月16日之前的记录group by product_id  -- 按产品ID分组)


http://www.ppmy.cn/news/1428747.html

相关文章

VUE - pdfmake的中文字库支持

VUE - pdfmake的中文字库支持

前端VUE导出pdf。 jspdf这个插件对中文支持不够友好&#xff0c;用html的canvas转图片后还是很模糊。最终选用了pdfmake插件。 使用 1.引入pdf npm install pdfmake --save 2.页面import import pdfMake from pdfmake/build/pdfmake; import pdfFonts from pdfmake/build…
阅读更多...
黑马鸿蒙学习5：LIST容器

黑马鸿蒙学习5：LIST容器

LIST容器&#xff0c;其实就是如果FOREACH容器展示不全的话&#xff0c;会自动有滚动条了。要注意的是&#xff0c;LIST中必须有固定的listitem这个项&#xff0c;而且列表里面只能包含一个根组件。 必须把ROW容器放到listitem中&#xff0c;如下&#xff1a;
阅读更多...
基于单目相机的标靶三维定位——编程实现

基于单目相机的标靶三维定位——编程实现

上一章内容中我们描述了基于单目相机实现标靶三维定位的原理，关键步骤为1）计算得到相机的内参和畸变系数；2）计算得到标靶角点的世界坐标和像素坐标；3）计算标靶坐标系到相机坐标系的变换矩阵。 第一点我们通过相机标定得到；第二点的核心功能我们可以借助cv::findChessboa…
阅读更多...
vuex.esm.js:497 [vuex] unknown action type: userModule/ClearStorage

vuex.esm.js:497 [vuex] unknown action type: userModule/ClearStorage

vuex.esm.js:497 [vuex] unknown action type: userModule/ClearStorage 错误解释&#xff1a; 这个错误表明在Vuex中尝试调用一个名为userModule/ClearStorage的action&#xff0c;但是在该模块的actions定义中没有找到这个名字的函数。这可能是由于拼写错误、未定义的actio…
阅读更多...
英语写作中“原理”“准则”principle、norm、criterion、rule等的用法

英语写作中“原理”“准则”principle、norm、criterion、rule等的用法

一、principle、rule一般指科学原理和法则&#xff0c;例如&#xff1a; Newton’ laws of motion are the basic principle of mechanics. &#xff08;牛顿运动定律是力学的基本原理。&#xff09; Maxwell’ equations are the rule electromagnetic fields and electroma…
阅读更多...
就业班 第三阶段（ansible） 2401--4.16 day2 ansible2 剧本+角色

就业班 第三阶段（ansible） 2401--4.16 day2 ansible2 剧本+角色

六、Ansible playbook 简介 playbook 是 ansible 用于配置&#xff0c;部署&#xff0c;和管理被控节点的剧本。 　　通过 playbook 的详细描述&#xff0c;执行其中的一系列 tasks &#xff0c;可以让远端主机达到预期的状态。playbook 就像 Ansible 控制器给被控节点列出的的…
阅读更多...
分布移位下用于泛化的泛化的自监督测试时训练

分布移位下用于泛化的泛化的自监督测试时训练

Test-Time Training with Self-Supervision for Generalization under Distribution Shifts 论文链接 https://arxiv.org/abs/1909.13231 代码链接 Test-Time Training Project Website 发表于ICML2020 机构&#xff1a; UC Berkeley&#xff0c; UC San Diego 这张文章里的…
阅读更多...
探索AI大模型：理论、技术与应用

探索AI大模型：理论、技术与应用

引言 近年来&#xff0c;随着深度学习技术的迅猛发展&#xff0c;AI大模型已经成为人工智能领域的重要研究方向和热点话题。AI大模型&#xff0c;指的是拥有巨大参数规模和强大学习能力的神经网络模型&#xff0c;如BERT、GPT等&#xff0c;这些模型在自然语言处理、计算机视觉…
阅读更多...
最新文章

Copyright @ 2022~2023