Created time
Mar 19, 2023 05:54 PM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
题目描述：
给定正整数n，求在[1, n]范围内有至少1位重复数字的正整数的个数。
思路解析：
我们可以通过枚举每个数字，并判断其是否包含重复数字来解决此问题。但是，这个方法的时间复杂度为O(nlogn)，不足以通过本题。因此，我们需要寻找更高效的解决方法。
我们可以使用数位DP的方法来解决这个问题。数位DP是一种通过动态规划来解决数字问题的方法。在这个问题中，我们可以使用一个状态数组dp[i][j][k][l]表示位数为i，j表示是否已经达到上界n，k表示是否存在重复数字，l表示前缀数字的状态。具体来说，当我们枚举数字时，我们可以在dp数组中累积计数器，以计算具有至少一个重复数字的数字的数量。
好的，让我详细解释一下数位DP的思路。
我们可以从高位到低位地考虑每个数字。假设我们现在要处理第i位上的数字，我们可以定义一个表示当前数字状态的变量state，它表示前i-1位数字的状态。如果这些位中没有重复数字，state的值为0，否则为1。
现在，我们要计算第i位数字的贡献，即在[0,9]范围内有多少个数字包含了至少一个重复的数字。假设当前的上界为n，则我们可以分为以下几种情况：
- 当前数字已经达到上界n，即j=1。此时，我们只需要考虑前缀数字是否存在重复数字，因为我们不能选取超出上界的数字。如果前缀数字中没有重复数字，则当前数字可以取[0,9]中的任意一个数字；否则，当前数字只能取前缀数字中出现过的数字。
- 当前数字还没有达到上界n，即j=0。此时，我们可以考虑当前数字是否会使得前缀数字出现重复。如果前缀数字中已经有了与当前数字相同的数字，则当前数字只能取0；否则，当前数字可以取[0,9]中的任意一个数字。
我们可以使用一个三维数组dp[i][j][state]来表示在当前位数为i、是否达到上界为j、前i-1位数字的状态为state的情况下，能够组成的具有至少1位重复数字的数字的数量。根据上述分析，我们可以得到状态转移方程：
dp[i][j][state] = sum(dp[i-1][j or (digit == n)][state or (1<<digit)])
其中，sum表示对所有满足条件的digit进行累加。具体来说，我们可以枚举所有的[0,9]中的数字，并根据上述讨论的情况计算出当前数字的贡献，然后将其加入到dp[i][j][state]中。
最终的答案就是dp[n][1][0]，表示在位数为n、达到上界为n、前n-1位数字中没有重复数字的情况下，能够组成的具有至少1位重复数字的数字的数量。
以下是使用Go语言实现的代码：
```
func countDupNums(n int) int { // 定义dp数组 dp := make([][][]int, 10) for i := range dp { dp[i] = make([][]int, 2) for j := range dp[i] { dp[i][j] = make([]int, 1<<10) } }
// 初始化dp数组 for i := 1; i <= 9; i++ { dp[1][0][1<<i] = 1 // 第一位数字可以取[1,9]中的任意一个数字 }
// 计算dp数组 for i := 2; i <= n; i++ { for j := 0; j <= 1; j++ { for state := 0; state < 1<<10; state++ { for digit := 0; digit <= 9; digit++ { if j == 0 && digit > i { // 当前数字已经超出上界n，直接跳过 break } if state&(1<<digit) != 0 { // 前缀数字中已经出现过当前数字，直接跳过 continue } if j == 1 || digit < n { dp[i][1][state|(1<<digit)] += dp[i-1][j][state] } else { dp[i][0][state|(1<<digit)] += dp[i-1][j][state] } } } } }
// 计算答案 ans := 0 for state := 1; state < 1<<10; state++ { if dp[n][1][state] > 0 { ans += dp[n][1][state] } } return ans}
```
我们首先定义一个三维数组dp，其中dp[i][j][state]表示在当前位数为i、是否达到上界为j、前i-1位数字的状态为state的情况下，能够组成的具有至少1位重复数字的数字的数量。然后，我们初始化dp数组的第一位，即dp[1]，因为在只有1位数字的情况下，满足条件的数字只有[1,9]中的数字。
接下来，我们使用三层循环，分别遍历位数、是否达到上界和前缀数字状态，然后枚举当前数字，计算它的贡献，并将其加入到dp数组中。最后，我们遍历整个dp数组，累加所有满足条件的数字的数量，得到最终的答案。
需要注意的是，在计算dp数组的过程中，我们需要根据上界n的大小来判断当前数字是否已经超出上界。如果超出上界，则直接跳过。此外，在计算贡献时，我们需要判断前缀数字中是否已经出现过当前数字，如果出现过，则直接跳过。
希望这份代码能够帮到你。