首页 > 编程语言 >C++算法第十六天

C++算法第十六天

时间:2025-01-19 09:28:18浏览次数:3  
标签:第十六 arr 题目 nums int C++ 算法 vector dp

本篇文章我们继续学习动态规划

第一题

题目链接

978. 最长湍流子数组 - 力扣(LeetCode)

题目解析

从上图可见其实有三个状态

代码原理

注意:我们在分析题目的时候分析出来的是三个状态,分别是上升、下降、平坦,但是不一定要定义三个状态表示,一个不够加一个,直到可以解决这道题为止

代码编写

class Solution {

public:

    int maxTurbulenceSize(vector<int>& arr) {

        int n = arr.size();

        vector<int> f(n, 1);

        auto g = f;

        int ret = 1;

        for(int i = 1; i < n; i++)

        {

            if(arr[i] > arr[i - 1])f[i] = g[i - 1] + 1;

            else if(arr[i] < arr[i - 1])g[i] = f[i - 1] + 1;

            ret = max(ret, max(f[i], g[i]));

        }

        return ret;

    }

};

第二题

题目链接

413. 等差数列划分 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    int numberOfArithmeticSlices(vector<int>& nums) {

        int n = nums.size();

        vector<int> dp(n);

        int count = 0;

        for(int i = 2; i < n; i++)

        {

            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]? dp[i - 1] + 1:0;

            count += dp[i];

        }

        return count;

    }

};

第三题

题目链接

139. 单词拆分 - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    bool wordBreak(string s, vector<string>& wordDict) {

        unordered_set<string> hash;

        for(auto cur: wordDict) hash.insert(cur);

        int n = s.size();

        vector<bool>dp(n + 1);

        dp[0] = true;

        s = ' ' + s;//保证字符串的长度与dp表的长度一致

        for(int i = 1; i <= n; i++)

        {

            for(int j = i; j >= 1; j--)

            {

                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))

                {

                    dp[i] = true;

                    break;

                }

            }

        }

        return dp[n];

    }

};

本篇文章的内容就先到这里,我们下期文章再见!!!

记得一键三联哦!!!

标签:第十六,arr,题目,nums,int,C++,算法,vector,dp
From: https://blog.csdn.net/2302_80418176/article/details/145181780

相关文章

  • 三轴云台之姿态融合算法
       三轴云台的姿态融合算法是一种将来自不同传感器的数据进行融合,以获取更准确、更稳定的姿态信息的算法。这种算法通常应用于无人机、摄影设备、机器视觉等领域,以确保设备在各种运动状态下都能保持稳定。一、基本原理   三轴云台通过集成的3轴陀螺仪和3轴加速度计......
  • 2024dsfz集训Day1:贪心算法
    DAY1:贪心算法a经典模型:硬币问题:找零钱问题:有\(100\)元、\(50\)元、\(20\)元、\(10\)元、\(5\)元和\(1\)元这些面值的钱求凑出\(......
  • 使用PythonDEAP库实现简单遗传算法
    ​本人博客食用体验更佳哦DEAP(DistributedEvolutionaryAlgorithmsinPython)是一个用于快速原型设计和实验的进化计算框架。它支持多种进化算法,包括遗传算法、遗传编程、进化策略、粒子群优化等。DEAP的设计目标是灵活性和易用性,使得研究人员和开发者能够轻松地实现和测试各......
  • LRU算法的应用
    13.LRU算法的应用题目关于用户信息的需求假定在一个复杂的系统中,需要抽象出一个用户系统,提供给其他子系统使用,该如何实现。子系统对用户信息的查询频率很高,要注意性能问题。用户信息是存储在数据库里的,但是对于查询频率高的数据,不能每一次请求时都去查询数据库。思路哈希表......
  • 最大流问题:增广路与 Edmonds-Karp 算法
    最大流问题是其中一个经典的图论问题,其目标是在一个流网络中计算从源点到汇点的最大流量。流网络由节点和边组成,每条边都有一个容量,表示该边所能承载的最大流量。最大流问题通常来说,最大流问题仅在有向图上考虑,允许成环,且不考虑重边和自环。在数学上,流网络可以表示为一个有向图......
  • 202312 青少年软件编程等级考试C/C++ 二级真题答案及解析(电子学会)
    第1题统计指定范围里的数给定一个数的序列S,以及一个区间[L,R],求序列中介于该区间的数的个数,即序列中大于等于L且小于等于R的数的个数。时间限制:1000内存限制:65536输入第一行1个整数n,表示序列的长度。(0<n≤10000) 第二行n个正整数,表示序列里的每一个数,每个数小于等......
  • 区间合并(C++模板)
    //区间合并(模板)#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<int,int>PA;vector<PA>segs;intn;intHebing(vector<PA>&segs){ vector<PA>res; sort(segs.begin(),......
  • 保姆级解析雪花算法原理,看完必懂!
    引言最近发现项目里主键id生成算法很短小精悍,遂深入看了下,还蛮有意思,在此分享一下,源码如下。privatestaticSpinLockmLock=newSpinLock();privatestaticvolatileintrotateId=0;privatestaticvolatilelongtimeId=0;privatestaticintnodeI......
  • 机器学习算法深度解析与实践案例:以随机森林为例
    机器学习算法深度解析与实践案例:以随机森林为例在当今大数据驱动的时代,机器学习作为人工智能的一个核心分支,正以前所未有的速度改变着各行各业。从金融风控到医疗健康,从自动驾驶到智能推荐系统,机器学习算法的应用无处不在。本文将深入探讨一种广泛应用于分类和回归任务的强......
  • 七大排序算法
    文章目录排序的概念及引用1.插入排序2.希尔排序(缩小增量排序)3.选择排序4.堆排序5.冒泡排序6.快速排序7.归并排序8.代码排序部分的测试9.代码加效果大致测试时间(仅供参考)排序的概念及引用排序:将数据按照特定的规律排成递增或递减的操作稳定性:例如arr数组中arr[i......