湖北企业模板建站开发_大连今天最新通知_互联网营销外包公司_免费网站在线观看人数在哪直播

题目描述

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

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

输入格式

一个整数 ( N )。

输出格式

一个整数代表答案。

样例输入与输出

样例输入 1

24

样例输出 1

7

样例输入 2

2024

样例输出 2

150

样例说明

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

评测用例规模与约定

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

思路分析

问题核心

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

思路拆解

1. 定义好数：

   • 奇数位（从右往左数的第一个、第三个、第五个……）上的数字必须是奇数。
   • 偶数位（从右往左数的第二个、第四个、第六个……）上的数字必须是偶数。

2. 遍历每个数：

   • 对于每一个数，检查其每一位是否满足上述条件。
   • 如果满足条件，则计数器加一。

代码段

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;}
}

代码逐行讲解

1. 读取输入数据：

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

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

2. 遍历每个数并检查是否为好数：

   for (int i = 1; i <= n; i++) {if (func(i)) {ans++;}
   }
   

   • 遍历从 1 到 ( N ) 的每个数。
   • 调用函数 func(i) 检查当前数是否为好数，如果是则计数器 ans 加一。

3. 函数 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。

4. 输出结果：

   System.out.println(ans);
   

复杂度分析

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

总结的知识点

1. 数字处理：如何通过模运算和除法操作逐位处理一个整数。
2. 条件判断：根据题目要求对每个位进行奇偶性判断。
3. 循环控制：使用 for 循环遍历范围内的所有数，并调用辅助函数进行判断。
4. 输入输出处理：使用 Scanner 进行输入输出操作。