牛客网-华为-2020届校园招聘上机考试-软件类机考-2

题目描述：
输入一个字符串（不含空格），请寻找输入中包含所有蛇形字符串。
蛇形字符串定义：
1.蛇形字符串由连续字符对组成，其特点如下：
1.1 字符对定义：字符对由同一字母的大写和小写组成（前大后小）。如：Aa，Dd；
1.2 蛇形字符串中包含的字符对，必须是连续字母，并按照字母顺序排序。如：AaBbCc或OoPpQqRrSs；
2.从输入中寻找字符组成蛇形字符串（字符顺序不限），符合规则：
2.1 每次寻找必须是最长的蛇形字符串；
2.2 使用过的字符不能重复使用；

例：输入SxxsrR^AaSs
正确过程：
Step1：SxxsrR^AaSs -> RrSs （找到两对连续字符对：Ss、Rr，可以组成蛇形字符串。另，Ss后应该是Tt，但当前字符串SxxsrR^AaSs中不包含，所以当前蛇形字符串到Ss结束。本轮查找结果是RrSs。）
Step1：xs^AaSs -> Aa
Step1：xx^Ss -> Ss

……（省略其他错误说明）

输入描述：
一个字符串（不含空格，字符串长度<=5000）
输出描述：

所有包含的蛇形字符串，按首字母升序排列（即A在Z前）；（这里和前面2.1中“每次寻找必须是最长的蛇形字符串”冲突！）
同一个首字母的情况，按照蛇形字符串长度升序输出；
如果没有找到，输出Not Found。

示例1：
输入：SwSE$3454356DD$$E#eswsxxsssAAWDxxdderfvcRFER65645hbg^^%%^UnbnvccTRChnyvcxcvVCFR
输出：
（下面这个输出是题目给出的，但事实上和上面说的矛盾，是错误的！）
（这里我先按照上面的编写了很久，结果用这个案例自测一直错误；后来改成能输出下面结果的代码，即不管长度按照首字母顺序输出，这能够通过自测，提交之后能够通过60%的案列；然后很暴躁地重读题目，发现这个bug，就修改回原先的方法，并优化了代码，这才通过所有测试案例……因为这么小的系统bug，真的是耗神又耗时啊……）
CcDdEeFf
CcDdEe
RrSs
Ss
VvWw
（下面这个输出才是符合前面所说，是正确的）
CcDdEeFf
CcDdEe
RrSs
VvWw
Ss

1.思考

首先想到利用ASCII码来简化操作，这样所有的记录都可以用“a”+数字进行；
先定义一个26长度的vector <int> mp来计数Aa这样的有几个，每次找到并计数，再从str中删除；
然后调用自己编写的FindS()函数，来找到最长的蛇形字符串，用res来记录字符串开始和结束的位置，最后输出，输出的时候要在mp计数的对应位置-1；
如果存在蛇形字符串，则反复调用FindS()函数，直到所有蛇形字符串都输出；
如果FindS()函数没有找到蛇形字符串，则输出Not Found。

2.实现

这里一方面也因为自己太急躁没有完全读清楚题意，另一方面因为自己被之前不知名的Bug折腾的没有底，再加之时间一点点耗尽，所以耗费时间超级长；
进度差不多是这样的：半小时左右完成代码编写，之后40min左右一直在dubug。导致最后完成这道题之后只剩下20min左右了……
遇事一定不能慌！心态还是不行，有待提升！

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
#include <stdio.h>
#include <limits.h>
using namespace std;

bool FindS(vector<char>& str, vector<int>& mp)
{
    int count = 0, mxs = 0, i = 0, j = 0;
    vector<int> range(2);
    bool flag = false;
    while (i < 26){
        if (mp[i]>0){
            count = 1;
            j = i + 1;
            while (j < 26 && mp[j]>0){
                count++;
                j++;
            }
            if (count > mxs){
                flag = true;
                mxs = count;
                range[0] = i;
                range[1] = j - 1;
            }
            i = j + 1;
        }
        else{
            i++;
        }
    }

    if (flag == false)
        return false;

    vector<char> res;
    for (int i = range[0]; i <= range[1]; i++){
        res.push_back('A' + i);
        res.push_back('a' + i);
        mp[i]--;
    }

    int lres = res.size();
    for (int i = 0; i < lres; i++){
        if (i < lres - 1){
            cout << res[i];
        }
        else{
            cout << res[i] << endl;
        }
    }

    return true;
}

int main(){
    string input;
    vector<char> str;

    while (getline(cin, input)){
        str.clear();
        vector<int> mp(26, 0);

        for (auto in : input){
            str.push_back(in);
        }

        int posa, posA;
        for (int i = 0; i < 26; i++){
            auto pA = find(str.begin(), str.end(), 'A' + i);
            auto pa = find(str.begin(), str.end(), 'a' + i);
            while (pa != str.end() && pA != str.end()){
                posa = pa - str.begin();
                posA = pA - str.begin();
                str.erase(str.begin() + max(posa, posA));
                str.erase(str.begin() + min(posa, posA));
                mp[i]++;
                pA = find(str.begin(), str.end(), 'A' + i);
                pa = find(str.begin(), str.end(), 'a' + i);
            }
        }
        
        bool flag = false;
        while (1){
            if (FindS(str, mp) == false){
                break;
            }
            else{
                flag = true;
            }
        }   

        if (flag == false){
            cout << "Not Found" << endl;
        }

    }

    return 0;
}

秒客网

牛客网-华为-2020届校园招聘上机考试-软件类机考-2

相关文章