请完成函数cal(int L, int R)功能,该函数统计给定 范围[L, R]的所有整数中回文数的个数(100≤L≤R≤1000000)。 回文数是指将各位数字反向排列所得自然数与原数相同. 例如,[100,130]范围有3个数101、111、121满足要求。
时间: 2023-12-14 07:39:25 浏览: 36
可以先写一个函数判断一个数是否是回文数,然后在给定范围内遍历每一个数,统计回文数的个数。
代码如下:
```c++
bool isPalindrome(int n) {
int temp = n, reversed = 0;
while (temp > 0) {
reversed = reversed * 10 + temp % 10;
temp /= 10;
}
return n == reversed;
}
int cal(int L, int R) {
int count = 0;
for (int i = L; i <= R; ++i) {
if (isPalindrome(i)) {
++count;
}
}
return count;
}
```
需要注意的是,上面的代码时间复杂度为 $O(n \log n)$,其中 $n=R-L+1$。如果要进一步优化时间复杂度,可以考虑使用回文数的性质,只遍历一半的数即可。这样时间复杂度为 $O(\log n)$。但是对于本题给定的数据范围,上面的代码已经足够快了。