题解 | #牛牛数数#

题目链接

牛牛数数

题目描述

牛牛需要列出从 1 到 n 之间所有满足特定规则的整数。规则是：跳过所有含有数字 '4' 的数，也跳过所有是 4 的倍数的数。

输入描述: 输入一个正整数 n (1 ≤ n ≤ 1000)。

输出描述: 按升序输出所有从 1 到 n 中，既不包含数字 '4' 也不是 4 的倍数的整数，每个数字占一行。

解题思路

本题的核心是一个循环筛选过程。我们需要遍历从 1 到 n 的每一个整数 i，并对 i 进行两项检查：

它是不是 4 的倍数？
它的数位中是否包含数字 4？

只要这两个条件中任意一个成立，这个数 i 就应该被"跳过"。反之，如果两个条件都不成立，那么 i 就是符合要求的数，应该被输出。

算法步骤:

读取输入的整数 n。
使用一个 for 循环，让变量 i 从 1 遍历到 n。
在循环内部，对当前的 i 进行判断：
- 检查条件一: i % 4 == 0。如果这个为 true，则说明 i 是 4 的倍数，应该跳过，我们可以使用 continue 语句直接进入下一次循环。
- 检查条件二: i 是否包含数字 '4'。
  - 字符串法 (推荐): 这是最简洁的方法。将整数 i 转换为字符串，然后检查该字符串中是否包含字符 '4'。
  - 数学法: 使用之前题目中的"模除法"。循环 while (temp > 0)，在循环中用 temp % 10 检查个位数是否为 4，然后用 temp /= 10 去掉个位数，继续检查。
- 如果两个检查都不满足（即 i % 4 != 0 并且 i 不含 '4'），则输出 i。

由于外层循环本身就是从 1 到 n 升序进行的，所以输出结果自然就是升序的。

代码

c++
java
python

#include <iostream>
#include <string> // 为了使用 to_string

using namespace std;

// 辅助函数：检查数字是否包含'4'
bool containsFour(int n) {
    // 将数字转为字符串
    string s = to_string(n);
    // string::npos 表示没找到
    return s.find('4') != string::npos;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        // 条件1: 是4的倍数
        if (i % 4 == 0) {
            continue; // 跳过
        }
        // 条件2: 包含数字4
        if (containsFour(i)) {
            continue; // 跳过
        }
        
        // 两个条件都不满足，输出
        cout << i << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            // 条件1: 是4的倍数
            if (i % 4 == 0) {
                continue; // 跳过
            }
            
            // 条件2: 包含数字4 (使用字符串转换法)
            if (String.valueOf(i).contains("4")) {
                continue; // 跳过
            }

            // 两个条件都不满足，输出
            System.out.println(i);
        }
    }
}

n = int(input())

for i in range(1, n + 1):
    # 用一个 if 判断把所有要跳过的情况组合起来
    # not ( ... or ... ) 等价于 and
    if i % 4 != 0 and '4' not in str(i):
        print(i)

算法及复杂度

算法：循环与条件筛选。
时间复杂度： $\mathcal{O}(N \cdot \log_{10}N)$ 。外层循环执行 N 次。在每次循环中，取模是 $\mathcal{O}(1)$ 操作，而将数字 i 转换为字符串并检查需要的时间与 i 的位数（即 $\log_{10}i$ ）成正比。
空间复杂度： $\mathcal{O}(\log_{10}N)$ 。在检查数字是否含 '4' 时，如果使用字符串转换法，会临时创建一个字符串，其长度与 N 的最大位数成正比。如果不使用字符串，空间复杂度为 $\mathcal{O}(1)$ 。