思路
按位枚举+分类讨论(思路完全等同于y总,这里不再赘述)
写作动机
由于觉得这道题按位枚举的过程中,左右两侧数的计算非常容易出错,且夹杂着一些边界问题。导致清楚了思路后,还是很难快速的写出代码AC,如果面试出到这种题会因为边界情况直接爆炸。于是去找了找有没有写起来比较直观的代码。
最后在LeetCode中找到了剑指offer的一道题,是这道题的简化版。里面有一位大佬写的代码非常简洁优雅。于是按照同样的思路,修改了一下用于这道题。详细请看注释。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int count(int n, int x) {
if(n < 1) return 0;
// dig 目前枚举到的位数,个位为1,十位为10,百位为100,...以此类推
// hi 左侧数,起始为n / 10,之后每次除10,直至为0。 例如12345,hi依次为1234,123,12,1,0
// cur 当前枚举位的值,起始为n % 10,之后每次更新为hi % 10。 例如12345,cur依次为5,4,3,2,1
// lo 右侧数,起始为0,之后每次加上当前的枚举位的值,即cur * dig。 例如12345,lo依次为0,5,45,345,2345
int dig = 1, res = 0;
int hi = n / 10, cur = n % 10, lo = 0;
while(hi || cur) { // 结束标志:hi等于0,并且cur=0,此时最高位也枚举完毕
if(x == 0 && hi == 0) break; // 当计算0出现次数时,是不需要考虑最高位的,hi等于0意味着枚举到了最高位。
// 0 ~ abc - 1情况
if(x) res += hi * dig; // 最高位时,hi = 0,hi * dig = 0,所以无需特判
else res += (hi - 1) * dig; // 之前的break保证了这里hi一定不为0,放心-1
// abc情况
if(cur > x) res += dig;
else if(cur == x) res += lo + 1;
lo += cur * dig; // 这里的更新顺序要保证lo先于dig
dig *= 10;
cur = hi % 10;
hi /= 10;
}
return res;
}
int main() {
int a, b;
while(cin >> a >> b, a || b) {
if(a > b) swap(a, b);
for(int i = 0; i < 10; i ++)
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}