v***在线笔试
时间：2-7 15：00
工具：牛客网
题型：7到单选、3道多选、3道编程，90min
编程1：拿手机的方案（类似于上楼梯），一次可以拿1、2、3、4部手机，问仓库里n台手机有多少种方案进行拿取？
int total_count(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 3;
} else if (n ==3 ) {
return 4;
} else if (n == 4) {
return 8;
} else {
std::vector<int> dp(n, 0);
dp[1] = 2, dp[2] = 3, dp[3] = 4, dp[4] = 8;
for (int i = 5; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4];
}
return dp[n];
}
}
编程2：
有一个数组nums，每个元素代表着对应的图片被查看的次数。以后每查看一张图片，则对应的位置加1。输入一个数n，表示可以查看的总次数，问查看n此后nums中元素出现的最大频次是多少？
举例：3 [3,4,5] 说明：有3张图片（nums有3个元素），图片分别已经被查看3、4、5次，还可以查看3次
输出：4 说明：查看图片0两次、图片1一次，则nums变为[5,5,5]，所以最大频数是3。
解决思路：先对nums排序，再从后遍历，
int getMaxFreq(int n, std::vector<int>& nums) {
int len = nums.size();
sort(nums.begin(), nums.end());
int max_count = 0;
for (int i = len - 1; i > 0; --i) {
int max_count_tmp = 1;
int gap = 0;
int n_copy = n;
int j = 1;
while(n_copy && (i-j) >= 0) {
gap = nums[i] - nums[i-j];
if(gap > n_copy) {
break;
} else {
n_copy -= gap;
max_count_tmp++;
}
j++;
}
max_count = max_count_tmp > max_count ? max_count_tmp:max_count;
}
return max_count;
}
编程3：动态规划-多重背包
分房：有n个员工，k种房间、每种房间可容纳的人为p1,p2,...,pk，费用为c1,c2,...,ck，数量为r1,r2,...,rk。
如何分房，花费最小
分析：背包容量就是n，有k种物品、每种有rk个、代价是pk、费用是ck（代价其实就是重量、或者体积，此处体积更好）
还是有点不一样，没想出来
int minCost(int n, std::vector<int>& p, std::vector<int>& c, std:vector<int>& r) {
int bagV = n;
int objNum = p.size();
std::vector<int> dp(bagV + 1, 0);
for (int i = 1; i <= objNum; ++i) {
for (int j = bagV; j > 0; j--) {
if (j < p[i]) {
dp[j] = dp[j];
} else {
for (int k = 0; k <= j / p[i] && k <= r[i]; k++) {
dp[j] = min(dp[j], dp[j - k * p[i]] + k * c[i]);
}
}
}
}
return dp[bagV];
}
o***在线笔试
单选、多选、两道编程题，90min
编程题1：
输出倒叙数
编程题2：
/**
* author: CofCai
* datatime: 2022-03-04 11:59:12
* file description:
* OPPO在线笔试第2道编程题
* 一个单链表，如1-2-3-4-5
* 返回1-5-2-4-3，即最前和最后两两对应。需自己处理输入，然后构造链表
* 输入样例：head = [1,2,3,4,5]
* 输出样例：[1,5,2,4,3]
* 思路：1.处理输入，构造链表head
* 2. 将链表从中间断开，形成2个链表，即head1、head2
* 3. 将head2反转
* 4. 依次取head1、head2的元素进行连接
*/
using namespace std;
void display_value(string str, struct List* const head);
struct List
{
int val;
struct List* next;
};
int main()
{
// 处理输入：head = [1,2,3,4,5]
string input;
cin >> input >> input >> input;
// cout << input << endl;
struct List* head = (struct List*)malloc(sizeof(struct List));
struct List* cur = head;
int len_str = input.size();
int len = 0;
for (int i = 1; i < len_str; i += 2)
{
len++;
cur->val = input[i] - 0x30;
if(i + 2 >= len_str) {
cur->next = nullptr;
} else {
cur->next = (struct List*)malloc(sizeof(struct List));
cur = cur->next;
}
// cout << cur->next->val << endl;
}
// 处理逻辑
// 1. 将链表平均分为两段、即head1、head2
cur = head;
for (int i = 0; i < len/2 - 1; ++i) {
cur = cur->next;
}
struct List* tmp = cur->next;
cur->next = nullptr;
struct List* head2 = tmp;
struct List* head1 = head;
// display_value("head1: ", head1);
// display_value("head2: ", head2);
// 2. 反转head2
cur = head2;
struct List* pre = nullptr;
tmp = cur;
while(cur) { /// cur->next
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
head2 = pre; /// head2 = cur 为何改为这两句就不行了？？？？
// display_value("head1: ", head1);
// display_value("head2: ", head2);
// 3. 顺序拼接head和head2
struct List* cur1 = head1;
struct List* cur2 = head2;
struct List* tmp1 = nullptr;
struct List* tmp2 = nullptr;
while(cur1) {
tmp1 = cur1->next;
tmp2 = cur2->next;
cur1->next = cur2;
if(tmp1 == nullptr && tmp2 != nullptr) {
cur2->next = tmp2;
}else {
cur2->next = tmp1;
}
// 更新
cur1 = tmp1;
cur2 = tmp2;
}
display_value("", head1);
return 0;
}
void display_value(string str, struct List* const head){
if(str.size())
cout << str;
struct List* cur = head;
while(cur) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
