携程 测开 笔试 9/4

四道编程题 2h

1、高铁时速区间[250,350]，动车[160,250]，城际列车[200,300]。输入速度，判断可能属于什么车。

直接用判断

2、输入{3}，则输出为2；

输入为{3，1}，则输出为1；

输入为{3，1，6}，则输出为3；

解释：{3}，需要补2个数{1，2}，才能成为数组{1，2，3}

{3，1}，需要补1个数{2}，才能成为数组{3，1，2}

{3，1，6}，需要补3个数{2，4，5}，才能成为数组{3，1，6，2，4，5}

使用动态规划nums[i]<max时，dp[i]=dp[i-1]-1；nums[i]>max时，dp[i]=nums[i]-max-1+dp[i-1]并更新max为nums[i];

初始化if nums[0]!=1时，dp[0]=nums[0]-1。max=Math.max(1,nums[0])

3、数学计算题：给定四个正整数l,r,k,x。求区间[l,r]中对k取余等于x的个数有多少。

4、图：没做出来