【机试】2017年03月06日阿里测试岗内推在线测试

题目大意

给定一组数字，判断该组数字可否被分为总和相同的四部分，其中每个部分中间有一个间隔点，抛弃不计。 例如： 对于{5, 2, 1, 1, 1, 1, 4, 3, 7, 2, 7} ， 可以划分为{{5,2},1,{1,1,1,4},3,{7},2,{7} 。 其中每个部分的总和都是7。 分隔点{1,3,2} 不列入计算。

解题思路

深搜。 计算第一个部分的总和，作为目标值，向下继续搜索。 由于不计算间隔值，所以将下标+2作为下一次搜索的开始下标，顺序向后遍历，计算当前总和，如果等于目标值，则继续向下搜索。 直到搜索次数为4并且开始下标大于数字总长度时，返回找到。 在最外层，顺序遍历扩大第一部分。由于只需要判断是否可以四分，所以当找到一个合理情况即可直接返回了。

CPP代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; bool dfs(const vector<int>& nums, int startIdx, int target, int step, vector<int>& sep) { //找到符合条件的一组 if (startIdx >= nums.size() && step == 4) return true; int sum = 0; for (int i = startIdx; i < nums.size(); ++i) { sum += nums[i]; //找到和目标值相同的一组数字，继续向下搜索后续分组 if (sum == target && dfs(nums, i + 2, target, step + 1, sep)) { if (i + 1 < nums.size()) sep.push_back(i + 1); return true; } } return false; } int main() { int numsArr[] = {5, 2, 1, 1, 1, 1, 4, 3, 7, 2, 7}; vector<int> nums(numsArr, numsArr + sizeof(numsArr) / sizeof(numsArr[0])); int sum = 0; bool isFourDivided = false; vector<vector<int> > ans; for (int i = 0; i < nums.size(); ++i) { sum += nums[i]; vector<int> sep; sep.push_back(i + 1); if (dfs(nums, i + 2, sum, 1, sep)) { isFourDivided = true; //break; sort(sep.begin(), sep.end()); ans.push_back(sep); } } if(isFourDivided) cout << "Yes" << endl; else cout << "No" << endl; for (int i = 0; i < ans.size(); ++i) { cout << "Seperator List " << i << ": "; for (int j = 0; j < ans[i].size(); ++j) { cout << "nums[" << ans[i][j] << "]=" << nums[ans[i][j]] << " "; } cout << endl; } return 0; }