class Solution {
public:
int countSpecialNumbers(int n) {
}
};
2376. 统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20 输出：19 解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5 输出：5 解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135 输出：110 解释：从 1 到 135 总共有 110 个整数是特殊整数。 不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 109原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 2.1 MB, 提交时间: 2024-09-20 09:06:34
impl Solution {
pub fn count_special_numbers(n: i32) -> i32 {
fn dfs(i: usize, mask: usize, is_limit: bool, is_num: bool, s: &[u8], memo: &mut Vec<Vec<i32>>) -> i32 {
if i == s.len() {
return if is_num { 1 } else { 0 }; // is_num 为 true 表示得到了一个合法数字
}
if !is_limit && is_num && memo[i][mask] != -1 {
return memo[i][mask]; // 之前计算过
}
let mut res = 0;
if !is_num { // 可以跳过当前数位
res = dfs(i + 1, mask, false, false, s, memo);
}
// 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
let up = if is_limit { s[i] - b'0' } else { 9 };
// 枚举要填入的数字 d
// 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
let low = if is_num { 0 } else { 1 };
for d in low..=up {
if (mask >> d & 1) == 0 { // d 不在 mask 中，说明之前没有填过 d
res += dfs(i + 1, mask | (1 << d), is_limit && d == up, true, s, memo);
}
}
if !is_limit && is_num {
memo[i][mask] = res; // 记忆化
}
return res;
}
let s = n.to_string();
let s = s.as_bytes();
let mut memo = vec![vec![-1; 1 << 10]; s.len()]; // -1 表示没有计算过
return dfs(0, 0, true, false, &s, &mut memo);
}
}
javascript 解法, 执行用时: 67 ms, 内存消耗: 53.6 MB, 提交时间: 2024-09-20 09:06:20
/**
* @param {number} n
* @return {number}
*/
var countSpecialNumbers = function(n) {
const s = n.toString();
const m = s.length;
const memo = Array.from({ length: m }, () => Array(1 << 10).fill(-1)); // -1 表示没有计算过
function dfs(i, mask, isLimit, isNum) {
if (i === m) {
return isNum ? 1 : 0; // is_num 为 true 表示得到了一个合法数字
}
if (!isLimit && isNum && memo[i][mask] !== -1) {
return memo[i][mask]; // 之前计算过
}
let res = 0;
if (!isNum) { // 可以跳过当前数位
res += dfs(i + 1, mask, false, false);
}
// 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
const up = isLimit ? +s[i] : 9;
// 枚举要填入的数字 d
// 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
for (let d = isNum ? 0 : 1; d <= up; d++) {
if ((mask >> d & 1) === 0) { // d 不在 mask 中，说明之前没有填过 d
res += dfs(i + 1, mask | (1 << d), isLimit && d === up, true);
}
}
if (!isLimit && isNum) {
memo[i][mask] = res; // 记忆化
}
return res;
}
return dfs(0, 0, true, false);
};
cpp 解法, 执行用时: 16 ms, 内存消耗: 11.5 MB, 提交时间: 2024-09-20 09:06:06
class Solution {
public:
int countSpecialNumbers(int n) {
string s = to_string(n);
int m = s.length();
vector<vector<int>> memo(m, vector<int>(1 << 10, -1)); // -1 表示没有计算过
auto dfs = [&](auto&& dfs, int i, int mask, bool is_limit, bool is_num) -> int {
if (i == m) {
return is_num; // is_num 为 true 表示得到了一个合法数字
}
if (!is_limit && is_num && memo[i][mask] != -1) {
return memo[i][mask]; // 之前计算过
}
int res = 0;
if (!is_num) { // 可以跳过当前数位
res = dfs(dfs, i + 1, mask, false, false);
}
// 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
int up = is_limit ? s[i] - '0' : 9;
// 枚举要填入的数字 d
// 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
for (int d = is_num ? 0 : 1; d <= up; d++) {
if ((mask >> d & 1) == 0) { // d 不在 mask 中，说明之前没有填过 d
res += dfs(dfs, i + 1, mask | (1 << d), is_limit && d == up, true);
}
}
if (!is_limit && is_num) {
memo[i][mask] = res; // 记忆化
}
return res;
};
return dfs(dfs, 0, 0, true, false);
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 41.7 MB, 提交时间: 2024-09-20 09:05:40
class Solution {
public int countSpecialNumbers(int n) {
char[] s = Integer.toString(n).toCharArray();
int[][] memo = new int[s.length][1 << 10];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
return dfs(0, 0, true, false, s, memo);
}
private int dfs(int i, int mask, boolean isLimit, boolean isNum, char[] s, int[][] memo) {
if (i == s.length) {
return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字
}
if (!isLimit && isNum && memo[i][mask] != -1) {
return memo[i][mask]; // 之前计算过
}
int res = 0;
if (!isNum) { // 可以跳过当前数位
res = dfs(i + 1, mask, false, false, s, memo);
}
// 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
int up = isLimit ? s[i] - '0' : 9;
// 枚举要填入的数字 d
// 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
for (int d = isNum ? 0 : 1; d <= up; d++) {
if ((mask >> d & 1) == 0) { // d 不在 mask 中，说明之前没有填过 d
res += dfs(i + 1, mask | (1 << d), isLimit && d == up, true, s, memo);
}
}
if (!isLimit && isNum) {
memo[i][mask] = res; // 记忆化
}
return res;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 6 MB, 提交时间: 2023-08-22 15:02:20
func countSpecialNumbers(n int) (ans int) {
s := strconv.Itoa(n)
m := len(s)
memo := make([][1 << 10]int, m)
for i := range memo {
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var f func(int, int, bool, bool) int
f = func(i, mask int, isLimit, isNum bool) (res int) {
if i == m {
if isNum {
return 1 // 得到了一个合法数字
}
return
}
if !isLimit && isNum {
p := &memo[i][mask]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
if !isNum { // 可以跳过当前数位
res += f(i+1, mask, false, false)
}
d := 0
if !isNum {
d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
}
up := 9
if isLimit {
up = int(s[i] - '0') // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
}
for ; d <= up; d++ { // 枚举要填入的数字 d
if mask>>d&1 == 0 { // d 不在 mask 中
res += f(i+1, mask|1<<d, isLimit && d == up, true)
}
}
return
}
return f(0, 0, true, false)
}
python3 解法, 执行用时: 380 ms, 内存消耗: 21.5 MB, 提交时间: 2022-09-19 17:23:39
class Solution:
"""
将 n 转换成字符串 s，定义 f(i, mask, isLimit, isNum) 表示构造从左往右第 i位及其之后数位的合法方案数，其余参数的含义为：
mask 表示前面选过的数字集合，换句话说，第 i 位要选的数字不能在 mask 中。
isLimit 表示当前是否受到了 n 的约束。若为真，则第 i 位填入的数字至多为 s[i]，否则可以是 9。如果在受到约束的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。
isNum 表示 i 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；若为真，则必须填数字，且要填入的数字可以从 0 开始。
"""
def countSpecialNumbers(self, n: int) -> int:
s = str(n)
@cache
def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
if i == len(s):
return int(is_num)
res = 0
if not is_num: # 可以跳过当前数位
res = f(i + 1, mask, False, False)
up = int(s[i]) if is_limit else 9
for d in range(0 if is_num else 1, up + 1): # 枚举要填入的数字 d
if mask >> d & 1 == 0: # d 不在 mask 中
res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
return res
return f(0, 0, True, False)