admin管理员组

文章数量:815329

求职面试题

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、head2cur = 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. 反转head2cur = head2;struct List* pre = nullptr;tmp = cur;while(cur) {    /// cur->nexttmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}head2 = pre;    /// head2 = cur   为何改为这两句就不行了????// display_value("head1: ", head1);// display_value("head2: ", head2);// 3. 顺序拼接head和head2struct 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;
}

本文标签: 求职面试题