每日一题（组队竞赛，排序子序列，倒置字符串， 删除公共字符，修理牧场）

2022-10-31 18:26:26 浏览数 (2)

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第18天，点击查看活动详情

一：组队竞赛

  • 题目：题目链接
  • 代码：
代码语言：javascript复制
#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. 注意排序函数要引用头文件

二：排序子序列

  • 题目：题目链接
  • 代码：
代码语言：javascript复制
#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 &amp;&amp; arr[a] <= arr[a 1])
                     a  ;
         }
        else if(arr[a] == arr[a 1])
        {
            a  ;
            continue;
        }
        else
        {
                 while(a<n &amp;&amp; arr[a] >= arr[a 1])
                     a  ;
        }
        a  ;
        count  ;
    }
    cout<<count;
  return 0;
}
  • 思路：
  1. 先判断是升序还是降序，或者只是相同的
  2. 假如是升序或者降序，一直 ，直到不为升序或者降序为止
  3. 假如是相同的，则直接
  • 注意：
  1. 注意 开空间是开 n 1个空间，以防越界
  2. 注意要有相同情况下的判断，不然会出现这种 情况

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

三：倒置字符串

  • 题目：题目链接

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

  • 代码：
代码语言：javascript复制
#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;
  • 启发：

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

四： 删除公共字符

  • 题目：题目链接
  • 代码:
代码语言：javascript复制
#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里，可以减少很多不必要的运算

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

  • 题目：
  • 代码:
代码语言：javascript复制
#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
int queue string

0 人点赞