奇安信 8月1 c++
1.单选20道
2.多选10道
3.编程题2道
#奇安信##笔试时间#
2.多选10道
3.编程题2道
(1)背包问题，给定总钱数，每个物品的价值，求能达到的最大价值。物品数量无限。
完全背包。
100
5
77 92
22 22
50 46
99 90
(2)给一个数组，[1，1，2]找到全排列之后能被7整除的数的个数.
全排列，但是没ac不懂我为什么，这题耗了我整整70多分钟，直接心态爆炸。
每次都是这这样，感觉题目都不难，然后都没做出来。
有没有好心人帮我看下，已知就过0.5，线下自测都是对的。
class Solution {
public:
int ans = 0;
bool is7(vector<int>& nums) {
int tmp = 0;
if (nums.size() > 0 && nums[0] == 0) return false;
for (int i = 0; i < nums.size(); i++) {
tmp = tmp * 10 + nums[i];
}
return tmp % 7 == 0;
}
void get_ans(vector<int>& nums, vector<int>& tmp, int index) {
if (tmp.size() == nums.size()) {
if (is7(tmp)) ans++;
return;
}
for (int i = index; i < nums.size(); i++) {
swap(nums[i], nums[index]);
tmp.push_back(nums[index]);
get_ans(nums, tmp, index + 1);
swap(nums[i], nums[index]);
tmp.pop_back();
}
return;
}
int reletive_7(int* digit, int digitLen) {
if (digitLen == 0) return 0;
if (digitLen == 1) return digit[0] == 7 ? 1 : 0;
vector<int> dig(digitLen, 0);
vector<int> tmp(digitLen, 0);
for (int i = 0; i < digitLen; i++) {
dig[i] = digit[i];
}
get_ans(dig, tmp, 0);
return ans;
}
}; 
查看19道真题和解析
