leetcode 413.等差数列划分

server/2024/12/22 21:39:30/

思路:dp

因为正在练dp,所以这里就用dp的方法做了。

通过我们做过的一个题,就是leetcode 53.最大子段和那个,还有最长递增序列那一类题,我们可以知道,设置dp含义一般都是以什么什么数结尾,然后再去写转移方程。

这里还是一样,把nums[i]为尾作为dp数组的含义。

然后,我们想,这里不一样的地方其实还是在于长度必须是严格大于等于3这个条件,所以在这之前我们的dp数组都应该是0才对,从i=2这个下标才真正开始计数。

这里作者一开始在想和子段和有何不同的时候,没有想到价值怎么加,后来才发现这个只是对于个数计数,价值是1才对。

也就是说,当nums[i]-nums[i-1]==nums[i-1]-nums[i-2]的时候,我们这个时候默认是有三个数在一块并且是等差的,这个时候是符合条件的。dp[i]=dp[i-1]+1

上代码:

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;if(n<3)return 0;int []num=new int[n];for(int i=2;i<n;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){num[i]=num[i-1]+1;}}int ans=0;for(int i=2;i<n;i++){ans+=num[i];}return ans;}
}


http://www.ppmy.cn/server/35582.html

相关文章

毕业找工作经验,信息差玩死你

目录 公务员 事业编 考研读博 大厂 本文以计算机硕士为例讲解工作经; 公务员 关注省考和国考,这些知识在你找事业编的时候照样可以用到; 事业编 关注这几个网站: 工业和信息化部所属单位公开招聘考试考务服务平台

Shell脚本编写-定时清空文件内容,定时记录文件内容大小

find命令 – 根据路径和条件搜索指定文件 – Linux命令大全(手册)find命令的功能是根据给定的路径和条件查找相关文件或目录&#xff0c;其参数灵活方便&#xff0c;且支持正则表达式&#xff0c;结合管道符后能够实现更加复杂的功能&#xff0c;是Linux系统运维人员必须掌握的…

爬虫学习(2)破解百度翻译

代码 import requests import jsonif __name__ "__main__":url https://fanyi.baidu.com/sug#post请求参数处理&#xff08;同get请求一致&#xff09;headers {"User-Agent": Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, …

PostgreSQL的扩展pgpool

PostgreSQL的扩展pgpool pgpool-II&#xff08;通常简称为 pgpool&#xff09;是一个流行的 PostgreSQL 中间件&#xff0c;广泛用于连接池、负载均衡、自动故障转移等场景。作为一种高级数据库解决方案&#xff0c;pgpool 能够在多个 PostgreSQL 服务器之间分配数据库查询&am…

1天搞定SpringBoot+Vue全栈开发 (4)多表查询及分页查询

1.多表查询 在多表查询中&#xff0c;mybatis和mybatis plus无区别 User: package com.example.mpdemo.entity;import com.baomidou.mybatisplus.annotation.IdType; import com.baomidou.mybatisplus.annotation.TableField; import com.baomidou.mybatisplus.annotation.Ta…

【毕业设计】基于SSM的运动用品商城的设计与实现

1.项目介绍 在这个日益数字化和信息化的时代&#xff0c;随着人们购物习惯的转变&#xff0c;传统的实体商店已经无法满足人们日益增长的在线购物需求。因此&#xff0c;基于SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架的运动用品商城项目应运而生&#xff0…

zookeeper源码分析(五)——网络通信组件ServerCnxnFactory

1.概述 Zookeeper作为一个服务器,需要与客户端进行网络通信,Zookeeper使用ServerCnxFactory管理与客户端的连接,其中有两个实现,一个是NIOServerCnxnFactory,使用java原生Nio实现,一个是NettyServerCnxnFactory,使用netty实现。 2.NIOServerCnxnFactory 使用的是java…

【python】条件语句与循环语句

目录 一.条件语句 1.定义 2.条件语句格式 &#xff08;1&#xff09;if &#xff08;2&#xff09;if-else &#xff08;3&#xff09;elif功能 &#xff08;4&#xff09;if嵌套使用 3.猜拳游戏 二.循环语句 1. while循环 2.while嵌套 3.for循环 4.break和conti…