小O的五号倍数

题目链接: https://www.nowcoder.com/practice/f40cb14a15444609ac61bc4b4d75d3c3

题意

给定一个正整数 N（以字符串形式输入），每次可以删除其中一个数位，问最少删除多少个数位，使得剩余数字能被 5 整除。

特殊规定：全部删完后视为 0，0 也是 5 的倍数。

思路

一个整数能被 5 整除，当且仅当其最后一位是 0 或 5。

因此，策略是：

1. 从右往左扫描，找到第一个（即最右边的）值为 0 或 5 的位置 pos。
2. 保留 s[0..pos]，删掉 s[pos+1..n-1] 后面的所有数位。
3. 需要删除的数位数为 n - 1 - pos。
4. 如果整个字符串中没有 0 或 5，则需要删除全部 n 位（结果视为 0）。

正确性：因为我们要让最终数字的末位是 0 或 5，所以选择最靠右的满足条件的数位作为末位，可以最少删除其后的所有数位，且不需要删除该位之前的任何数位。

复杂度

• 时间复杂度：O(n)，n 为数字的位数
• 空间复杂度：O(n)

示例分析

代码

C++

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        string s;
        cin >> s;
        int n = s.size();
        int ans = n; // 全部删除，结果为 0
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0' || s[i] == '5') {
                ans = n - 1 - i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            String s = br.readLine().trim();
            int n = s.length();
            int ans = n; // 全部删除，结果为 0
            for (int i = n - 1; i >= 0; i--) {
                if (s.charAt(i) == '0' || s.charAt(i) == '5') {
                    ans = n - 1 - i;
                    break;
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}