C++ 范围内没有重复数字的总数

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

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

方法一

这是一种简单粗暴的方法，我们只是遍历从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

方法二

在这种方法中，我们将使用一个前缀数组，该数组存储了没有重复数字的整数的数量，直到索引“iterator”。

这种方法涉及的步骤如下：

• 定义一个函数，检查一个数字是否有重复的数字。

• 用零初始化一个前缀数组。前缀数组将存储到给定索引“iterator”的有效数字的数量。

• 从低到高遍历每个数字，检查它是否有重复的数字。如果没有重复的数字，将相应索引处的前缀数组增加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）

方法三：动态规划方法

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

该程序计算给定范围内的有效数字的总数，即没有重复数字的数字。它使用动态规划方法，其中函数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

结论 − 在这段代码中，我们讨论了三种方法来计算在从低到高的范围内没有重复数字的总数。