统计各位数字之和为偶数的整数个数
难度:
标签:
题目描述
代码结果
运行时间: 28 ms, 内存: 16.5 MB
/*
* 题目思路:
* 1. 使用Java Stream API来实现。
* 2. 我们用IntStream生成从1到num的整数流。
* 3. 通过过滤函数筛选出各位数字之和为偶数的数字。
* 4. 使用count()方法获取满足条件的数字的数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int countEven(int num) {
return (int) IntStream.rangeClosed(1, num)
.filter(this::isSumEven)
.count();
}
// 计算数字各位之和是否为偶数
private boolean isSumEven(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum % 2 == 0;
}
}
解释
方法:
本题解采用数学和模拟的方法来解决问题。首先,计算出小于当前十位数(num//10)的整数中,满足各位数字之和为偶数的数字数量。对于每个十位数区间,例如0-9, 10-19等,其中有一半的数字的各位数字之和是偶数。因此,可以直接计算出直到最近的十位数的满足条件的数字总数。接着处理最后一个不完整的十位区间的数字,即从最近的十位数到num的数字,逐个检查这些数字,统计其中满足各位数字之和为偶数的数量。为此,计算从0开始到最近的十位数的数字之和是否为偶数,然后根据最后一位数字的奇偶性调整计数结果。
时间复杂度:
O(log(num))
空间复杂度:
O(1)
代码细节讲解
🦆
在计算各位数字之和时,你是如何确定每十位区间内恰好有一半的数字的各位数字之和为偶数的?
▷🦆
为什么在初始化计数器ans设置时,要使用`num // 10 * 5 - 1`而不是`num // 10 * 5`?
▷🦆
在计算不完整的十位区间数字时,`ans += (num % 10 + 2 - (s & 1)) >> 1`这个表达式是如何工作的,特别是`(s & 1)`部分是什么意思?
▷