在一個範圍內沒有重複數字的總數

在本文中，我們將討論計算給定範圍 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

結論 - 在這段程式碼中，我們討論了三種方法來計算從低到高範圍內沒有重複數字的總數。

以上是在一個範圍內沒有重複數字的總數的詳細內容。更多資訊請關注PHP中文網其他相關文章！