【OJ】动规练习六

个人主页 : zxctscl
如有转载请先通知

题目

  • 1. 413. 等差数列划分
    • 1.1 分析
    • 1.2 代码
  • 2. 978. 最长湍流子数组
    • 2.1 分析
    • 2.2 代码
  • 3. 139. 单词拆分
    • 3.1 分析
    • 3.2 代码

1. 413. 等差数列划分

在这里插入图片描述

1.1 分析

一、题目解析:
至少有三个元素才能构成等差数列,题目要求返回的是子序列等差数列的个数

二、算法原理:

  1. 状态表示
    以i位置为结尾,找所有子数组中有多少个等差数列
    dp[i]表示以i位置为结尾的所有子数组中有多少个等差数列。

  2. 状态转移方程
    在这里插入图片描述
    子数组是连续的,如果i位置是等差数列的子序列,那么它前面的两个至少也是构成等差数列。

第一种:考虑abc构成等差数列:c-b=b-a
如果abc能构成等差数列,那么以ab结尾的所有的等差数列再加上一个c也是等差数列。
以ab为结尾,也就是以b为结尾,那么以b结尾的所有子数组等差数列就有dp[i-1]个。但是ab就不在这个数列里面,可abc能构成等差数列,但是也多了一种,所以得多加一个1,这里的1是多加了abc这样的一种情况。

第二种:考虑abc不构成等差数列:c-b≠b-a
那么前面的数再多也不能构成等差数列,此时dp[i]=0。

状态转移方程:dp[i]=c-b==b-a?dp[i-1]+1:0

  1. 初始化
    在这里插入图片描述
    因为要三个才能构成等差数列,所以
    dp[0]=0
    dp[1]=0

  2. 填表顺序
    从左往右

  3. 返回值
    题目要求返回的不一定是最后一个位置的值,而是所有子序列等差数列的个数,所以得全部加起来。返回值就是dp表中所以元素的和。
    在这里插入图片描述

1.2 代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
      int n=nums.size();
      vector<int> dp(n);
      if(n<=2)return 0;
      int sum=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;
         sum+=dp[i];
       }
       return sum;
    }
};

2. 978. 最长湍流子数组

在这里插入图片描述

2.1 分析

一、题目解析:
湍流数组意思是相邻两个元素大小一升一降
在这里插入图片描述
像题目给的例子1就是在第二个位置4和第三个位置都是降的就不行2。而到了第七个位置8和第六个位置8是平的没有变化,就不是湍流数组,所以例1的最大湍流数组长度就是5。
在这里插入图片描述
在例2中都是升的,所以最大湍流数组长度就是2。
在这里插入图片描述
在例1中只有一个元素,所以最大湍流数组长度就是1。
在这里插入图片描述

二、算法原理:

  1. 状态表示
    以某一个位置为结尾
    如果以dp[i]表示以i位置为结尾的所以子数组中,最长的湍流数组长度,那么可能会出现三种情况最后一个位置可能会出现下降趋势,也可能是上升趋势,还可以是水平的,一个状态表示不能满足情况,所以得换状态表示。
    **f[i]表示i位置为结尾的所以子数组中,最后呈现“上升”**状态下,最长的湍流数组长度
    **g[i]表示i位置为结尾的所以子数组中,最后呈现“下降”**状态下,最长的湍流数组长度

  2. 状态转移方程
    在f[i]中会出现三种情况,第一种:i-1大于i,这样就不能呈现上升状态,所以i位置自己成为上升状态。第二种:i-1小于i,刚好呈现上升状态,接下来就要i-1位置为结尾成下降状态,就是g[i-1]。第三种,i位置的值和i位置相同,就得自己成为上升状态。
    在这里插入图片描述

在g[i]中会出现两种情况,第一种:i-1小于i,这样就不能呈现下降状态,所以i位置自己成为下降状态。第二种:i-1打于i,刚好呈现下降状态,接下来就要i-1位置为结尾成上升状态,就是f[i-1]。第三种,i位置的值和i位置相同,就得自己成为下降状态。
在这里插入图片描述

  1. 初始化

在f表和g表中最差的情况就是1,所以把表中元素全部初始化为1。这样就减少了很多判断情况。

  1. 填表顺序
    从左往右
    两个表一起填

  2. 返回值
    返回f表和g表中最大的那个
    在这里插入图片描述

2.2 代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n=arr.size();
        vector<int> f(n,1),g(n,1);
       int ret=1;
        for(int i=1;i<n;i++)
        {
            if(arr[i-1]<arr[i])
            {
            f[i]=g[i-1]+1;
            }
            else if(arr[i-1]>arr[i])
            {
            g[i]=f[i-1]+1;
            }
            ret=max(ret,max(f[i],g[i]));
        }
        return ret;
    }
};

3. 139. 单词拆分

在这里插入图片描述

3.1 分析

一、题目解析:
在给的 wordDict 字典里面可以重复使用某一个单词,还没有要求全部使用。
看一下给的例2:s里面给的字符串就可以在wordDict 字典里面找到就返回true。
在这里插入图片描述
例3:第一单词不管是选择cat还是cats最后剩下的og在wordDict 字典里面都没有找到,就返回false。
在这里插入图片描述

二、算法原理:

  1. 状态表示
    以某一个位置为结尾
    dp[i]表示以i位置为结尾的[0,i]区间内的字符串,能否被字典中的单词拼接而成。能被拼接而成就是true,不能就是false。

  2. 状态转移方程
    根据最后一个位置的情况来划分问题:前面那一部分单词,加上最后一个单词,而最后一个单词中的i,只要能确定前面部分能拼接而成,并且最后一个单词在wordDict 字典里面能找到,那么这个字符串就能拼接而成。
    在这里插入图片描述
    那么在设一个变量j来作为左边部分的最后一个下标,左边这个字符串的开始在0,结尾在j-1,这个区间能否作为字典中的单词拼接而成就是dp[j-1],右边这个位置就[j,i]组成的单词是否在字典中就行。左右两种情况都为true的时候就能拼接。
    在这里插入图片描述

  3. 初始化

为了dp[j-1]不越界,就加一个虚拟节点。为了保证后面的填表顺序是正确,那么dp[0]=true。
还得注意下标的映射关系,这里加了一个新节点,那么s表就得加一个辅助字符。

  1. 填表顺序
    从左往右

  2. 返回值
    题目要求返回是s字符串能否被拼接,就是dp[n]。
    在这里插入图片描述

3.2 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> hash;
    for(auto& s: wordDict)hash.insert(s);
     int n=s.size();
     vector<bool>dp(n+1);
     dp[0]=true;
     s=' '+s;
     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];
    }
};/*  */

有问题请指出,大家一起进步!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/516587.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【开发环境】Mac 安装 Visual Studio Code ( VSCode 简介 | 下载 VSCode | 安装 VSCode | 安装中文语言包 )

文章目录 一、Visual Studio Code 简介二、MAC 安装 Visual Studio Code1、下载 Visual Studio Code2、安装 Visual Studio Code3、安装中文语言包4、编辑 html 并运行 一、Visual Studio Code 简介 Visual Studio Code 简称 VSCode , 是 微软 开发的一款 轻量级 / 跨平台 的代…

前视声呐目标识别定位(五)-代码解析之修改声呐参数

前视声呐目标识别定位&#xff08;一&#xff09;-基础知识 前视声呐目标识别定位&#xff08;二&#xff09;-目标识别定位模块 前视声呐目标识别定位&#xff08;三&#xff09;-部署至机器人 前视声呐目标识别定位&#xff08;四&#xff09;-代码解析之启动识别模块 …

arm裸机-1、定时器pwm

时钟配置 我们使用s3c2440&#xff0c;主频12M&#xff0c;查看用户手册 通过锁相环抬升到400MHZ&#xff0c;分成三条通路&#xff0c;通过HHDIVN和PDIVN配置频率比&#xff0c;这个频率比配置手册已经给出。 配置MPLL主频400Mhz&#xff0c; 通过这个公式算出MPLL s、p、m都…

Redis从入门到精通(四)Redis实战(二)商户查询缓存

↑↑↑请在文章头部下载测试项目原代码↑↑↑ 文章目录 前言4.2 商户查询缓存4.2.1 缓存介绍4.2.2 查询商户信息的传统做法4.2.2.1 接口文档4.2.2.2 代码实现4.2.2.3 功能测试 4.2.3 查询商户信息添加Redis缓存4.2.3.1 逻辑分析4.2.3.2 代码实现4.2.3.3 功能测试 4.2.3 数据一致…

动力云客-B站(第一天)

一 项目技术选型及开发工具 前后端分离的项目&#xff08;前端项目 后端项目&#xff09; 前端&#xff1a;Html、CSS、JavaScript、Vue、Axios、Element Plus后端&#xff1a;Spring Boot、Spring Security、MyBatis、MySQL、Redis 相关组件&#xff1a;HiKariCP&#x…

【C++进阶】带你手撕红黑树(红与黑的爱恨厮杀)

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;c大冒险 总有光环在陨落&#xff0c;总有新星在闪烁 引言&#xff1a; 之前我们…

K8S- Deployment 的滚动更新 Rolling Update

滚动更新 这里的更新指的不是更新deployment 本身的属性(label/ replicas)等&#xff0c; 而是更新POD 的container 的版本 更新方法通常有两种 是直接update deployment配置&#xff0c; 注意只有update了template中的内容(与container相关) 才会触发更新用kubectl set ima…

【蓝桥杯】GCD与LCM

一.概述 最大公约数&#xff08;GCD&#xff09;和最小公倍数&#xff08;Least Common Multiple&#xff0c;LCM&#xff09; 在C中&#xff0c;可以使用 std::__gcd(a, b)来计算最大公约数 1.欧几里德算法/辗转相除法 int gcd(int a,int b){return b?gcd(b, a%b):a; } 2…

CATIA软件 焊点坐标(BiW Welding SpotPoint)导出txt文本的操作方法

通常我们客户给的工件是带焊点球的形式&#xff0c;且可导出焊点坐标。如下图所示的焊点位置标识及坐标&#xff0c;即是CATIA中Automotive BiW Fastening模块下的BiW Welding SpotPoint焊点定义。 遇到这样的形式&#xff0c;要导出焊点坐标txt文本&#xff0c;可按如下图片找…

ssm023实验室耗材管理系统设计与实现+jsp

实验室耗材管理系统的设计与实现 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对实验室耗材信息管理混乱&#xff…

深入浅出 -- 系统架构之单体架构和微服务架构的区别

在软件开发中&#xff0c;架构设计是非常重要的一环。架构设计不仅决定了软件系统的性能、可维护性和扩展性&#xff0c;还直接关系到开发成本和项目进度。目前&#xff0c;主流的架构设计模式有两种&#xff0c;一种是单体架构&#xff0c;另一种是微服务架构。本文将详细介绍…

【C语言】从零开始:用C语言实现顺序表

欢迎来CILMY23的博客 本篇主题为 从零开始&#xff1a;用C语言实现顺序表 个人主页&#xff1a;CILMY23-CSDN博客 C语言专栏&#xff1a; http://t.csdnimg.cn/hQ5a9 Python系列专栏&#xff1a;http://t.csdnimg.cn/HqYo8 上一篇C语言博客&#xff1a; http://t.csdnimg.…

pwn学习笔记(7)--堆相关源码

相关源码&#xff1a; 1. chunk 相关源码&#xff1a; ​ 对于用户来说&#xff0c;只需要确保malloc()函数返回的内存不会发生溢出&#xff0c;并且在不用的时候使用free() 函数将其释放&#xff0c;以后也不再做任何操作即可。而对于glibc来说’它要在用户第一次调用malloc…

C语言数据结构初阶-顺序表

什么是数据结构 数据结构是由数据和结构两个词结合而来&#xff0c; 那么数据由是什么 就比如我们日常生活中的1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;a,b,c,d,e文字信息图片等&#xff0c;这些就是数据 那么结构又是什么&#xff1f; 想像一下如…

Collection与数据结构 Stack与Queue(一): 栈与Stack

1. 栈 1.1 概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 压栈&…

【029】基于ssm+小程序实现的理发店预约系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;ssm 【…

Hadoop: word count,并将reduce结果写入ES

一、依赖&#xff0c;其中ES版本为7.6.2 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http…

[StartingPoint][Tier0]Mongod

Task 1 How many TCP ports are open on the machine? (机器上打开了多少个 TCP 端口&#xff1f;) Example: $ sudo nmap -sS -T4 10.129.222.112 -p 27017,22 2 Task 2 Which service is running on port 27017 of the remote host? (哪个服务正在远程主机的端口 270…

Hippo4j线程池实现技术

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容部署运行模式集成线程池监控配置参数默认配置 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家…

基于Java课程选课系统设计与实现(源码+部署文档)

博主介绍&#xff1a; ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅 &#x1f447;&#x1f3fb; 不然下次找不到 Java项目精品实…