顺丰笔试 8.29

等差数列复盘  思路 设置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; }

这一题应该是有问题的.... 题干说要控制成本，难道不是求最小值吗？最后给的例子却是求最大值... 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数字和-1个数。能组成等差就组，不能就把前面的划为一个等差数列，然后更新非-1数字，-1个数置0。 拍脑袋想的，不知道成不成立啊

同求

同求助，一题都没a出来

第二题好像是动态规划

补充一下 第二题要的是拖货最多的卡车最少拖多少货