牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。
如样例所示:
如果牛牛把6个队员划分到两个队伍
如果方案为:
team1:{1,2,5}, team2:{5,5,8}, 这时候水平值总和为7.
而如果方案为:
team1:{2,5,8}, team2:{1,5,5}, 这时候水平值总和为10.
没有比总和为10更大的方案,所以输出10.

输入描述:

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.

输出描述:

输出一个整数表示所有队伍的水平值总和最大值.

1.2 思路

这就是一个贪心的策略，想让总和最大那我直接从大到小排好每次取第二个，取n次就好了。

1.3代码实现

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<long long> v;
    long long n,ret = 0;
    cin >> n;
    int a = 3*n;
    long long temp = 0;
    while(a--)
    {
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(),v.end(),greater<int>());    
    for(int i = 1;i<=(2*n-1);i+=2)
    {
        ret+=v[i];
    }
    cout << ret << endl;
}

2.排序子序列

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述:

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述:

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

2.1?思路?

1.v[j] > v[j + 1]就是一个非递减排序的碰见不满足v[j] >= v[j + 1] count++ ；

2.v[j] <?v[j + 1]就是一个非递增排序的碰见不满足v[j] <= v[j + 1] count++ ；

3.v[j] ==?v[j + 1] 没有起或者伏往下走 j++；

2.2 代码实现

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v;
    //防止越界
    v.reserve(n + 1);
    //总的子序列的个数
    int count = 0;
    for(int i = 0;i < n;++i)
    {
        cin >> v[i];
    }
    int j = 0;
    while(j < n)
    {
        if(v[j] < v[j + 1])
        {
            while(v[j] <= v[j + 1])
            {
                j++;
            }
            count++;
            j++;
        }
        else if(v[j] > v[j + 1])
        {
            while(v[j] >= v[j + 1])
            {
                j++;
            }
            count++;
            j++;
        }
        else
        {
            j++;
        }
    }
    cout << count <<endl;
}

3.??数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n \le 50000n≤50000，数组中元素的值?0 \le val \le 100000≤val≤10000

要求：空间复杂度：O(1)O(1)，时间复杂度?O(n)O(n)

输入描述：

保证数组输入非空，且保证有解

3.1 思路?

1. 拿到这个题首先我想到就是排序然后加一个计数器count 遍历数组前后俩相等 count++ 出现不相等里面 count 置零如果 count 大于总元素个数的一半就return，还要加一点边界判断。

2. 之后发现了其实如果大于一半的话肯定那个数字必然在中间，大于总元素个数的一半。其实直接把中间那个元素 return 都可以，做到这发现其实你一直用的是 sort(); 也就是快排时间复杂度还是有的能不能再降一降。

3. 我们用哈希映射的思想用unordered_map来做，遍历一遍数组把值出现的次数存到map中，然后再遍历一遍找出来最多的。

3.2 代码实现

// class Solution {
// public:
//     int MoreThanHalfNum_Solution(vector<int> numbers) {
//         //有快排时间复杂度 O(N log N)
//     sort(numbers.begin(),numbers.end());
//     int count = 0;
//     int ret = 0;
//     for(int i = 0; i < numbers.size(); i++)
//     {
//         if(numbers[i] == numbers[i + 1])
//         {
//             ++count;
//             if(count >= (numbers.size() >> 1))
//             {
//                 ret = numbers[i];
//             }
//         }
//         else
//         {
//             count = 0;
//         }
//     }
//     if(numbers.size() == 1)
//     {
//         return numbers[0];
//     }
//         return ret;
//     }
// };


// class Solution {
// public:
//   int MoreThanHalfNum_Solution(vector<int> numbers) 
//   {
//       //既然他的长度大于数组的一半那说明中间必然是所求数字
//        sort(numbers.begin(),numbers.end()); 
//        int middle = numbers[numbers.size() >> 1];
//        int count = 0; 
//        for(int i = 0;i < numbers.size();++i)
//        {
//            if(numbers[i] == middle)
//            {
//                 count++;
//            }
//        }
//        return (count > numbers.size() >> 1) ? middle :  0;
//   }
// };


//  class Solution {
//  public:
//    int MoreThanHalfNum_Solution(vector<int> numbers) 
//    {
//         sort(numbers.begin(),numbers.end()); 
//         return numbers[numbers.size() >> 1];
//    }
//  };

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int,int> mp;
        for (auto & val : numbers)
        {
            mp[val]++;
        }
        for (auto & val : numbers) 
        {
            if (mp[val] > numbers.size() >> 1)
            {
                 return val;
            }
        }
        return 0;
    }
};

4. 计算糖果

A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息：
A - B, B - C, A + B, B + C. 这四个数值.每个字母代表每个人所拥有的糖果数.
现在需要通过这四个数值计算出每个人手里有多少个糖果,即A,B,C。这里保证最多只有一组整数A,B,C满足所有题设条件。

输入描述:

输入为一行，一共4个整数，分别为A - B，B - C，A + B，B + C，用空格隔开。 范围均在-30到30之间(闭区间)。

输出描述:

输出为一行，如果存在满足的整数A，B，C则按顺序输出A，B，C，用空格隔开，行末无空格。 如果不存在这样的整数A，B，C，则输出No

4.1 思路

这个就是一个翻译的过程，还有就是对结果的逆向判断一下看看是否有解的问题。

4.2 代码实现

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.reserve(4);
    
    int temp = 0;
    int a = 0, b = 0, c = 0;
    for(int i = 0;i < 4;i++)
    {
        cin >> v[i];
    }
    a = (v[0] + v[2]) >> 1;
    b = (v[1] + v[3]) >> 1;
    c = (v[3] - v[1]) >> 1;
    //A - B，B - C，A + B，B + C 来逆推一下
    if ((a - b) == v[0] && (b - c) == v[1] && (a + b) == v[2] && (b + c) == v[3])
    {
        cout << a << " " << b << " " << c;
    }
    else
    {
        cout << "No";
    }
}

5. 进制转换

给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数

输入描述:

输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。

输出描述:

为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）

5.1 思路?

1. 先有一个string类对象 s 保存结果辗转相除的结果不只有数字还有 A 到 F 字母 maptable 对象存放?

2. 判断是否为负数是的话就在最后加上 - 就好了

3. 你辗转相除的结果就是反过来的也就是逆序的? 在最后拼接的时候就是将 s 放在后面

5.2 代码实现

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s = "",maptable = "0123456789ABCDEF";
    int m = 0;
    int n = 0;
    cin >> m >> n;
    if(m == 0)
    {
        s = "0";
    }
    while(m)
    {
        if(m < 0)
        {
            m = -m;
            cout << "-";
        }
        s = maptable[m % n] + s;
        m /= n;
    }
    cout << s << endl;
}

6. 删除公共字符

描述

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”

输入描述：

每个测试输入包含2个字符串

输出描述：

输出删除后的字符串

6.1 思路

1. 这个题的第一思路就是遍历字符串s1 然后从 s2 第一个开始找找完一次删一个然后指针++ 移动到 s2 的第二个，这样的话时间复杂度很高就是O( N ^ 2);

2. 可以用哈希映射的方式来处理；

3. 给一个hashtable 先遍历 s2 统计一下s2中字符出现的个数给一个 string 类对象 ret 接受返回值，s1 映射过来如果等于0的话就说明这个字符没在 s2 中出现过直接拼接到 ret 上；

6.2 代码实现

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s1, s2, ret;
    getline(cin,s1);
    getline(cin,s2);
    int hashtabel[255] = { 0 };
    for(int i = 0;i < s2.size();i++)
    {
        hashtabel[s2[i]]++;
    }
    for(int i = 0;i < s1.size();i++)
    {
        if(hashtabel[s1[i]] == 0)
        {
            ret += s1[i];
        }
    }
    cout << ret << endl;
}

7. 倒置字符串

描述

将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I

输入描述：

每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100

输出描述：

依次输出倒置之后的字符串,以空格分割

7.1 思路

这个一个利用stack特性的一种巧解的思路?

7.2 代码实现

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

8.?字符串中找出连续最长的数字串

描述

读入一个字符串str，输出字符串str中的连续最长的数字串

输入描述：

个测试输入包含1个测试用例，一个字符串str，长度不超过255。

输出描述：

在一行内输出str中里连续最长的数字串。

8.1 思路

1. 实例化两个string对象 cur 和 ret 一个是当前的字符串，一个是要返回的字符串；

2. 判断是否是数字是的话拼接cur 一次次更新直到找到最长的数字串；

8.2 代码实现

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    string ret,cur;
    getline(cin,s);
    for(int i = 0;i <= s.size();i++)
    {
        if(s[i]>='0' && s[i]<='9')
        {
            cur += s[i];
        }        
        else
        {
            if(ret.size() < cur.size())
            {
                ret = cur;
            }
            else
            {
                cur.clear();
            }      
        }
    }
    cout << ret;
    return 0;
}