滴滴4.10后端笔试算法第二题(java)
题目大致是这样的：
第一行输入N，X（N为数组长度，X为等差数列的公差，X大于0）；第二行输入为N个正整数，代表数组元素。每次可以变化数组中的一个元素为任意正整数，问将数组变成一个以X为公差的等差数列最小的步数（数列为正整数数列）。
本地用了几个测试用例均通过，但是提交上去AC只有0.18，提示答案错误（没有超时超空间）请大佬指正：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
int[] trees=new int[n];
for(int i=0;i<n;i++){
trees[i]=sc.nextInt();
}
sc.close();
int length=0; //连续等差子列长度
int max=0; //记录最长的长度
for(int i=1;i<n;i++){
if(trees[i]-trees[i-1]==x&&trees[i-1]>=1+(i-1)*x){ //寻找连续等差子数列，且该子序列起始点的值需满足让变化后的tree[0]>=1
length++;
max= max>length?max:length; //更新max
}else{ //不满足条件则length归零
length=0;
}
}
System.out.println(n-max-1);
}
}
查看6道真题和解析