只能说自己水平太次，所以在笔试的时候只通过了1道题，复杂度还是O(n2)级别的。紧张什么的都不是理由。做完这道题，让我认识到我的水平距离秋招还太远太远。

vivo提前批笔试题整理

寻找数组中不存在的元素

题目描述

A、B两个数组，要求输出A中存在而B中不存在的元素。
例如

代码实现

#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区间之内的元素倒序存储并输出此链表。

代码实现

#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，每个礼品只能买一次，如何购买可以使得所有礼品的总热度值最高。

代码

/*
* 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;

}