当前位置：首页 > article >正文

蓝桥杯16

article 2025/3/19 10:40:36

文章目录

- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入与输出
  - - 样例输入 1
    - 样例输出 1
    - 样例输入 2
    - 样例输出 2
    - 样例说明
  - 评测用例规模与约定
  - 思路分析
  - - 问题核心
    - 思路拆解
  - 代码段
  - 代码逐行讲解
  - 复杂度分析
  - 总结的知识点

题目描述

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位等）上的数字是奇数，偶数位（十位、千位、十万位等）上的数字是偶数，我们就称之为“好数”。

给定一个正整数 ( N )，请计算从 1 到 ( N ) 一共有多少个好数。

输入格式

一个整数 ( N )。

输出格式

一个整数代表答案。

样例输入与输出

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例说明

对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

评测用例规模与约定

对于 10% 的评测用例，( 1 \leq N \leq 100 )。
对于 100% 的评测用例，( 1 \leq N \leq 10^7 )。

思路分析

问题核心

判断一个数是否为“好数”，并统计从 1 到 ( N ) 中有多少个这样的数。

思路拆解

定义好数：
- 奇数位（从右往左数的第一个、第三个、第五个……）上的数字必须是奇数。
- 偶数位（从右往左数的第二个、第四个、第六个……）上的数字必须是偶数。
遍历每个数：
- 对于每一个数，检查其每一位是否满足上述条件。
- 如果满足条件，则计数器加一。

代码段

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            if (func(i)) {
                ans++;
            }
        }
        
        System.out.println(ans);
    }

    private static boolean func(int count) {
        int x = 1;
        while (count != 0) {
            int t = count % 10;
            if (x % 2 == 1) { // 奇数位
                if (t % 2 == 0) return false; // 奇数位上的数字必须是奇数
            } else { // 偶数位
                if (t % 2 == 1) return false; // 偶数位上的数字必须是偶数
            }
            x++;
            count /= 10;
        }

        return true;
    }
}

在这里插入图片描述

代码逐行讲解

读取输入数据：

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int ans = 0;

读取输入的整数 ( N )。
初始化计数器 ans 为 0。

遍历每个数并检查是否为好数：
```
for (int i = 1; i <= n; i++) {
    if (func(i)) {
        ans++;
    }
}
```
- 遍历从 1 到 ( N ) 的每个数。
- 调用函数 func(i) 检查当前数是否为好数，如果是则计数器 ans 加一。

函数 func 实现：

private static boolean func(int count) {
    int x = 1;
    while (count != 0) {
        int t = count % 10;
        if (x % 2 == 1) { // 奇数位
            if (t % 2 == 0) return false; // 奇数位上的数字必须是奇数
        } else { // 偶数位
            if (t % 2 == 1) return false; // 偶数位上的数字必须是偶数
        }
        x++;
        count /= 10;
    }

    return true;
}

初始化变量 x 为 1，表示当前处理的是第几位数字。
使用 while 循环逐位处理数字 count：
- 取出当前最低位数字 t。
- 如果当前位是奇数位（x % 2 == 1），则检查该位是否为奇数。
- 如果当前位是偶数位（x % 2 == 0），则检查该位是否为偶数。
- 更新 x 和 count，继续处理下一位。
如果所有位都满足条件，则返回 true，否则返回 false。

输出结果：
```
System.out.println(ans);
```

复杂度分析

时间复杂度：对于每个数需要遍历其每一位，假设 ( N ) 的最大值为 ( 10^7 )，则最坏情况下时间复杂度为 ( O(N \cdot d) )，其中 ( d ) 是数的最大位数。在本题中，( d ) 不超过 8，因此总的时间复杂度为 ( O(N) )。
空间复杂度：只使用了常数级别的额外空间，即 ( O(1) )。