[programming training] delete public characters (hash mapping) + team competition (greedy)

1. Delete public characters -> link

【 Their thinking 】：

If we use the traditional violence search method , For example, judge whether the character of the first string is in the second string , Move the character again to delete this character
The way , The efficiency is O(N^2), Efficiency is too low , It's hard to satisfy .

• Map the characters of the second string to a hashtable Array , Used to determine a character in this string .

• Judge a character in the second string , Do not use delete , That's inefficient , Because every deletion is accompanied by data movement . Here To consider the use of adding an absent character to a new string , Finally, a new string is returned .

Implementation code ：

#include<iostream>
#include<string>
using namespace std;

int main()
{
    
    string s1,s2;
    //  Be careful not to use cin receive , because cin It ends when you encounter a space .
    // oj in IO The best input string is getline.
    getline(cin,s1);
    getline(cin,s2);
    
    int hash[256]={
    0};
    //  Using the idea of hash mapping, first str2 Count the number of times characters appear 
    for(int i=0;i<s2.size();i++)
    {
    
        hash[s2[i]]++;
    }
    
    //  Traverse str1,str1[i] mapping hashtable The corresponding position is 0, It means that this character is in  
    // str2 There's no such thing as , Then take him += To ret. Be careful not to str1.erases(i) 
    //  Because edge traversal , edge erase, It's easy to make mistakes .
    string ret="";
    for(int j=0;j<s1.size();j++)
    {
    
        if(hash[s1[j]]==0)
            ret+=s1[j];
    }
    
    cout<<ret<<endl;
    return 0;
    
}

2. Team competition -> link

【 title 】：

The level value of the team is equal to the second highest level value among the team members , For the solution of the maximum sum of the level values of all teams , That is to say, every team
The second value of is the largest possible value . So the actual value puts the maximum value to the far right , The smallest is on the far left .

【 Their thinking 】：

The main idea of this problem is greedy algorithm , The greedy algorithm is actually very simple , That is, each time you select a value, you choose the most worry free part you can see at present , So the greed here is to ensure that the second value of each group is the maximum value that can be selected , We try to maximize each time , But the biggest The number cannot be the median , So back to second place , Take the second largest in each group .

• for example Now after sorting Yes 1 2 5 5 8 9 , Then group them into 1 8 9 and 2 5 5
• Relational ：arr[arr.length-(2*(i+1))]( What you get is the level value of a team )

Code implementation ：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    
    int n=0;
   // Loop to implement multiple sets of tests 
    while(cin>>n)
    {
    
         vector<int> a;
        long long sum=0;
        a.resize(3*n);
        for(int i=0;i<3*n;i++)
        {
    
            cin>>a[i];
        }
        std::sort(a.begin(),a.end());// use sort Implement ascending sort 
        for(int i=0;i<n;i++)
        {
    
            sum+=a[a.size()-(2*(i+1))];
        }
      cout<<sum<<endl;
    }
   
    return 0;
}