在本文中，我们将讨论计算给定范围 Low 到 high 之间没有重复数字的正整数数量的不同方法。第一种方法是暴力方法，它迭代范围内的所有数字并检查它们是否包含重复的数字。在第二种方法中，我们使用前缀数组计算所需的计数，而在最后一种方法中，我们使用动态编程中的记忆概念来获得所需的结果。
问题陈述：给定两个数字，从低到高，我们必须找到从低到高之间的所有数字的计数，使得该数字不包含任何重复的数字。
方法 1
这是蛮力方法，我们只是从低到高迭代所有数字并检查它们是否包含任何重复的数字。这是解决我们的问题的最简单方法。
示例
下面给出了相同的代码解决方案：
#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
在这种方法中，我们将使用一个前缀数组来存储直到索引“迭代器”为止没有重复数字的整数的计数。
此方法涉及的步骤是：
定义一个函数来检查数字是否具有重复的数字。
用零初始化前缀数组。前缀数组将存储直到给定索引“迭代器”为止的有效数字的数量。
从低到高遍历每个数字，检查是否有重复的数字。如果没有重复数字，则将相应索引处的前缀数组加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 为（高 - 低）。
空间复杂度 - O(n)
方法3动态规划方法
在这种方法中，我们将问题分解为子问题，并将子问题的结果存储在记忆表中
程序计算给定范围内有效数字的总数，即没有重复数字的数字。它使用动态编程方法，其中函数 dp(“iterator”,used) 返回可以从位置“iterator”开始且数字“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
结论 - 在这段代码中，我们讨论了三种方法来计算从低到高范围内没有重复数字的总数。
