vivo提前批笔试题整理
寻找数组中不存在的元素
题目描述
A、B两个数组，要求输出A中存在而B中不存在的元素。
例如
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <iostream> #include <vector> #include <algorithm> using namespace std; void solution1(vector<int> a,vector<int> b) { int asize = a.size(); int bsize = b.size(); vector<int> result; for (int i = 0; i < asize; i++) { vector<int>::iterator it = find(b.begin(), b.end(), a[i]); if (it == b.end()) result.push_back(a[i]); } int rsize = result.size(); if (rsize == 0) cout << "No match!\n"; else { for (int i = 0; i < rsize - 1; i++) cout << result[i] << " "; cout << result[rsize - 1] << endl; } } int main() { vector<int> a{ 3,2,8,5,7,4,9,1 }; vector<int> b{ 3,8,1,9,5,10 }; solution1(a,b); system("pause"); return 0; } |
倒序链表中的两个元素之间的元素
题目描述
一个单向链表，输入m,n，要求在第m和第n区间之内的元素倒序存储并输出此链表。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <iostream> #include <vector> #include <algorithm> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; //vivo笔试中的解题方法 //void reverseBetween(ListNode* head, int m, int n) { // vector<int>temp; // ListNode *p=head; // while (p != NULL) // { // temp.push_back(p->val); // p = p->next; // } // reverse(temp.begin() + m - 1, temp.begin() + n); // int tsize = temp.size(); // for (int i = 0; i < tsize; i++) // { // cout << temp[i] << " "; // } // cout << endl; //} ListNode* reverseBetween(ListNode* head, int m, int n) { if (!head || !head->next || n == m) return head; struct ListNode *L = (struct ListNode *)malloc(sizeof(struct ListNode)); L->next = head; //删除节点常用手段考虑加个头指针 struct ListNode* pre = NULL; struct ListNode* p = L; int temp_m = m; int temp_n = n; //将p转移到反转链表的第一个节点，pre保存前一个节点 while (temp_m-- >= 1) { pre = p; p = p->next; } struct ListNode* reverse_head = NULL; struct ListNode* reverse_tail = p; struct ListNode* reverse_tail_after = NULL; struct ListNode* q = NULL; //进行反转 while (temp_n - m > 0) { q = p->next; reverse_tail_after = q->next; p->next = reverse_head; reverse_head = p; p = q; temp_n--; } p->next = reverse_head; reverse_head = p; pre->next = reverse_head; reverse_tail->next = reverse_tail_after; return L->next; } int main() { ListNode *temp1 = new ListNode(1); ListNode *head = temp1; for (int i = 2; i <= 10; i++) { ListNode * newnode = new ListNode(0); newnode->val = i; newnode->next = NULL; temp1->next = newnode; temp1 = temp1->next; } //reverseBetween(head, 3, 7); ListNode *result = reverseBetween(head, 3, 7); ListNode *p = head; while (p != NULL) { cout << p->val << " "; p = p->next; } cout << endl; system("pause"); return 0; } |
0-1背包问题
题目描述
有n种礼品，每个礼品对应一个热度值，总金额为k，每个礼品只能买一次，如何购买可以使得所有礼品的总热度值最高。
代码
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | /* * vivo2019提前批笔试第三题： * 小v负责一次活动礼品采购，每一款礼品的受欢迎程度(热度值)各不相同，现给出总金额以及各个礼品的单价 * 和热度值，且每个礼品只购买一个，如何购买可以使得所有礼品的总热度值最高。 * 输入： * 第一行是一个正整数，表示总金额(不大于1000) * 第二行是一个长度为n的正整数数组，表示礼品单价(n不大于100) * 第三行是一个长度为n的正整数数组，表示对应礼品的热度值 * 输出： * 一个正整数，表示可以获得的最高总热度值 * * 样例输入：1000 * 200 600 100 180 300 450 * 6 10 3 4 5 8 * 样例输出：21 */ #include <iostream> #include <vector> #include <algorithm> using namespace std; int solution3(int total,int len, vector<int>price, vector<int>hot) { vector<vector<int> > dp(len + 1, vector<int>(total + 1, 0)); for (int i = 1; i <= len; i++) { for (int j = 1; j <= total; j++) { if (price[i - 1]>j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - price[i - 1]] + hot[i - 1]); } } } return dp[len][total]; } int main() { int n, total;//商品数量和总价 int temp;//临时变量 cout << "请输入n和总价:" << endl; cin >> n >> total;//输入商品数量值和商品总价 vector<int> hot; vector<int> price; //价格存入 cout << "请输入热度" << endl; for (int i = 0; i<n; i++) { cin >> temp; hot.push_back(temp); } for (int i = 0; i<n; i++) { cin >> temp; price.push_back(temp); } //下面开始进行处理 int result = solution3(total, n, price, hot); cout << result << endl; system("pause"); return 0; } |
