关注
等差数列复盘
思路
设置k,i,j三个位置指针,k指向当前待判定序列的最左端点,i指向当前序列第一个不为-1的位置,j 指向当前序列第二个不为-1的位置。
求公差 d = (nums[j] - nums[i]) / (j - i); ,1. 若公差不为整数,说明 i 到 j 间不能构成等差序列 (例如1 -1 2 公差d为0.5,不符合题意) 2. 若 nums[j] - d*(j - k) <= 0) 说明最左面端点k值<=0 不符合题意。 则1.2两种情况均计数+1,指针k向右移动到 j 位置循环判断。
若可以构成等差序列,则指针k移动到 j+1位置向右寻找可以构成等差序列的最右端点。
c++:
#include<iostream>
(5488)#include<vector>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
vector<double> nums(n);
for (int i = 0; i < n; i++)
cin >> nums[i];
int cnt = 0, i, j, k = 0;
while (k < n)
{
cnt++;
i = k;
while (i < n && nums[i] == -1)
i++;
j = i + 1;
while (j < n && nums[j] == -1)
j++;
if (j >= n)
break;
double d = (nums[j] - nums[i]) / (j - i);
if (d - floor(d) || nums[j] - d*(j - k) <= 0)
{
k = j;
continue;
}
k = j + 1;
while (k < n && nums[j] + d*(k - j) > 0 && (nums[k] == -1 || nums[k] == nums[j] + d*(k - j)))
k++;
}
cout << cnt << endl;
}
return 0;
}
查看原帖
2 1
相关推荐


点赞 评论 收藏
分享
05-15 19:57
西安建筑科技大学 Java 点赞 评论 收藏
分享
牛客热帖
更多
- 1... 6月18日,我将站上法庭,正式起诉美团。我送出的每一单快件,都是我人生碎片的一部分。我会一直前进,拿回在海外SaaS失去的一切。5.6W
- 2... 研一快手后端开发,一周速通,附一二面面经1.3W
- 3... 毕业一年在回到学校的感觉真不一样1.0W
- 4... 25校招 双非硕 拿下大厂🐧1.0W
- 5... 挚文集团-陌陌笔试202506069655
- 6... 主包租房的经验总结!5336
- 7... 金山办公测试春招一面_珠海4316
- 8... 深入浅出秋招简历3887
- 9... 上海银行 修改入职协议 不还本科毕业证学位证双证原件 😂3748
- 10... 华为暑期实习3176
正在热议
更多
# 我的实习收获 #
34931次浏览 527人参与
# 安利/避雷我的专业 #
73655次浏览 515人参与
# 实习吐槽大会 #
38741次浏览 182人参与
# 我在牛爱网找对象 #
186458次浏览 1402人参与
# 晒一晒你的工位 #
87295次浏览 310人参与
# 你后悔选择现在的专业吗 #
81946次浏览 672人参与
# 你觉得专业和学校哪个对薪资影响最大 #
58165次浏览 473人参与
# 求职遇到的搞笑事件 #
113667次浏览 772人参与
# 移动求职进展汇总 #
1697次浏览 17人参与
# 2025牛客秋招季 #
6409次浏览 198人参与
# 机械人与华为的爱恨情仇 #
113404次浏览 938人参与
# 双非能在秋招上岸吗? #
215534次浏览 1150人参与
# 我的租房踩坑经历 #
33935次浏览 338人参与
# 第一份工作应该选高薪还是热爱? #
61761次浏览 562人参与
# 26届秋招投递记录 #
4973次浏览 132人参与
# 我的国央企投递进展 #
43154次浏览 268人参与
# 穿越回高考你还会选现在的专业吗 #
24928次浏览 285人参与
# 牛友们,签完三方你在忙什么? #
95207次浏览 841人参与
# 地方国企笔面经互助 #
30028次浏览 99人参与
# 招银网络求职进展汇总 #
113415次浏览 742人参与