牛客刷题系列之进阶版（组队竞赛，排序子序列，倒置字符串，删除公共字符，修理牧场）

2022-10-21
湖南
本文字数：1570 字
阅读完需：约 5 分钟

一：排序子序列

题目：题目链接
代码：

#include<iostream>#include<algorithm>using namespace std;
int main(){    int n;    cin >> n;    int arr[n+1];    arr[n]=0;    for(int i=0;i<n;i++)    {      cin >> arr[i];    }    int a=0;    int count =0;    while(a<n)    {         if(arr[a]< arr[a+1])         {                 while(a<n && arr[a] <= arr[a+1])                     a++;         }        else if(arr[a] == arr[a+1])        {            a++;            continue;        }        else        {                 while(a<n && arr[a] >= arr[a+1])                     a++;        }        a++;        count++;    }    cout<<count;  return 0;}

复制代码

思路：

先判断是升序还是降序，或者只是相同的
假如是升序或者降序，一直++，直到不为升序或者降序为止
假如是相同的，直接++

注意：

注意开空间是开 n+1 个空间，以防越界
注意要有相同情况下的判断，不然会出现这种情况

假如没有相同情况的判断，会多加一次

二：组队竞赛

题目：题目链接
代码：

#include<iostream>#include<algorithm>using namespace std;
int main(){    int n;    cin >> n;    int sum;    sum =n*3;    int arr[sum];    for(int i=0;i<sum;i++)    {      cin >> arr[i];    }    sort(arr,arr+sum);   long sums =0 ;    int i=sum-2;    while(n--)    {       sums+= arr[i];        i-=2;    }    cout<<sums;      return 0;}

复制代码

思路：

先排序
最优解是将最小的一个数和右边两个大数进行组队，这样得到的平均值最大

注意：

注意排序函数要引用头文件<algorithm>

三：倒置字符串

题目：题目链接

这里就不写常规的写法了，只介绍一种我觉得很巧妙的方法

代码：

#include<iostream>using namespace std;
int main(){   string s1;    string s2;    cin>> s2;    while(cin>> s1)    {       s2 = s1 + " "+ s2;    }    cout<< s2;  return 0;}

复制代码

思路：

先输入一个单词到 s1 上
再循环输入，每次输入的单词都在上一个单词的前面
直到输入，即完成了逆置

注意：

注意是 s2 = s1 + " "+ s2;

启发：

当我们面对一些让我们自己输入的题目时，我们可以先一开始不全部输入进去，一部分一部分的输入，一边输入一边处理

四：删除公共字符

题目：题目链接
代码:

#include<iostream>using namespace std;
int main(){   string s1;   getline(cin,s1);   string s2;    cin>>s2;    char arr[256]={0};    for(int i=0;i<s2.size();i++)    {        arr[s2[i]] = 1;    }        auto it = s1.begin();    string ret;    for (it = s1.begin(); it != s1.end();it++)  {    if(arr[*it] == 0)            ret+= *it;    }    cout<<ret;
  return 0;}

复制代码

注意：

可以将要输出的内容保存到一个 string 里，可以减少很多不必要的运算

五：修理牧场（利用堆和哈夫曼树思想的运用）

题目：
代码:

#include<iostream>#include <queue>using namespace std;int main(){    int n, tatal = 0;    cin >> n;    priority_queue<int, vector<int>, greater<int>>  que;    while (n--)    {        int tem;        cin >> tem;        que.push(tem);    }    while (que.size() > 1)    {        int a = que.top();        que.pop();        int b = que.top();        que.pop();        tatal += a + b;        que.push(a + b);    }    cout << tatal;    return 0;}

复制代码

这道题主要考的是对堆，即优先级队列的运用

注意：

注意优先级队列的定义 priority_queue<int,vetcor<int >,great<int>> queue

ps

想和博主一样刷优质面试和算法题嘛，快来刷题面试神器牛客吧，期待与你在牛客相见噢！

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/bb4fafbfbd179ffa980e66a6b】。未经作者许可，禁止转载。

雪芙花

关注

还未添加个人签名 2022-04-28 加入

还未添加个人简介

发布

暂无评论

创作场景

牛客刷题系列之进阶版（组队竞赛，排序子序列，倒置字符串， 删除公共字符，修理牧场）

一：排序子序列

二：组队竞赛

三：倒置字符串

四： 删除公共字符

五：修理牧场（利用堆 和 哈夫曼树思想的运用）

ps

雪芙花

评论

牛客刷题系列之进阶版（组队竞赛，排序子序列，倒置字符串，删除公共字符，修理牧场）

四：删除公共字符

五：修理牧场（利用堆和哈夫曼树思想的运用）