C++程序，用于删除数字字符串中的字符，使其能被8整除

1. 背景介绍

在生活中，经常会遇到需要处理数字字符串的需求。比如在手机号码、身份证号码等格式校验时，需要将输入的字符串中的数字提取出来进行校验。在实际应用中，还会遇到需要将数字字符串中的某些字符删除的情况，比如本文所解决的问题：删除数字字符串中的字符，使其能被8整除。

2. 问题描述

给定一个数字字符串，从中删除若干个字符，使得剩余字符组成的数字能够被8整除。如果无法删除任何字符，则返回空串。

2.1 输入格式

输入一个由数字组成的字符串，长度不超过1000。

2.2 输出格式

输出一个符合要求的数字字符串，如果无法删除任何字符，则输出空串。

3. 解题思路

本题是一道字符串处理的题目，需要对给定的数字字符串进行删除操作，使得剩余数字字符串能够被8整除。考虑对数字字符串进行枚举和删除操作。

3.1 枚举数字字符串

由于给定字符串的长度不超过1000，因此可以采用枚举的方式遍历所有非空子串。具体地，从第一个字符开始，枚举所有长度不小于1且不大于输入字符串长度的子串。如下图所示：

// 枚举所有子串

for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        string t = s.substr(i, len);
        // 处理子串t
    }
}

其中，n为输入字符串的长度，s为输入的数字字符串。

3.2 删除字符串

对于每个子串，需要通过删除操作使得剩余字符构成的数字能够被8整除。

对于一个三位数，其能够被8整除，当且仅当其各个位上数字构成的三位数能够被8整除。因此，在删除操作中，只需要删除那些不能被8整除的数字即可。

具体地，可以先统计各个数字的出现次数，然后依次判断数字0~9，删除其中一次出现的数字，再判断剩余数字组成的数字串是否能够被8整除。重复此过程，直到删除所有非0数字或数字串能够被8整除为止。如下图所示：

// 统计数字出现次数

int cnt[10] = {0};
for (int i = 0; i < t.size(); i++) {
    cnt[t[i] - '0']++;
}
// 删除不符合要求的数字
for (int i = 1; i <= 9; i++) {
    // 删除一个i
    if (cnt[i] > 0) {
        cnt[i]--;
        string tmp = "";
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < cnt[j]; k++) {
                tmp += (j + '0');
            }
        }
        int x = stoi(tmp);
        // 判断删除数字后是否符合要求
        if (x % 8 == 0) {
            t = tmp;
            break;
        } else {
            cnt[i]++;
        }
    }
}

4. 实现代码

综合上述思路，得到完整的C++程序如下：

#include <bits/stdc++.h>

using namespace std;
int main() {
    string s;
    cin >> s;
    bool flag = false;
    string ans = "";
    int n = s.size();
    // 枚举所有子串
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            string t = s.substr(i, len);
            // 统计数字出现次数
            int cnt[10] = {0};
            for (int i = 0; i < t.size(); i++) {
                cnt[t[i] - '0']++;
            }
            // 删除不符合要求的数字
            for (int i = 1; i <= 9; i++) {
                // 删除一个i
                if (cnt[i] > 0) {
                    cnt[i]--;
                    string tmp = "";
                    for (int j = 0; j <= 9; j++) {
                        for (int k = 0; k < cnt[j]; k++) {
                            tmp += (j + '0');
                        }
                    }
                    int x = stoi(tmp);
                    // 判断删除数字后是否符合要求
                    if (x % 8 == 0) {
                        t = tmp;
                        flag = true;
                        break;
                    } else {
                        cnt[i]++;
                    }
                }
            }
            if (flag) {
                if (ans == "") {
                    ans = t;
                } else {
                    ans = min(ans, t);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}