题目描述

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

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

样例

24

7

算法1

(暴力枚举) $O(n)$ 最大时间复杂度7n

时间复杂度

$O(n)$ 最大时间复杂度7n

解析过程

由于题目是从个位开始一位位判断奇偶，可以设置一个判断数组，以此判断每个位是否等于判断数组，如果不等于说明不符合直接break

C++ 代码

#include <iostream>
using namespace std;
int main()
{
  int n;
  int flag[2]= {0,1}; // 判断数组
  int cnt = 0;
  cin >> n;
  for(int i = 1;i<=n;i++)
  {
      if(i % 2 == 0) continue;
      int k = 0,j = i;
      int res = 0;
      for( j = i;j > 0;j = j / 10)
      {
        res = (++k) % 2;  //通过加1求余来不断循环判断数组
        if(j % 2 == flag[res]) continue;
        else break;
      }
      //cout << j << ' ';
      if(j == 0) cnt ++;  //如果j退出循环等于0，说明全部判断通过
  }
  cout << cnt;
  return 0;
}