LeetCode 1012. 至少有 1 位重复的数字

Categories:

题目描述
思路分析
1. 解法一：数位 DP 计数（推荐）
相似题目

题目描述

✅ 1012. 至少有 1 位重复的数字

思路分析

解法一：数位 DP 计数（推荐）

核心思路：

先统计 [1, n] 中无重复数字的个数，再用 n 减去它得到答案。

用数位 DP，状态为位置、已使用数字集合、是否受限。

受限为 false 的状态可以记忆化，避免重复计算。

复杂度分析：

时间复杂度：O(10 * 2^10)，数位 DP 状态数量有限。

空间复杂度：O(10 * 2^10)，记忆化缓存。

import java.util.*;

class Solution {
    public int numDupDigitsAtMostN(int n) {
        return n - (countNoRepeat(n) - 1);
    }

    private int countNoRepeat(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int len = digits.length;
        int[][] memo = new int[len][1 << 10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(digits, 0, 0, true, memo);
    }

    private int dfs(char[] digits, int pos, int mask, boolean tight, int[][] memo) {
        if (pos == digits.length) {
            return 1;
        }
        if (!tight && memo[pos][mask] != -1) {
            return memo[pos][mask];
        }

        int limit = tight ? digits[pos] - '0' : 9;
        int res = 0;
        for (int d = 0; d <= limit; d++) {
            int bit = 1 << d;
            if (mask == 0 && d == 0) {
                res += dfs(digits, pos + 1, 0, tight && d == limit, memo);
            } else if ((mask & bit) == 0) {
                res += dfs(digits, pos + 1, mask | bit, tight && d == limit, memo);
            }
        }

        if (!tight) {
            memo[pos][mask] = res;
        }
        return res;
    }
}

import "strconv"

func numDupDigitsAtMostN(n int) int {
    return n - (countNoRepeat(n) - 1)
}

func countNoRepeat(n int) int {
    digits := []byte(strconv.Itoa(n))
    memo := make([][]int, len(digits))
    for i := range memo {
        memo[i] = make([]int, 1<<10)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return dfsNoRepeat(digits, 0, 0, true, memo)
}

func dfsNoRepeat(digits []byte, pos int, mask int, tight bool, memo [][]int) int {
    if pos == len(digits) {
        return 1
    }
    if !tight && memo[pos][mask] != -1 {
        return memo[pos][mask]
    }

    limit := 9
    if tight {
        limit = int(digits[pos] - '0')
    }

    res := 0
    for d := 0; d <= limit; d++ {
        bit := 1 << d
        if mask == 0 && d == 0 {
            res += dfsNoRepeat(digits, pos+1, 0, tight && d == limit, memo)
        } else if mask&bit == 0 {
            res += dfsNoRepeat(digits, pos+1, mask|bit, tight && d == limit, memo)
        }
    }

    if !tight {
        memo[pos][mask] = res
    }
    return res
}

相似题目

题目	难度	考察点
357. 计算各个位数不同的数字个数	中等	数位 DP
233. 数字 1 的个数	困难	数位 DP
902. 最大为 N 的数字组合	困难	数位 DP
1012. 至少有 1 位重复的数字	困难	数位 DP
1067. 范围内的数字计数	困难	数位 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/51039230