写点什么

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

作者:雪芙花
  • 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;}
复制代码


  • 思路:


  1. 先判断是升序还是降序,或者只是相同的

  2. 假如是升序或者降序,一直++,直到不为升序或者降序为止

  3. 假如是相同的,直接++


  • 注意:


  1. 注意 开空间是开 n+1 个空间,以防越界

  2. 注意要有相同情况下的判断,不然会出现这种 情况


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

二:组队竞赛


#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;}
复制代码


  • 思路:


  1. 先排序

  2. 最优解是将最小的一个数和右边两个大数进行组队,这样得到的平均值最大


  • 注意:


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

三:倒置字符串


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


  • 代码:


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


  • 思路:


  1. 先输入一个单词到 s1 上

  2. 再循环输入,每次输入的单词都在上一个单词的前面

  3. 直到输入,即完成了逆置


  • 注意:


  1. 注意是 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
用户头像

雪芙花

关注

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

还未添加个人简介

评论

发布
暂无评论
牛客刷题系列之进阶版(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)_c_雪芙花_InfoQ写作社区