力扣--动态规划413.等差数列划分

news/2024/6/16 11:49:47 标签: leetcode, 动态规划, 算法, 数据结构, c++, c语言

思路分析 :

  1. 开始时判断输入向量的大小是否小于等于2,若是,则返回0,因为少于3个元素不可能形成等差数列。
  2. 初始化一个大小为n的动态规划数组dp,用于存储以每个位置为结尾的等差数列的数量。
  3. 初始化一个变量result用于存储最终的结果,表示整个向量中的等差数列总数。
  4. 从第三个元素(索引2)开始遍历输入向量。
  5. 对于每个元素,检查它与前两个元素是否构成等差数列。
  6. 如果是等差数列,更新动态规划数组dp,并将当前位置的数量添加到result中。
  7. 最终返回result,即等差数列的总数量。
#include <vector>

class Solution {
public:
    int numberOfArithmeticSlices(std::vector<int>& nums) {
        // 获取输入向量的大小
        int n = nums.size();
        
        // 如果大小小于等于2,则没有等差数列
        if (n <= 2)
            return 0;
        
        // 初始化一个动态规划(DP)数组,用于存储以每个位置为结尾的等差数列的数量
        std::vector<int> dp(n, 0);
        
        // 初始化一个变量,用于存储最终的结果
        int result = 0;
        
        // 从第三个元素(索引2)开始遍历输入向量
        for (int i = 2; i < n; i++) {
            // 检查当前三个连续的元素是否构成等差数列
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                // 如果是,更新DP数组,并将数量添加到结果中
                dp[i] = dp[i - 1] + 1;
                result += dp[i];
            }
        }
        
        // 返回最终结果,表示整个向量中的等差数列总数
        return result;
    }
};


http://www.niftyadmin.cn/n/5408300.html

相关文章

ES入门六:Suggesters Api实践

都是负担在很多app上&#xff0c;当我们输入某些内容时候&#xff0c;它会立即做一些补全操作&#xff0c;如果我想实现上述的需求&#xff0c;我们就可以使用ES提供的Suggesters Api。那Suggesters是如何做到的那&#xff1f;简单来说&#xff0c;Suggesters会将输入的文本拆分…

进程间通信---管道题目练习

实现AB进程对话。 A进程发送一句话后&#xff0c;B进程接收到打印。然后B进程发送一句话&#xff0c;A进程接收后打印 重复上述步骤。直到AB接收或者发送完quit后&#xff0c;结束AB进程 A进程 #include <stdio.h> #include <sys/types.h> #include <sys/stat.…

【C++】继续学习 string类 吧

开始使用 string类 吧 1 继续学习1.1 扩容机制1.2 string类对象的访问及遍历操作1.3 string类对象的修改操作1.4 其他一些成员函数 2 实践解决问题&#xff1a;Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;&#xff01;&#xff01;下一篇文章见&…

【书生·浦语大模型实战营】第5节 课后作业

LMDeploy 的量化和部署 0. 课程链接1. 课后作业1.1 基础作业1.2 进阶作业&#xff08;可选做&#xff09; 0. 课程链接 链接&#xff1a;https://github.com/InternLM/tutorial/blob/main/lmdeploy/lmdeploy.md 1. 课后作业 1.1 基础作业 使用 LMDeploy 以本地对话、网页Gra…

适用于ZigBee应用的JN5168/001K、JN5188HN、JN5188THN/001Z、JN5189THN超低功耗射频微控制器MCU

一、JN5168/001K 适用于ZigBee应用的超低功耗、高性能无线微控制器 JN5168是超低功耗、高性能无线微控制器&#xff0c;适用于ZigBee应用&#xff0c;它具有256kB嵌入式闪存、32 kB RAM&#xff0c;无需外部存储器即可进行OTA升级。32位RISC处理器可通过不同宽度指令、多级指令…

第十五届蓝桥杯软件赛模拟赛第三期(c++,python,java通用)

注&#xff1a;1.填空题用最简单的方式&#xff08;暴力递归或枚举&#xff09;得出答案即可。 2.编程题若无思路可用暴力递归或枚举也能拿到不少的分数。 第一题 【问题描述】 请问 2023 有多少个约数&#xff1f;即有多少个正整数&#xff0c;使得 2023 是这个正整数的整数倍…

Mybatis:Oracle批量新增、批量修改

Oracle批量新增 1、创建 SEQUENCE &#xff0c;用于自增主键 CREATE SEQUENCE TEST_SEQminvalue 1maxvalue 9999999999999999999start with 1increment by 1cache 100;2、创建实体类&#xff0c;用于存数据 Data Accessors(chain true) public class Student {/*** 主键(自…

安装算法依赖时版本报错,依赖之间对应版本

困惑了很久&#xff0c;毕竟不是计算机专业专业出身&#xff0c;才知道安装深度学习算法各个依赖之间是有版本对应关系的。 &#xff08;本文使我随笔记录&#xff0c;无价值&#xff09; 比如&#xff1a; 再比如&#xff1a; 由于我第一步安装cuda时就和其他博主不一致&…