HJ92 题解 | #在字符串中找出连续最长的数字串#

题意分析

• 给出一个字符串，我们需要将其中长度最长的数字子串输出，同时最后用一个逗号分隔，然后输出这个最长的字符串的长度。如果有多个最长字符串，按照顺序输出即可。

思路分析

• 这个题目，我们需要遍历这个字符串的每个字符，然后处理出这个字符串的数字子串，这个地方我们可以用一个临时的字符串收集，一旦遇到一个不是数字字符的就立马将之前的字符收集起来，然后将临时字符串情况。最后，我们收集到了所有的数字子串。然后进一步处理即可。

写法一

• 这种写法，我先把所有的字符串存进一个结构体里面，然后我们将这个结构体的小于运算符进行重载，长度长的优先级高，最后我们就可以很快地得到最长的那些字符串了。得到之后，我们逐个比较，将所有最长的数字子串按照题目要求输出即可。
• 代码如下
  • 结构体数组里面的元素的个数最多为n/2个，然后按照长度优先进行排序，同时需要遍历整个字符串，时间复杂度为$O(nlogn)O(nlogn)$
  • 结构体数组里面的元素最多为n/2个，所以空间复杂度为$O(n)O(n)$

#include<bits/stdc++.h>

using namespace std;


struct node{
    string str;
    int len;
    // 重载运算符，长度长的优先级高
    bool operator <(const node a){
        return len>a.len;
    }
}Node[205];

int main(){
    string s;
    while(cin>>s){
        int cnt=0;
        string c="";
        s+=" ";
        // 先收集每个字符串
        for(auto x:s){
            if(x>='0'&&x<='9'){
                c+=x;
            }else{
                if(c.size()){
                    Node[++cnt].str=c;
                    Node[cnt].len=c.size();
                }
                c="";
            }
        }
        // 特判，防止越界
        if(cnt==0){
            continue;
        }
        sort(Node+1,Node+1+cnt);
        int mxLen=Node[1].len;
        // 寻找长度最长的输出
        for(int i=1;i<=cnt;i++){
            if(Node[i].len==mxLen){
                cout<<Node[i].str;
            }else{
                break;
            }
        }
        cout<<","<<mxLen<<endl;
    }
    return 0;
}

写法二

• 这种写法是在上面一种写法的基础上进行改进的。我们用一个变量维护最长的数字子串的长度，同时用一个vector向量存储满足题目条件的所有的字符串，我们在得到每个数字子串的时候，我们更新维护最长的数字子串的长度。
  • 如果发现和目前已知的最长的数字子串的长度一致，那么我们直接放进向量里面；
  • 如果目前这个是已知的第一个最长的字符串，那么我们清空之前收集的字符串，更新最长的数字子串的长度，然后，将这个数字子串放进去。
  • 如果这个数字子串的长度小于目前已知的最长的数字子串的长度，那么我们不进行处理。
• 结合下图更好理解

• 代码如下
  • 我们需要遍历这个字符串，总的时间复杂度为$O(n)O(n)$
  • 在遍历这个字符串的时候，我们使用了vector来存储我们认为符合条件的字符串，空间复杂度为$O(n)O(n)$

#include<bits/stdc++.h>

using namespace std;
vector<string> v;
int main(){
    string s;
    while(cin>>s){
        v.clear();
        int mxLen=0; // 记录最长的字符串的长度
        s+=" "; // 确保最后的一个字符串一定不是数字字符
        string now;
        for(auto c:s){
            if(c<='9'&&c>='0'){
                now+=c;
            }else{
                int nowLen=now.size();
                // 说明之前的数字子串都比这个数字子串小
                if(nowLen>mxLen){
                    v.clear();
                    v.push_back(now);
                    mxLen=nowLen;
                }else if(nowLen==mxLen){ // 如果刚好等于的话，那么直接放进v里面
                    v.push_back(now);
                }
                now="";
            }
        }
        
        for(auto x:v){
            cout<<x;
        }
        cout<<","<<mxLen<<endl;
    }
    return 0;
}