顺丰笔试 8.29

第一题：

一个数组中有不确定值和确定值，确定值为正整数，不确定值为-1，不确定值-1 可以变为任意正整数，将数组分段，每段要求是等差数列，求最少的段数

注一个数和两个数必为等差数列

例如

输入3个数

-1 -1 -1

输出

3个数不需要分割即为等差数列，最少段数为1

输入

-1，-1，1

输出

输入

1，-1，2

输出

输入

-1，-1，-1，4，5，1，2

输出

第二题：

货物数目为n，货车数目为k，货物第 i 个重量为 w[i]，货车可以搬运index连续的货物到货车上，每个货车必须有货物，每个货车的运输成本等于它里面装有的货物的 weight 总值的平方，问最大的运输成本为多少且拉货物最多的货车一共拉了多少货物？

例如

输入

货物 4 个，货车3个，货物重量【1，2，3，4】

输出

最大运输成本：分割【1】【2】【3，4】 = 1 + 4 + 49 = 54

拉货物最多的车拉了 2 个货物

0AC

求大佬指点

#笔试题目##顺丰科技#

全部评论

推荐最新楼层

牛客638832633号

哈尔滨工程大学 Java

等差数列复盘思路设置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> #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 回复分享

发布于 2020-08-31 14:35

首夏犹清和

京东_广告部_后端开发工程师

这一题应该是有问题的.... 题干说要控制成本，难道不是求最小值吗？最后给的例子却是求最大值... public int func(int[] nums, int m) { int n = nums.length; int[][] f = new int[n + 1][m + 1]; for (int i = 0; i <= n; i++) { Arrays.fill(f[i], Integer.MIN_VALUE); //如果求最小值，改成MAX_VALUE } int[] sub = new int[n + 1]; for (int i = 0; i < n; i++) { sub[i + 1] = sub[i] + nums[i]; } f[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= Math.min(i, m); j++) { for (int k = 0; k < i; k++) { int val = (sub[i] - sub[k])*(sub[i] - sub[k]); f[i][j]=Math.max(f[i][j],f[k][j-1]+val); //如果求最小值，改成Math.min } } } return f[n][m]; }

1 回复分享

发布于 2020-08-29 21:45

Miao_txy

武汉大学算法工程师

第一题贪心可以试试，遍历数组，记录之前最后一个非-1数字和-1个数。能组成等差就组，不能就把前面的划为一个等差数列，然后更新非-1数字，-1个数置0。拍脑袋想的，不知道成不成立啊

1 回复分享

发布于 2020-08-29 20:10

振动的厉害

门头沟学院 Java

同求

点赞回复分享

发布于 2020-08-30 00:35