13.5 隐藏数字的发现

“小朋友们，有时候数字会藏在一串字符中，”我神秘地说，”今天我们要学习如何从混合字符串中找出最大的隐藏整数！”

13.5.1 寻找隐藏的最大整数

题目描述： 整数小伙伴们在玩捉迷藏，它们藏在一个长长的字符串中。我们需要找到隐藏在字符串中最大的那个整数的位置。隐藏的整数不会以0开头，且可能超过20位。

输入格式： 只有一个字符串，里面藏有很多的整数（字符串长度≤100，且不含空格）。

输出格式： 只有一个整数，表示藏在其中的最大的那个整数小伙伴的位置（整数第一个数字在原串中的位置）。

样例输入：

*((*-a32AB342+//32143abAA

样例输出：

17

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    char a[110];           // 存储输入的字符串
    char b[110] = {''};  // 存储当前正在处理的数字
    char c[110] = {''};  // 存储目前找到的最大数字
    
    cin >> a;              // 输入字符串
    int k = 0;             // b数组的当前位置
    int d;                 // 存储最大数字的结束位置
    
    // 遍历整个字符串
    for(int i = 0; i < strlen(a); i++){
        if(isdigit(a[i])){  // 如果是数字字符
            b[k++] = a[i];  // 添加到当前数字中
            
            // 如果到达字符串末尾或下一个字符不是数字，说明数字结束
            if(i == strlen(a) - 1 || !isdigit(a[i + 1])){
                b[k] = '';  // 添加字符串结束符
                
                // 去除前导零
                int l = 0;
                while(b[l] == '0' && strlen(b) > 1 && l < strlen(b) - 1){
                    l++;  // 跳过前导零
                }
                
                // 将去除前导零后的数字移到数组开头
                for(int x = 0, j = l; j < strlen(b); j++, x++){
                    b[x] = b[j];
                    if(j == strlen(b) - 1) b[++x] = '';
                }
                
                // 比较当前数字与已找到的最大数字
                if(strlen(b) > strlen(c)){
                    // 如果当前数字位数更多，直接更新
                    strcpy(c, b);
                    d = i;  // 记录结束位置
                }
                else if(strlen(b) == strlen(c) && strcmp(b, c) > 0){
                    // 如果位数相同但字典序更大，更新
                    strcpy(c, b);
                    d = i;  // 记录结束位置
                }
                k = 0;  // 重置当前数字位置
            }
        }
    }
    
    // 计算最大数字的起始位置
    cout << d + 1 - strlen(c) + 1;
    return 0;
}

算法解析：

1. 逐字符遍历字符串，提取所有数字串
2. 对每个数字串去除前导零
3. 比较数字大小：
   • 首先比较位数，位数多的更大
   • 位数相同时，使用字典序比较
4. 记录最大数字的结束位置，通过长度计算起始位置
5. 最终输出最大数字在原字符串中的起始位置