一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称之为“好数”。给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

我的思路就是利用

while(x){
	int dight = x % 10;
	// do something
	x /=10;
}

取它的每一位判断,但我怎么可以确定每一位是对应奇数位还是偶数位了?我无法确定,于是我就想到一种简单粗暴的方式,把从低位到高位的每一位取出来然后存放在数组中,用两个循环分别遍历数组的奇数位和偶数位,判断每一位是不是符合要求。于是就有了下面的代码。


#include<iostream>
#include<vector>
using namespace std;

bool IsHaoShu(int N)
{
   vector<int> arr1;
   int n;
   while(N){
    n=N%10;
    arr1.push_back(n);
    N/=10;
   }
   int flag1=1,flag2=1;
   for(int i=0;i<=arr1.size()-1;i+=2)
   {
        if(arr1[i]%2==0)
        {
            flag1=0;
            break;
        }
   }
   for(int j=1;j<=arr1.size()-1;j+=2)
   {
      if(arr1[j]%2!=0)
      {
            flag2=0;
            break;
      }
   }
   if(flag1 && flag2)
   return true;
   else return false;
}

int main(){
    int N;
    cin>>N;
    int cnt=0;
    for(int k=1;k<=N;k++)
    {
        if(IsHaoShu(k))
        cnt++;
    }
    cout<<cnt;
}

简单粗暴,时间复杂度为O(NlogN)
后来了就看到一种每次在while循环里面可以判断我所判断的这一位就是是要满足偶数位性质还是奇数位性质。

int index=1;
while(x)
{
	int dight=x%10;
	if(dight % 2 != index % 2)
		return false;
	x /= 10;
	index++;
}

很巧妙的运用到了一个index，它模2是一个1，0，1，0的循环序列,刚好对应奇数位为奇数模2余1,偶数位为偶数模2余0。还有几种写法,就是把index++改为index=1-index或者index ^=1。
优化后的代码为

#include<iostream>
using namespace std;
bool IsHaoShu(int N)
{
    int index=1;
    while(N)
    {
        int dight=N%10;
        if(dight % 2!=index % 2)
        return false;
        N /=10;
        index++;
    }
    return true;
}


int main()
{
    int N,count=0;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        if(IsHaoShu(i))
        count++;
    }
    cout<<count;
}