首页 > 代码库 > PAT甲题题解-1112. Stucked Keyboard (20)-(map应用)

PAT甲题题解-1112. Stucked Keyboard (20)-(map应用)

题意:给定一个k,键盘里有些键盘卡住了,按一次会打出k次,要求找出可能的坏键,按发现的顺序输出,并且输出正确的字符串顺序。

map<char,int>用来标记一个键是否为坏键,一开始的时候都为0,表明所有的键为坏键。

然后遍历每个字符,统计当前字符连续出现的次数cnt,则只要存在cnt%k!=0,则表明为好键,另其map=1。

最后再for一遍字符串,存储坏键字符串和正确字符串,最后输出即可。

技术分享
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
const int maxn=1000+5;
int k;
char str[maxn];
map<char,int> maps; //一开始都为0,表示为stucked keys
int main()
{
    scanf("%d",&k);
    scanf("%s",str);
    int len=strlen(str);
    char ch;
    int cnt;
    for(int i=0;i<len;i+=cnt){
        ch=str[i];
        int p=i;
        for(;ch==str[p+1];p++);
        cnt=p-i+1;
        if(cnt%k!=0){
            maps[ch]=1; //如果连续出现的次数不是k的倍数,显然不是stucked keys,标记为1
        }
    }
    char ans[maxn];
    char stucked[maxn];
    int idx=0,idx2=0;;
    cnt=0;
    for(int i=0;i<len;i+=cnt){
        if(maps[str[i]]==1){
            ans[idx]=str[i];
            idx++;
            cnt=1;
        }
        else{
            int p=i;
            //若stucked keys第一次出现对应的map为0,之后标记为2
            if(maps[str[i]]!=2){
                stucked[idx2]=str[i];
                idx2++;
                maps[str[i]]=2;
            }
            for(;str[i]==str[p+1];p++);
            cnt=p-i+1;
            for(int j=0;j<cnt/k;j++){
                ans[idx]=str[i];
                idx++;
            }
        }
    }
    ans[idx]=\0;
    stucked[idx2]=\0;
    printf("%s\n",stucked);
    printf("%s",ans);


    return 0;
}
View Code

 

PAT甲题题解-1112. Stucked Keyboard (20)-(map应用)