一定範圍內不含重複數字的總數

---

在本文中，我們將討論計算給定範圍（從低到高）內不含重複數字的正整數個數的不同方法。第一種方法是暴力方法，它迭代範圍內的所有數字，並檢查它們是否包含重複數字。在我們的第二種方法中，我們使用字首陣列計算所需的計數，而在我們的最後一種方法中，我們使用動態規劃中的記憶化概念來獲得所需的結果。

問題陳述：給定兩個數字 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

結論 - 在此程式碼中，我們討論了三種方法來計算一定範圍內從低到高不含重複數字的總數。