PAT_甲级_1112 Stucked Keyboard (20分) (C++)【字符串处理】

大家好，欢迎来到IT知识分享网。

目录

1，题目描述

 题目大意

注意

2，思路

3，AC代码

4，解题过程

第一搏

1，题目描述

• stuck：动不了; 无法移动; 卡住; 陷住; 陷(入); 困(于); 被难住; 答不上来; 卡壳； 

Sample Input:

3 caseee1__thiiis_iiisss_a_teeeeeest 

Sample Output:

ei case1__this_isss_a_teest

 题目大意

键盘上有一些按键出现问题（stacked keys），这些按键每按一次，就会出现k个该按键对应的字符。给出一个字符串，找出这样的按键，并输出原本想输出的序列；

注意

• The stucked key will always repeat output for a fixed k times：stucked key是指，每次按下都会重复固定次数的按键；
• print in one line the possible stucked keys, in the order of being detected：按照检测出的先后顺序输出按键；

2，思路

虽然比较low，但是不容易出错，哈哈哈 

1. 遍历一遍字符串s，vector<int>ans1存放可能的stacked keys，set<int> tem存放不可能为stacked keys的键；
2. 遍历ans1，将ans1中不存在于tem中的字符放入vector<int>ans2中，ans2即为最终的stacked keys；
3. 遍历s，若字符存在于ans2则结果字符串s2中只保留一个，跳过后面k-1个字符，否则s2添加当前字符；

3，AC代码

#include<bits/stdc++.h> using namespace std; int k; string s; bool isRepeat(int index){ int num = 1; for(int i = index; i < s.size() - 1; i++){ if(s[i] == s[i+1]){ num++; if(num == k) return true; }else return false; } } int main(){ #ifdef ONLINE_JUDGE #else freopen("1.txt", "r", stdin); #endif // ONLINE_JUDGE cin>>k; cin>>s; vector<char> ans1, ans2; //ans1初步选定的keys ans2最终选定的keys set<int> tem; //确定不是stacked keys的键 int i = 0; while(i < s.size()){ if(isRepeat(i)){ ans1.push_back(s[i]); i += k; }else{ tem.insert(s[i]); i++; } } for(i = 0; i < ans1.size(); i++){ //将ans1中不属于tem的键 且在ans2中不重复的键 存入ans2中 if(find(tem.begin(), tem.end(), ans1[i]) == tem.end() && find(ans2.begin(), ans2.end(), ans1[i]) == ans2.end()) ans2.push_back(ans1[i]); } string s1 = ""; i = 0; //重新赋值 while(i < s.size()){ //s1代替原先的s if(find(ans2.begin(), ans2.end(), s[i]) == ans2.end()) s1 += s[i++]; else{ s1 += s[i]; i += k; } } for(i = 0; i < ans2.size(); i++) cout<<ans2[i]; cout<<endl<<s1; return 0; } 

4，解题过程

第一搏

不管怎样先把代码敲出来再说（用最土的办法，不断的来回拷贝。。。）

感觉比较low的几个地方：

1，第一次遍历s，将所有可能为stacked keys的字符都存入了ans1中，并将不可能为stacked keys的字符存入tem（set<int>）中，再遍历一遍ans1才能得出最终的stacked keys。

2，遍历ans1，将ans1中不存在于tem中的字符放入vector<int>ans2中

之所以另存到ans2中，而不是直接在ans1中删除，是因为以前写程序的时候遇到过，在遍历数据结构的同时，将数据结构中的某条记录删除，但其规模指针并未随之改变，从而出现了程序崩溃的错误，由于不是很熟悉vector的特性，为了保险这样做；

3，遍历s时，将字符另存到ans2中

原因与1相同；

#include<bits/stdc++.h> using namespace std; int k; string s; bool isRepeat(int index){ int num = 1; for(int i = index; i < s.size() - 1; i++){ if(s[i] == s[i+1]){ num++; if(num == k) return true; }else return false; } } int main(){ #ifdef ONLINE_JUDGE #else freopen("1.txt", "r", stdin); #endif // ONLINE_JUDGE cin>>k; cin>>s; vector<char> ans1, ans2; //ans1初步选定的keys ans2最终选定的keys set<int> tem; //确定不是stacked keys的键 int i = 0; while(i < s.size()){ if(isRepeat(i)){ ans1.push_back(s[i]); i += k; }else{ tem.insert(s[i]); i++; } } for(i = 0; i < ans1.size(); i++){ //将ans1中不属于tem的键 且在ans2中不重复的键 存入ans2中 if(find(tem.begin(), tem.end(), ans1[i]) == tem.end() && find(ans2.begin(), ans2.end(), ans1[i]) == ans2.end()) ans2.push_back(ans1[i]); } string s1 = ""; i = 0; while(i < s.size()){ //s1代替原先的s if(find(ans2.begin(), ans2.end(), s[i]) == ans2.end()) s1 += s[i++]; else{ s1 += s[i]; i += k; } } for(i = 0; i < ans2.size(); i++) cout<<ans2[i]; cout<<endl<<s1; return 0; } 

虽然过程看上去比较冗余，但由于整体数据量较小，所以运行时间还是很快的