Count Special Integers in Java

2025年5月8日 | 阅读 7 分钟

该问题的首要目标是确定在给定数字 n 的范围内，有多少个正整数包含所有不重复的数字，也就是说，数字中没有任何数字出现一次以上。与 11345 不同，11345 不是一个唯一的数字，因为数字 1 重复出现；而 12345 是一个唯一的数字，因为它的每个数字都是唯一的。

为了计算这个值，我们必须只计算那些满足数字唯一性要求的整数，并考虑从 1 到 n 的所有整数。由于是正整数，必须记住 0 不能是任何唯一数字的第一位数字。

示例 1

输入

int n = 100

输出

特殊数字的总数为 90

解释

给定数字为 100，因为它包含重复数字。在 1 到 100 的范围内，像 11、22、33 等数字都不是特殊的。其中有九十个是特殊整数。

示例 2

输入

int n = 50

输出

特殊数字的总数为 45

解释

在 1 到 50 之间有 45 个特殊整数，尽管像 11、22 和 33 这样带有重复数字的数字不是特殊的。

示例 3

输入

int n = 50

输出

特殊数字的总数为 45

解释

在 1 到 500 的唯一整数中，不重复数字的数字有 420 个。在这 420 个唯一整数中，像 121、212 和 232 这样的数字不是唯一的。

方法：使用动态规划

该程序通过使用动态规划 (DP) 和一个 3D DP 表 (dp[pos][num][temp]) 来优化特殊数字的计算。通过 temp 变量，它有效地利用位掩码跟踪数字的使用情况，其中每个位表示该数字是否已被使用。num 变量显示新的计算是否符合原始数字的严格约束。递归调用与记忆化结合，通过确保重叠子问题只被解决一次，保存在 dp 表中，然后重复使用，从而减少了不必要的计算。这种方法结合了递归、缓存和状态表示，以最大化性能。

该算法通过使用记忆化来确保预先计算的状态得到最佳重用，从而降低了时间复杂度。该代码处理边缘情况（例如前导零和边界处的数字）展示了一种处理带有约束的组合问题的健壮且准确的方法。

算法

步骤 1： 输入数字 N 的各位数字应被提取并按相反顺序存储在位置列表中。

步骤 2： 确定位置大小，并将大小为 [size][2][(1<<10)-1] 的 3D DP 表 dp 的初始值设置为 null。

步骤 3： 应用递归函数 fillDp(pos, num, temp, flag) 进行填充

步骤 3.1： 对于基本情况：如果所有数字都已处理完毕且 pos 等于 size，则返回 1。

步骤 3.2： 对于记忆化：如果 dp[pos][num][temp] 不为 null，则返回存储的结果。

步骤 3.3： 对于初始化：将 dp[pos][num][temp] 设置为零。

步骤 4： 如果 num == 1，则开始迭代从 0 到 position.get(pos) 的数字 i。

步骤 4.1： 检查临时位掩码，看 'i' 是否已被使用。

步骤 4.2： 当 i 等于 position 时，下一个状态（紧或松）由是否基于 i 等于 position.get(pos) 来更新临时位掩码来决定。

步骤 4.3： 使用标志来处理前导零等边缘情况。

步骤 5： 如果 num == 0，则开始迭代从 0 到 9 的数字 i。

步骤 5.1： 检查临时位掩码，看 i 是否已被使用。

步骤 5.2： 在更新临时位掩码以包含 i 并处理下一个状态时，使用标志来处理前导零。

步骤 6： 返回计算出的值，并将其存储在 dp[pos][num][temp] 中。

步骤 7： 要用初始状态启动递归，请调用 fillDp(0, 1, 0, false)。

步骤 8： 要消除数字 0，请从结果中减去 1。

步骤 9： 应打印特殊数字的数量。

实施

文件名： DPSPecialCount.java

import java.util.*; 
import java.io.*;
public class DPSPecialCount
{
    public static void main(String[] args) 
    {
        SpecialCountDP obj = new SpecialCountDP();
        int N = 100;
        int res = obj.SpecialNumbers(N);
        System.out.println("The Count of special numbers is: " + res);
    }
}
class SpecialCountDP 
{
    Integer[][][] dp;
    ArrayList<Integer> position = new ArrayList<>();
    int size;
    public int SpecialNumbers(int N) 
    {
        // Break the number down into its component digits
        // and store them in reverse order.
        while (N != 0) 
        {
            position.add(0, N % 10);
            N = N / 10;
        }
        // Calculate the number's size.
        size = position.size();
        // Initialize and create the dp array
        dp = new Integer[size][2][(1 << 10) - 1];
        // compute the recursion
        return fillDp(0, 1, 0, false) - 1;
    }
    public int fillDp(int pos, int num, int temp, boolean flag) 
    {
        // Base case: if the numbers reach their end
        if (pos == size) 
        {
            return 1;
        }
        // Return the cached result if it has already been calculated.
        if (dp[pos][num][temp] != null)
        {
            return dp[pos][num][temp];
        }
        // Set the dp value for this state to its initial value.
        dp[pos][num][temp] = 0;
        if (num == 1) 
        {
            // Handle with the situation in which 
            //The number is closely confined.
            for (int i = 0; i <= position.get(pos); i++) 
            {
                // If the digit "i" has already been used 
                // (as indicated by temp), skip it.
                if ((temp & (1 << i)) > 0) 
                {
                    continue;
                }
                int newTemp = (temp | (1 << i)); // Updating the ith digit to include
                if (i == position.get(pos)) 
                {
                    if (i != 0) 
                    {
                        // For strict constraint (num = 1), proceed 
                        // to the next position if i is not zero.
                        dp[pos][num][temp] += fillDp(pos + 1, 1, newTemp, true);
                    } 
                    else 
                    {
                        if (flag) 
                        {
                            // Use the tight constraint and newTemp 
                            // if leading zeros are permitted.
                            dp[pos][num][temp] += fillDp(pos + 1, 1, newTemp, true);
                        } 
                        else 
                        {
                            // If no leading zeros are allowed, retain the
                            // temp and continue with tight constraint.
                            dp[pos][num][temp] += fillDp(pos + 1, 1, temp, false);
                        }
                    }
                } 
                else 
                {
                    // Proceed with the newTemp without strict constraint
                    // (num = 0) if i is not zero.
                    if (i != 0) 
                    {
                        dp[pos][num][temp] += fillDp(pos + 1, 0, newTemp, true);
                    } 
                    else 
                    {
                        if (flag) 
                        {
                            // Proceed with the newTemp and  modified constraint, allowing leading zeros.
                            dp[pos][num][temp] += fillDp(pos + 1, 0, newTemp, true);
                        } 
                        else 
                        {
                            dp[pos][num][temp] += fillDp(pos + 1, 0, temp, false);
                        }
                    }
                }
            }
        } 
        else if (num == 0) 
        {
            for (int i = 0; i <= 9; i++) 
            {
                // If digit i is already in use (as shown by temp), skip.
                if ((temp & (1 << i)) > 0)
                {
                    continue;
                }
                // update the temp value to include i
                int newTemp = (temp | (1 << i));
                if (i != 0) 
                {
                    // Use the newTemp to move on to the next position
                    // if i is not zero.
                    dp[pos][num][temp] += fillDp(pos + 1, 0, newTemp, true);
                } 
                else 
                {
                    if (flag) 
                    {
                        // Proceed with the newTemp after allowing leading zeros.
                        dp[pos][num][temp] += fillDp(pos + 1, 0, newTemp, true);
                    } 
                    else 
                    {
                        // Keep the temp, no leading zeros.
                        dp[pos][num][temp] += fillDp(pos + 1, 0, temp, false);
                    }
                }
            }
        }
        return dp[pos][num][temp];
    }
}   

输出

 
The Count of special numbers is: 90

方法：使用 DFS（深度优先搜索）

通过使用位掩码来维护唯一数字约束，该算法使用带递归的深度优先搜索 (DFS) 一位一位地构建数字。所有有效的“特殊数字”都通过这些标准在一个列表中预先计算好，这个列表是由一个静态块生成的。位掩码表示数字的使用状态，防止其被重复使用。通过对预先计算好的列表进行二分搜索，可以高效地查询出给定输入值以下的数字数量。该方法利用了先进的数据结构和算法来最大化生成和查询的效率。

文件名： DFSSpecialCountIntegers.java

import java.util.*;
import java.io.*;
public class DFSSpecialCountIntegers 
{
    private static final List<Long> val = new ArrayList<>();
    static 
    {
        // Generate all special numbers using DFS
        for (int i = 1; i <= 10; i++) 
        {
            DFS(0L, 0, i, 2000000000, 0);   
        }
    }
    public int SpecialNumbers(int N) 
    {
        // Find the index of the largest special number <= n
        int index = Collections.binarySearch(val, 0L + N);
        if (index < 0) return -(index + 1);
        return index + 1;
    }
    private static void DFS(long value, int index, int length, int max, int mask) 
    {
        // Base case: if the number length equals the target length
        if (index == length) 
        {
            if (value <= max && value > 0) 
            {
                val.add(value); // Add valid numbers to the list
            }
            return;
        }
        // Iterate through digits and choose unused ones
        for (int i = 0; i <= 9; i++)
        {
            if ((mask & (1 << i)) == 0) 
            { // Check if the digit is unused
                if (value == 0 && i == 0) 
                {
                    continue;
                } // Skip leading zeros
                DFS(value * 10 + i, index + 1, length, max, mask ^ (1 << i)); 
            }   
        }
    }
    public static void main(String[] args) 
    {
        DFSSpecialCountIntegers obj = new DFSSpecialCountIntegers();
        int n = 100;
        int res = obj.SpecialNumbers(n);
        System.out.println("The count of special numbers is: " + res);
    }
}   

输出

 
The count of special numbers is: 90

下一个主题Java 中使用 while 循环的阶乘程序

Count Special Integers in Java

方法：使用动态规划

实施

方法：使用 DFS（深度优先搜索）

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Count Special Integers in Java

方法：使用动态规划

实施

方法：使用 DFS（深度优先搜索）

相关帖子

DecimalStyle getAvailableLocales() Method in Java with Examples

如何在 Java 中添加启动画面

Java 中的星形数

IsoChronology eras() method in Java with Examples

Java 中的菱形图案

Java 中传递和返回对象

如何在 Java 中调用抽象类的具体方法

Java 中 Final 方法重载 | 可以重载 Final 方法吗？

如何生成 JVM 堆内存转储

ChocolatesByNumbers Problem in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器