刷题经验分享(一)
创始人
2024-02-08 11:34:16
0

文章目录

  • 删除公共字符:
  • 组队竞赛:

删除公共字符:

第一题:删除公共字符
方法一:
思路:
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<

方法二:
思路:
这里我利用C++string类内置函数解题,建立两个string类str1、str2,利用string类特有的find_first_of函数在str1中找到str2中的字符,并返回对应的下标,然后擦除对应位置的字符,然后再从当前位置继续向下查找即可。
在这里插入图片描述
结合返回值找不到的话就返回npos,
在这里插入图片描述
这里的npos类型可以看到是无符号整型的,-1被赋值给无符号整形,那么这里的npos就是一个非常大的数字。
在这里插入图片描述

#include        // std::cout
#include          // std::string
#include         // std::size_tusing 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;
}

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

#include        // std::cout
#include          // std::string
#include         // std::size_tusing 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 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 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;
}

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
客厅放八骏马摆件可以吗(家里摆... 今天给各位分享客厅放八骏马摆件可以吗的知识,其中也会对家里摆八骏马摆件好吗进行解释,如果能碰巧解决你...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...