leetcode 413.等差数列划分

news/2024/12/22 15:26:04/

思路: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/news/1455645.html

相关文章

springboot项目组合定时器schedule注解实现定时任务

springboot项目组合定时器schedule注解实现定时任务&#xff01; 创建好springboot项目后&#xff0c;需要在启动类上增加注解开启定时器任务 下图所示&#xff1a; 增加这个注解&#xff0c;启动项目&#xff0c; package com.example.scheduledemo.util;import org.springf…

App在某个页面静止造成卡死假象

今天遇到一个bug记录下来,供后续积累经验。 预期结果:App在冷启动时会加载一个“广告页”,“广告页”有个定时器,定时器结束后会自动跳转到App首页;然而当用户开启指纹或人脸识别登录之后,App直接进入验证界面,验证通过后直接进入App首页。 bug场景:进入App需要指纹识别…

解决 java: 非法字符: ‘\ufeff‘

【报错解释】&#xff1a; 该错误通常发生在尝试编译Java源代码文件时&#xff0c;文件开头的字符是一个字节顺序标记&#xff08;Byte Order Mark&#xff0c;BOM&#xff09;&#xff0c;即\ufeff。在Java中&#xff0c;\ufeff不是一个合法的字符&#xff0c;因此编译器会报…

vue 设置输入框只能输入数字且只能输入小数点后两位,并且不能输入减号

<el-input v-model.trim"sb.price" placeholder"现价" class"input_w3" oninput"valuevalue.replace(/[^0-9.]/g,).replace(/\.{2,}/g,.).replace(/^(\-)*(\d)\.(\d\d).*$/,$1$2.$3)"/> 嘎嘎简单、、、、、、、、、

React受控绑定

受控绑定 概念&#xff1a;使用React组件的状态&#xff08;useState&#xff09;控制表单的状态 简单理解为双向绑定 function App(){const [value, setValue] useState()return (<input type"text" value{value} onChange{e > setValue(e.target.value)}/&…

v4l2 调用select的时候error返回-22(Invalid argument)

int maxFd fd 1; FD_ZERO(&fds); FD_SET(fd, &fds); struct timeval tv; tv.tv_sec 10; int ret ::select(maxFd, &fds, NULL, NULL, &tv);上面代码是判断v4l2的fd是否可读, 预期可读时返回1 今天在其他平台下跑代码返回errno -22 后面检查发现, 是struc…

csrf攻击(跨站请求伪造)【2】

1.DVWA中csrf漏洞验证low &#xff08;1&#xff09;受害者将密码更改为password&#xff0c;显示更改成功 (2)受害者未退出登录状态&#xff0c;打开了新链接(黑客设计好的修改密码为admin123(原本为passwrod)的链接&#xff09;&#xff0c;导致受害者密码被更改&#xff0c…

SpringBoot+Vue+Element-UI实现协同过滤算法商品推荐系统

前言介绍 本次设计任务是要设计一个基于协同过滤算法的商品推荐系统&#xff0c;通过这个系统能够满足商品推荐系统的管理功能。系统的主要包括首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;商品类型管理&#xff0c;商品信息管理&#xff0c;系统管理&#xff0…