蓝桥杯16

文章目录

- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入与输出
  - - 样例输入 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) )。