统计对称整数的数目
难度:
标签:
题目描述
You are given two positive integers low and high.
An integer x consisting of 2 * n digits is symmetric if the sum of the first n digits of x is equal to the sum of the last n digits of x. Numbers with an odd number of digits are never symmetric.
Return the number of symmetric integers in the range [low, high].
Example 1:
Input: low = 1, high = 100 Output: 9 Explanation: There are 9 symmetric integers between 1 and 100: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
Example 2:
Input: low = 1200, high = 1230 Output: 4 Explanation: There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, and 1230.
Constraints:
1 <= low <= high <= 104
代码结果
运行时间: 48 ms, 内存: 16.4 MB
/*
* 题目思路：
* 使用 Java Stream 遍历范围内的每个数字，检查其是否满足对称整数的条件。
* 过滤出对称整数并计数。
*/
import java.util.stream.IntStream;
public class SymmetricIntegersStream {
public static int countSymmetricIntegers(int low, int high) {
return (int) IntStream.rangeClosed(low, high)
.filter(SymmetricIntegersStream::isSymmetric)
.count();
}
private static boolean isSymmetric(int num) {
String s = String.valueOf(num);
int len = s.length();
if (len % 2 != 0) return false; // 必须是偶数位
int half = len / 2;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < half; i++) {
sum1 += s.charAt(i) - '0';
sum2 += s.charAt(i + half) - '0';
}
return sum1 == sum2;
}
public static void main(String[] args) {
System.out.println(countSymmetricIntegers(1, 100)); // 输出: 9
System.out.println(countSymmetricIntegers(1200, 1230)); // 输出: 4
}
}解释
方法:
该题解通过预计算所有可能的对称整数并存储在一个列表中。然后，它遍历这个列表，统计在给定的区间 [low, high] 内的对称整数的数量。这个方法避免了对每个数字进行检查，而是直接查找预定义的有效值。
时间复杂度:
O(m) ，其中 m 是预定义对称整数列表的长度。
空间复杂度:
O(m)，其中 m 是预定义对称整数列表的长度。
代码细节讲解
🦆
在预计算对称整数时，如何确保所有可能的2 * n位对称整数都被生成并被考虑在内？
▷🦆
题解中提到的列表`fac`是否包含了所有小于10000的对称整数？如果没有，如何处理那些非列出的对称整数？
▷🦆
对于比较数字是否位于`low`和`high`之间，为什么选择使用遍历列表而不是其他搜索技术，比如二分查找？
▷🦆
如果`low`和`high`的数值非常接近而对称整数列表`fac`很大，这种方法的效率如何？是否有更优化的方法来处理这种情况？
▷