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

文章浏览阅读183次。1,题目描述stuck:动不了;无法移动;卡住;陷住;陷(入);困(于);被难住;答不上来;卡壳;SampleInput:3caseee1__thiiis_iiisss_a_teeeeeestSampleOutput:

目录

1,题目描述

 题目大意

注意

2,思路

3,AC代码

4,解题过程

第一搏


1,题目描述

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

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

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;
}



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

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

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/88333.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注