Find Total Numbers with No Repeated Digits in A Range in Java

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

查找范围内没有重复数字的总数的问题涉及识别每个数字仅出现一次的数字。它有助于分析数字属性，并经常用于组合数学。这个概念对于解决与数字唯一性和优化相关的求解很有用。

示例 1

输入 5 15

输出 9

说明： 范围 5 到 15 中没有重复数字的数字是：5、6、7、8、9、10、12、13、14、15。

示例 2

输入 20 30

输出 9

说明： 范围 20 到 30 中没有重复数字的数字是：20、21、23、24、25、26、27、28、29。

方法：暴力法

暴力破解方法包括直接检查所有可能的解决方案或情况，而无需任何优化。它通常使用简单、直接的逻辑来解决问题，但对于大型输入而言，时间复杂度通常很高。

算法

步骤 1： 设置下界和上界，并将计数器 count 初始化为 0。

步骤 2： 定义 hasRepeatedDigits(num) 以使用数字跟踪数组检查数字是否包含重复数字。

步骤 3： 循环遍历从 lower 到 upper 的数字。

步骤 4： 如果数字没有重复的数字，则递增 count。

步骤 5： 打印给定范围内具有唯一数字的数字的数量。

实施

文件名：BruteForceUniqueDigits.java

public class BruteForceUniqueDigits {
    // Method to check if a number has repeated digits
    private static boolean hasRepeatedDigits(int num) {
        // Array to track if a digit has been seen (index 0-9 for digits 0-9)
        boolean[] digitSeen = new boolean[10]; 
        // Loop until the number becomes 0
        while (num > 0) {
            int digit = num % 10; // Extract the last digit of the number
            if (digitSeen[digit]) { // Check if this digit was already seen
                return true; // Return true if a digit is repeated
            }
            digitSeen[digit] = true; // Mark the digit as seen
            num /= 10; // Remove the last digit from the number
        }
        return false; // Return false if no digits are repeated
    }
    public static void main(String[] args) {
        // Define the default range for the numbers to be checked
        int lower = 10; // Lower bound of the range
        int upper = 30; // Upper bound of the range
        int count = 0; // Initialize a counter to keep track of numbers with unique digits
        // Loop through all numbers in the range [lower, upper]
        for (int i = lower; i <= upper; i++) {
            if (!hasRepeatedDigits(i)) {
                count++; // Increment the counter if the number has unique digits
            }
        }
        // Print the range being checked
        System.out.println("Range: " + lower + " to " + upper);
        // Print the total count of numbers with unique digits in the given range
        System.out.println("Total numbers with no repeated digits: " + count);
    }
}   

输出

 
Range: 10 to 30
Total numbers with no repeated digits: 19

方法：前缀和法

前缀和法涉及预先计算元素范围的累积和（或计数），以便能够进行高效的范围查询。

算法

步骤 1： 定义一个 hasRepeatedDigits() 方法，使用数组检查数字是否具有重复数字。

步骤 2： 创建一个前缀数组来存储 up to maxRange 的唯一数字的累积计数。

步骤 3： 通过对没有重复数字的数字加 1 来填充前缀数组，使用 hasRepeatedDigits。

步骤 4： 对于范围 [L, R]，将唯一数字的计数计算为 prefix[R] - prefix[L - 1]。

步骤 5： 打印范围以及该范围内唯一数字的总数。

实施

文件名：EfficientUniqueDigits.java

public class EfficientUniqueDigits {
    // Method to check if a number has repeated digits
    private static boolean hasRepeatedDigits(int num) {
        boolean[] digitSeen = new boolean[10]; 
        while (num > 0) { 
            int digit = num % 10; 
            if (digitSeen[digit]) { // Check if the digit has already been seen
                return true; // If a digit is repeated, return true
            }
            digitSeen[digit] = true; // Mark the digit as seen
            num /= 10; // Remove the last digit from the number
        }
        return false; // If no digits are repeated, return false
    }
    public static void main(String[] args) {
        int maxRange = 1000;
        int[] prefix = new int[maxRange + 1]; // Create a prefix array to store cumulative counts of unique digit numbers
        // Precompute the prefix array
        for (int i = 1; i <= maxRange; i++) { 
            // If the current number has no repeated digits, add 1 to the previous prefix value
            prefix[i] = prefix[i - 1] + (hasRepeatedDigits(i) ? 0 : 1); 
        }
        // Example Queries
        int L = 10; // Define the lower bound of the range
        int R = 30; // Define the upper bound of the range
        // Calculate the result for the given range using the prefix array
        int result = prefix[R] - prefix[L - 1]; // Subtract the prefix of L-1 from R to get the count in the range [L, R]
        // Print the range being queried
        System.out.println("Range: " + L + " to " + R);
        // Print the total count of numbers with unique digits in the range
        System.out.println("Total numbers with no repeated digits: " + result);
    }
}   

输出

 
Range: 10 to 30
Total numbers with no repeated digits: 19

动态规划

该方法使用带记忆化的动态规划，通过递归地探索所有数字位置来有效地计算具有唯一数字的数字。它使用位掩码跟踪可用数字，并处理前导零和每个数字的紧凑约束。

算法

步骤 1： 创建并初始化一个 4D 记忆化数组来存储中间结果。

步骤 2： 实现一个递归函数，根据位置、紧凑约束和可用数字来计算具有唯一数字的数字。

步骤 3： 如果所有数字都已处理，则为有效数字返回 1。

步骤 4： 循环遍历可能的数字，并进行递归调用以计算有效数字的计数。

步骤 5： 通过从 [0, upperBound] 的结果中减去 [0, lowerBound-1] 的结果来计算范围内具有唯一数字的数字的计数。

实施

文件名：UniqueDigitCounter.java

import java.util.*; // Importing the required package for utility classes like Arrays
class UniqueDigitCounter {
    // 4D DP array to store intermediate results
    static int[][][][] memo = new int[11][2][(1 << 10)][2];
    // Recursive function to count numbers with unique digits
    static int countDistinctDigits(int position, int isTight, int availableMask, int leadingZeroAllowed, String number) {
        // Base case: If we have processed all digits of the number
        if (position == number.length()) {
            return 1; // Valid number, return 1
        }
        // If result for the current state is already computed, return it
        if (memo[position][isTight][availableMask][leadingZeroAllowed] != -1) {
            return memo[position][isTight][availableMask][leadingZeroAllowed];
        }
        int totalCount = 0; // Initialize the total count for this state
        int limit = isTight == 1 ? number.charAt(position) - '0' : 9; // Determine the range for the current digit
        // Iterate through all possible digits (0 to the current limit)
        for (int digit = 0; digit <= limit; digit++) {
            int mask = (1 << digit); // Create a bitmask for the current digit
            // Check if the digit is available for use
            if ((mask & availableMask) != 0) {
                // Case 1: Digit is 0 and leading zeros are allowed
                if (digit == 0 && leadingZeroAllowed == 0) {
                    totalCount += countDistinctDigits(position + 1, 0, availableMask, 0, number);
                } 
                // Case 2: Digit is 0 and leading zeros are not allowed
                else if (digit == 0 && leadingZeroAllowed == 1) {
                    totalCount += countDistinctDigits(position + 1, 0, availableMask - mask, 1, number);
                } 
                // Case 3: Digit equals the limit and the tight constraint is maintained
                else if (digit == limit && isTight == 1) {
                    totalCount += countDistinctDigits(position + 1, 1, availableMask - mask, 1, number);
                } 
                // Case 4: General case for non-zero digits without tight constraint
                else {
                    totalCount += countDistinctDigits(position + 1, 0, availableMask - mask, 1, number);
                }
            }
        }
        // Store the result in the DP array and return it
        return memo[position][isTight][availableMask][leadingZeroAllowed] = totalCount;
    }
    // Function to count numbers with unique digits in the range [lowerBound, upperBound]
    static int countInRange(int lowerBound, int upperBound) {
        // Reset the memoization array for the new computation
        for (int[][][] table : memo) {
            for (int[][] row : table) {
                for (int[] innerRow : row) {
                    Arrays.fill(innerRow, -1); // Fill all values with -1
                }
            }
        }
        lowerBound--; // Decrease lowerBound by 1 to calculate the exclusive range
        String lowerStr = String.valueOf(lowerBound); // Convert lowerBound to string
        String upperStr = String.valueOf(upperBound); // Convert upperBound to string
        // Count numbers with unique digits in the range [0, lowerBound]
        int countLower = countDistinctDigits(0, 1, (1 << 10) - 1, 0, lowerStr);
        // Reset the memoization array again for the next computation
        for (int[][][] table : memo) {
            for (int[][] row : table) {
                for (int[] innerRow : row) {
                    Arrays.fill(innerRow, -1); // Fill all values with -1
                }
            }
        }
        // Count numbers with unique digits in the range [0, upperBound]
        int countUpper = countDistinctDigits(0, 1, (1 << 10) - 1, 0, upperStr);
        // Return the difference between the counts in [0, upperBound] and [0, lowerBound]
        return countUpper - countLower;
    }
    // Main function
    public static void main(String[] args) {
        int lowerBound = 1, upperBound = 100; // Define the range
        // Print the count of numbers with unique digits in the specified range
        System.out.println("The count of numbers with unique digits in the range " 
                            + lowerBound + " to " + upperBound + " is: " 
                            + countInRange(lowerBound, upperBound));
    }
}   

输出

 
The count of numbers with unique digits in the range 1 to 100 is: 98

时间复杂度： O(log(R) × M)，其中 M = 1024。

辅助空间复杂度： O(log(R) × M)。

下一主题Java 中的卡特兰数

Find Total Numbers with No Repeated Digits in A Range in Java

方法：暴力法

算法

实施

方法：前缀和法

算法

实施

动态规划

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

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

Find Total Numbers with No Repeated Digits in A Range in Java

方法：暴力法

算法

实施

方法：前缀和法

算法

实施

动态规划

算法

实施

相关帖子

Java BF

Java 工具和命令列表

LRU Cache Implementation

如何在 Java 中获取文件类型

Java 与 Go

Java 程序打印数字的螺旋图案

Backwards Compatibility in a Software System with Systematic Reference to Java

Example of open dialog box

Java 中 ChoiceFormat equals() 方法及示例

Java 中重写 equals 方法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器