关于c++:PAT甲级1112-Stucked-Keyboard

题目粗心

给定 k 和一个字符串 s，因为一些键盘的按键损坏，损坏的键按一下会反复呈现 k 次，要求你找出所有的坏件和原始输出字符串。

算法思路

一个键是坏键的前提是该字符每一次间断呈现的次数肯定是 k 的整数倍，那么咱们能够先采纳 hasShownNotStucked 哈希表记录那些肯定是好键的字符，又因为坏键只记录一次就好，所以应用 hasShownStucked 记录记录曾经呈现过并确定是坏键的按键，防止反复增加。咱们采纳两边遍历的形式进行求解

第一次遍历将所有肯定是好键的字符全副记录，具体做法就是比拟以后字符和后一字符是否相等，如果不等那么肯定不是坏键，否则统计其呈现的次数 cnt, 只有以后字符没有确定为好键并且 cnt%n!=0，那么就阐明该键为好键。

第二次遍历进行获取反复的字符组成的字符串 repeated 和原始字符串 origin，具体做法就是，如果以后字符肯定是好键，那么就增加进 origin 中，否则就得计算呈现的次数 cnt，并让 origin 增加 cnt/ n 个 s[i]，判断以后字符是否曾经记录为坏键，如果没有就记录该坏键并增加该字符到 repeated 中。

留神点

• 1、一个键有可能之前呈现 k 的整数倍次，然而最初呈现的次数不能整除 k，那么就阐明不是坏键，比方 k =3,s=eeerre，其中 e 就是好键，所以须要先遍历一遍将所有肯定是好键的键进行记录。

提交后果

AC 代码

#include<cstdio>
#include<iostream>
#include<unordered_map>

using namespace std;

unordered_map<char,bool> hasShownNotStucked;// 记录好键
unordered_map<char,bool> hasShownStucked;// 记录曾经呈现过并确定是坏键的按键

int main() {
    int n;
    scanf("%d",&n);
    string s;
    cin>>s;
    string repeated,origin;
    int i;
    // 第一次遍历记录所有肯定不是坏键的键
    for(i=0;i<s.size()-1;){if(s[i]!=s[i+1]){
            // 以后按键只呈现了一次，肯定不是坏键
            hasShownNotStucked[s[i]] = true;
            ++i;
        }else{
            // 统计呈现反复的次数
            int cnt = 0;
            for(int j=i;j<s.size();++j){if(s[j]==s[i]){++cnt;}else{break;}
            }
            if(!hasShownNotStucked[s[i]]&&cnt%n!=0){
                // 以后字符之前不确定，然而无奈整除 n 阐明肯定不是坏键
                hasShownNotStucked[s[i]] = true;
            }
            i += cnt;
        }
    }
    if(i<s.size()){// s[i]!=s[i+1], 阐明最初一个键也不是坏键
        hasShownNotStucked[s[i]] = true;
    }
    for(i=0;i<s.size();){if(hasShownNotStucked[s[i]]){
            // 肯定不是坏键
            origin += s[i++];
        }else{
            // 有可能是坏键
            // 统计呈现反复的次数
            int cnt = 0;
            for(int j=i;j<s.size();++j){if(s[j]==s[i]){++cnt;}else{break;}
            }
            // 反复增加 cnt/ n 个 s[i]
            int a = cnt/n;
            while(a--){origin += s[i];
            }
            if(!hasShownStucked[s[i]]){
                // 之前没有增加过该反复字符
                hasShownStucked[s[i]] = true;
                repeated += s[i];
            }
            i += cnt;
        }
    }
    cout<<repeated<<endl<<origin;
    return 0;
}