刷题经验分享（一）

删除公共字符：

第一题：删除公共字符
方法一：
思路：
1.将第二个字符串的字符都映射到一个hashtable数组中，用来判断一个字符在这个字符串。
2. 判断一个字符在第二个字符串，这里可以考虑使用将不在字符添加到一个新字符串，最后返回新字符串。

#include
#include
using namespace std;
int main()
{
// 注意这里不能使用cin接收，因为cin遇到空格就结束了。
// oj中IO输入字符串最好使用getline。
string str1,str2;
//cin>>str1;
//cin>>str2;
getline(cin, str1);
getline(cin, str2);
// 使用哈希映射思想先str2统计字符出现的次数
int hashtable[256] = {0};
for(size_t i = 0; i < str2.size(); ++i)
{
hashtable[str2[i]]++;
}
// 遍历str1，str1[i]映射hashtable对应位置为0，则表示这个字符在
// str2中没有出现过，则将他+=到ret。注意这里最好不要str1.erases(i)
// 因为边遍历，边erase，容易出错。
string ret;
for(size_t i = 0; i < str1.size(); ++i)
{
if(hashtable[str1[i]] == 0)
ret += str1[i];
}
cout<<ret<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

方法二：
思路：
这里我利用C++string类内置函数解题，建立两个string类str1、str2，利用string类特有的find_first_of函数在str1中找到str2中的字符，并返回对应的下标，然后擦除对应位置的字符，然后再从当前位置继续向下查找即可。

结合返回值找不到的话就返回npos，

这里的npos类型可以看到是无符号整型的，-1被赋值给无符号整形，那么这里的npos就是一个非常大的数字。

#include        // std::cout
#include          // std::string
#include         // std::size_t

using namespace std;

int main()
{
    string str1;
    getline(cin, str1);

    string str2;
    getline(cin, str2);


    std::size_t found = str1.find_first_of(str2);
    while (found != string::npos)
    {
        str1.erase(found, 1);
        found = str1.find_first_of(str2, found);//注意细节
    }

    cout << str1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法三：
思路：
为了尽量不使用erase函数，这样效率太低，因为每次删除都伴随数据挪动，所以每次把找到的位置替换成 *，然后再创建一个string类对象，依次遍历把不是 * 的尾插到这个string类对象中即可。

#include        // std::cout
#include          // std::string
#include         // std::size_t

using namespace std;

int main()
{
    string str;
    getline(cin, str);

    string sur;
    getline(cin, sur);


    std::size_t found = str.find_first_of(sur);
    while (found != string::npos)
    {
        str[found] = '*';
        found = str.find_first_of(sur, found + 1);
    }
    
    int num = 0;
    sur.reserve(str.size()+1);

    sur.clear();
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] != '*')
        {
            sur += str[i];
        }
        
    }
    
    cout << sur << endl;


    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

组队竞赛：

第二题：组队竞赛
思路：
队伍的水平值等于该队伍队员中第二高水平值，为了所有队伍的水平值总和最大的解法，也就是说每个队伍的第二个值是尽可能大的值。所以实际值把最大值放到最右边，最小是放到最左边。
【解题思路】：
本题的主要思路是贪心算法，贪心算法其实很简单，就是每次选值时都选当前能看到的局部最优解，所以这里的贪心就是保证每组的第二个值取到能选择的最大值就可以，我们每次尽量取最大，但是最大的数不可能是中位数，所以退而求其次，取每组中第二大的。

举例说明：
现在排序后有 1 2 5 5 8 9 ，那么分组为1 8 9 和 2 5 5，8和5都是我们尽最大可能所排的中位数最大值了。
现在排序后有 1 2 3 4 5 6 7 8 9，那么分组为1 8 9和2 6 7和3 4 5，其中8、6、4都是我们尽最大可能所排的中位数最大值了。

从上面的例子来看：那其实就是先对所给数组进行排序，然后从倒数第二个数，倒的数n次，把数到的数加起来就是最后答案。

#include
#include
#include  
using namespace std;
int main()
{
	long long num = 0;//题目数值类型比较大
	cin >> num;

	vector<long long> arr;
	arr.resize(num * 3);
	for (int i = 0; i < num * 3; i++)
	{
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());

	long long sum = 0, temp = arr.size() - 2;
	while (num)
	{
		sum += arr[temp];
		temp -= 2;
		num--;
	}
	cout << sum;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27