统计特殊整数
难度:
标签:
题目描述
We call a positive integer special if all of its digits are distinct.
Given a positive integer n, return the number of special integers that belong to the interval [1, n].
Example 1:
Input: n = 20 Output: 19 Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
Input: n = 5 Output: 5 Explanation: All the integers from 1 to 5 are special.
Example 3:
Input: n = 135 Output: 110 Explanation: There are 110 integers from 1 to 135 that are special. Some of the integers that are not special are: 22, 114, and 131.
Constraints:
1 <= n <= 2 * 109
代码结果
运行时间: 45 ms, 内存: 16.0 MB
/*
思路：
1. 使用Java Streams简化遍历过程。
2. 使用stream的filter方法过滤特殊整数。
3. 检查一个数是否为特殊整数的方法是将其转换为字符串，并检查字符串中是否有重复的字符。
4. 统计所有特殊整数的数量并返回。
*/
import java.util.stream.IntStream;
public class SpecialIntegerCountStream {
public long countSpecialNumbers(int n) {
return IntStream.rangeClosed(1, n)
.filter(this::isSpecial)
.count();
}
private boolean isSpecial(int number) {
String str = String.valueOf(number);
int[] digits = new int[10];
for (char c : str.toCharArray()) {
int digit = c - '0';
if (digits[digit] != 0) {
return false;
}
digits[digit]++;
}
return true;
}
public static void main(String[] args) {
SpecialIntegerCountStream sics = new SpecialIntegerCountStream();
System.out.println(sics.countSpecialNumbers(20)); // 输出: 19
System.out.println(sics.countSpecialNumbers(5)); // 输出: 5
System.out.println(sics.countSpecialNumbers(135)); // 输出: 110
}
}解释
方法:
题解采用了数位动态规划的思想。首先，计算所有长度小于给定数字的特殊整数个数，然后计算长度等于给定数字的部分特殊整数。具体地，对于长度小于n的数，可以直接计算每个长度的特殊数字数量，例如长度为i的数字，其首位有9种选择(1-9)，其余位从剩下的9个数字中选(i-1)个数字排列。对于长度等于n的情况，从最高位到最低位逐位确定数字，并排除已经使用过的数字，使用排列计算剩余位的可能组合。如果在某一位发现重复使用数字，则剩余部分不再构成特殊整数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
数位动态规划的步骤中，如何精确计算长度小于n的特殊整数个数？特别是如何处理每个长度的首位和剩余位的选择与排列？
▷🦆
在处理长度等于n的数字时，为何要逐位检查并排除已使用过的数字？这种方法的正确性是如何保证的？
▷🦆
题解中提到，如果在逐位检查过程中发现重复使用数字，则返回当前计算结果。这种处理方式是否意味着可能遗漏某些符合条件的特殊整数？
▷