题解 | #小红的数字删除#

#include <iostream>
#include <string>
using namespace std;

// 判断一个数字是否是3的倍数
bool isDivisibleBy3(int sum) {
    if(sum == 0){
        return false;
    }
    return sum % 3 == 0;
}

// 去除字符串的前导0
string removeLeadingZeros(string& num) {
    int i = 0;
    while (i < num.length() && num[i] == '0') {
        i++;
    }
    return num.substr(i);  // 返回去掉前导0后的子字符串
}

int maxDeleteOperations(string num) {
    int deleteCount = 0;
    
    // 计算原始数字的数字和
    int sum = 0;
    for (char c : num) {
        sum += c - '0';
    }

    while (num.length() > 1) {
        bool found = false;

        // 尝试删除每一位数字
        for (int i = num.length() - 1; i >= 0; i--) {
            // 更新数字和
            int newSum = sum - (num[i] - '0');
            
            // 检查删除该位后的数字和是否是3的倍数
            if (isDivisibleBy3(newSum)) {
                num = num.substr(0, i) + num.substr(i + 1); // 删除i位置的数字
                num = removeLeadingZeros(num);  // 去除前导0
                sum = 0;
                for (char c : num) { // 更新新的数字和
                    sum += c - '0';
                }
                deleteCount++;  // 计数
                found = true;
                break;  // 找到合适的删除位置，退出当前循环
            }
        }

        // 如果找不到合适的删除位置，停止
        if (!found) {
            break;
        }
    }

    return deleteCount;
}

int main() {
    int T;
    cin >> T;  // 输入数据组数

    while (T--) {
        string n;
        cin >> n;  // 输入正整数n
        cout << maxDeleteOperations(n) << endl;  // 输出最多可以删除的次数
    }

    return 0;
}

感觉牛客的题解很不友好，总感觉看着怪怪的 orz

大致思路就是如上 写了注释。大致思路就是 emm ，首先，判断是不是3的倍数 他有这样一个性质嘛，他的和是3的倍数 那么 这个数就是3的倍数，，0除外。 先算出总和， 然后对当前字符串进行一个一个枚举，判断除去这个数之后的和还是不是三的倍数 如果是3的倍数，那么这个数可以被删除，然后拼接新的字符串，再除去前导0。如果遍历一遍还没有发现可以删去的数字，那么我们直接输出答案即可。 大致思路是这样的，此外我不会算 这个时间复杂度是多少，emm会不会被hack 欢迎大佬指点