一定范围内不含重复数字的总数

---

在本文中，我们将讨论计算给定范围（从低到高）内不含重复数字的正整数个数的不同方法。第一种方法是暴力方法，它迭代范围内的所有数字，并检查它们是否包含重复数字。在我们的第二种方法中，我们使用前缀数组计算所需的计数，而在我们的最后一种方法中，我们使用动态规划中的记忆化概念来获得所需的结果。

问题陈述：给定两个数字 low 和 high，我们必须找到 low 到 high 之间所有数字的计数，这些数字不包含任何重复的数字。

方法 1

这是暴力方法，我们只是迭代从 low 到 high 的所有数字，并检查它们是否包含任何重复的数字。这是解决我们问题的最简单方法。

示例

下面给出了相同的代码解决方案

#include <bits/stdc++.h>
using namespace std;
// function that checks whether or not the number contains any repeated digits
int count(int number){
	int arr[10] = {0};
	while(number != 0) {
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return 0;
		}
		arr[digit]++;
		number = number / 10;
	}
	return 1;
}
// this function iterates over all the numbers in the range from low to high and adds the count of numbers having no repeated digits to the result
int numberofnums(int l , int h)
{
	int res = 0;
	for(int iterator = l; iterator < h + 1; ++iterator)
	{
		res = res + count(iterator);
	}

	return res ;
}
int main()
{
	int low = 1, high = 90;
	cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<<numberofnums(low, high);
	return 0;
}

输出

The count of numbers with no repeated digits from 1 to 90 is 82

方法 2

在这种方法中，我们将使用一个前缀数组，该数组存储直到索引“迭代器”为止不含重复数字的整数的计数。

此方法涉及的步骤为

• 定义一个函数来检查数字是否包含重复的数字。

• 用零初始化前缀数组。前缀数组将存储直到给定索引“迭代器”为止的有效数字的数量。

• 从 low 迭代到 high，对于每个数字，检查它是否包含重复的数字。如果它不包含重复的数字，则将对应索引处的前缀数组加 1。

• 计算前缀数组的前缀和。前缀和将为您提供该范围内有效数字的总数。

• 返回前缀和。

示例

此方法的代码如下所示：

#include <bits/stdc++.h>
using namespace std;
bool isvalid(int number)
{
	int arr[10] = {0};
	while(number != 0)
	{
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return false;
		}
		arr[digit]++;
		number = number / 10;
	}
	return true;
}

int count(int low, int high) {
    vector<int> prefarray(high+1, 0);
    for (int iterator = low; iterator <= high; iterator++) {
        if (isvalid(iterator)) {
            prefarray[iterator] = 1;
        }
    }
    for (int iterator = 1; iterator <= high; iterator++) {
        prefarray[iterator] += prefarray[iterator-1];
    }
    return prefarray[high] - prefarray[low-1];
}

int main() {
    int low = 21, high = 200;
    int c = count(low, high);
    cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<< c;
    return 0;
}

输出

The count of numbers with no repeated digits from 21 to 200 is 143

时间复杂度 - O(nlogn)，其中 n 为 (high - low)。

空间复杂度 - O(n)

方法 3 动态规划方法

在这种方法中，我们将把问题分解成子问题，并将子问题的结果存储在记忆化表中

程序计算给定范围内有效数字的总数，即不含重复数字的数字。它使用动态规划方法，其中函数 dp(“迭代器”, used) 返回从位置“迭代器”开始使用“used”中的数字可以形成的有效数字的数量。

我们使用了记忆化表来存储 dp 函数的结果，并遍历数字范围以对每个数字调用 dp 函数。所有起始位置“迭代器”的 dp 函数结果之和是该范围内有效数字的总数。

示例

#include <bits/stdc++.h>
using namespace std;
int dp(int iterator, set<int>& used, unordered_map<string, int>& memo, const string& high_str) {
    if ( memo.count(to_string(iterator) + "|" + to_string(used.size() ))) {
        return memo[to_string(iterator) + "|" + to_string(used.size())];
    }
    if (iterator == high_str.length())
    {
        return 1;
    }
    int count = 0;
    for (int digit = 0; digit < 10; digit++) {
        if (digit == 0 && iterator == 0) {
            continue;
        }
        if (!used.count(digit)) {
            used.insert(digit);
            count += dp(iterator+1, used, memo, high_str);
            used.erase(digit);
        }
    }
    memo[to_string(iterator) + "|" + to_string(used.size())] = count;
    return count;
}

int count_valid_numbers(int low, int high) {
    unordered_map<string, int> memo;
    string high_str = to_string(high);
    int count = 0;
    for (int num = low; num <= high; num++) {
        set<int> used;
        count += dp(0, used, memo, high_str);
    }
    return count;
}

int main() {
    int low = 21, high = 200;
    int count = count_valid_numbers(low, high);
        cout << "The count of numbers with no repeated digits from " << low   <<  " to " << high << " is "<< count;
    return 0;
}

输出

The count of numbers with no repeated digits from 21 to 200 is 116640

结论 - 在此代码中，我们讨论了三种方法来计算一定范围内从低到高不含重复数字的总数。