2019-06-05 446 views 评论

vivo2020校招提前批开发笔试试题

vivo 提前批笔试题整理

寻找数组中不存在的元素

题目描述

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

代码实现

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
using namespace std;

void solution1(vector&lt;int&gt; a,vector&lt;int&gt; b)
{
    int asize = a.size();
    int bsize = b.size();
    vector&lt;int&gt; result;
    for (int i = 0; i &lt; asize; i++)
    {
        vector&lt;int&gt;::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 &lt;&lt; "No match!\n";
    else
    {
        for (int i = 0; i &lt; rsize - 1; i++)
            cout &lt;&lt; result[i] &lt;&lt; " ";
        cout &lt;&lt; result[rsize - 1] &lt;&lt; endl;
    }

}

int main()
{
    vector&lt;int&gt; a{ 3,2,8,5,7,4,9,1 };
    vector&lt;int&gt; b{ 3,8,1,9,5,10 };
    solution1(a,b);
    system("pause");
    return 0;
}

#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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

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&lt;int&gt;temp;
//  ListNode *p=head;
//  while (p != NULL)
//  {
//      temp.push_back(p-&gt;val);
//      p = p-&gt;next;
//  }
//  reverse(temp.begin() + m - 1, temp.begin() + n);
//  int tsize = temp.size();
//  for (int i = 0; i &lt; tsize; i++)
//  {
//      cout &lt;&lt; temp[i] &lt;&lt; " ";
//  }
//  cout &lt;&lt; endl;
//}

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (!head || !head-&gt;next || n == m) 
        return head;
    struct ListNode *L = (struct ListNode *)malloc(sizeof(struct ListNode));
    L-&gt;next = head;     //删除节点常用手段考虑加个头指针
    struct ListNode* pre = NULL;
    struct ListNode* p = L;
    int temp_m = m;
    int temp_n = n;
    //将p转移到反转链表的第一个节点，pre保存前一个节点
    while (temp_m-- &gt;= 1) {
        pre = p;
        p = p-&gt;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 &gt; 0) {
        q = p-&gt;next;
        reverse_tail_after = q-&gt;next;
        p-&gt;next = reverse_head;
        reverse_head = p;
        p = q;
        temp_n--;
    }

    p-&gt;next = reverse_head;
    reverse_head = p;
    pre-&gt;next = reverse_head;

    reverse_tail-&gt;next = reverse_tail_after;
    return L-&gt;next;
}


int main()
{
    ListNode *temp1 = new ListNode(1);
    ListNode *head = temp1;
    for (int i = 2; i &lt;= 10; i++)
    {
        ListNode * newnode = new ListNode(0);
        newnode-&gt;val = i;
        newnode-&gt;next = NULL;
        temp1-&gt;next = newnode;
        temp1 = temp1-&gt;next;
    }
    //reverseBetween(head, 3, 7);
    ListNode *result = reverseBetween(head, 3, 7);
    ListNode *p = head;
    while (p != NULL)
    {
        cout &lt;&lt; p-&gt;val &lt;&lt; " ";
        p = p-&gt;next;
    }
    cout &lt;&lt; endl;
    system("pause");
    return 0;
}

#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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

using namespace std;

int solution3(int total,int len, vector&lt;int&gt;price, vector&lt;int&gt;hot)
{
    vector&lt;vector&lt;int&gt; &gt; dp(len + 1, vector&lt;int&gt;(total + 1, 0));
    for (int i = 1; i &lt;= len; i++)
    {
        for (int j = 1; j &lt;= total; j++)
        {
            if (price[i - 1]&gt;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 &lt;&lt; "请输入n和总价:" &lt;&lt; endl;
    cin &gt;&gt; n &gt;&gt; total;//输入商品数量值和商品总价
    vector&lt;int&gt; hot;
    vector&lt;int&gt; price;
    //价格存入
    cout &lt;&lt; "请输入热度" &lt;&lt; endl;
    for (int i = 0; i&lt;n; i++)
    {

        cin &gt;&gt; temp;
        hot.push_back(temp);
    }
    for (int i = 0; i&lt;n; i++)
    {
        cin &gt;&gt; temp;
        price.push_back(temp);
    }
    //下面开始进行处理
    int result = solution3(total, n, price, hot);
    cout &lt;&lt; result &lt;&lt; endl;
    system("pause");
    return 0;

}