Die Gesamtzahl der Zahlen in einem Bereich ohne Duplikate

In diesem Artikel besprechen wir verschiedene Möglichkeiten, die Anzahl positiver Ganzzahlen zu zählen, ohne Zahlen zwischen einem bestimmten Bereich von niedrig bis hoch zu wiederholen. Die erste Methode ist eine Brute-Force-Methode, die alle Zahlen im Bereich durchläuft und prüft, ob sie doppelte Zahlen enthalten. Bei der zweiten Methode berechnen wir die erforderliche Anzahl mithilfe eines Präfix-Arrays und bei der letzten Methode verwenden wir das Speicherkonzept aus der dynamischen Programmierung, um das erforderliche Ergebnis zu erhalten.

Problemstellung: Bei zwei Zahlen von niedrig nach hoch müssen wir die Anzahl aller Zahlen zwischen niedrig und hoch ermitteln, sodass die Zahl keine doppelten Ziffern enthält.

Methode 1

Dies ist die Brute-Force-Methode. Wir durchlaufen einfach alle Zahlen von niedrig nach hoch und prüfen, ob sie doppelte Zahlen enthalten. Dies ist die einfachste Lösung für unser Problem.

Beispiel

Die Codelösung dafür ist unten angegeben:

#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;
}

Ausgabe

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

Methode 2

In dieser Methode verwenden wir ein Präfix-Array, um die Anzahl der Ganzzahlen ohne doppelte Zahlen bis zum Index „iterator“ zu speichern.

Die Schritte dieser Methode sind:

• Definieren Sie eine Funktion, um zu prüfen, ob eine Zahl doppelte Ziffern enthält.

• Initialisieren Sie das Präfix-Array mit Nullen. Das Präfix-Array speichert die Anzahl der signifikanten Ziffern bis zum angegebenen Index „iterator“.

• Durchlaufen Sie jede Zahl von niedrig nach hoch und prüfen Sie, ob es doppelte Zahlen gibt. Wenn keine doppelten Nummern vorhanden sind, fügen Sie am entsprechenden Index 1 zum Präfix-Array hinzu.

• Berechnen Sie die Präfixsumme des Präfixarrays. Die Präfixsumme gibt Ihnen die Gesamtzahl der signifikanten Ziffern im Bereich an.

• Gibt die Präfixsumme zurück.

Beispiel

Der Code für diesen Ansatz ist unten angegeben -

#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;
}

Ausgabe

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

Zeitkomplexität – O(nlogn), wobei n (hoch – niedrig) ist.

Raumkomplexität – O(n)

Methode 3 Dynamische Programmiermethode

Bei diesem Ansatz zerlegen wir das Problem in Teilprobleme und speichern die Ergebnisse der Teilprobleme in einer Speichertabelle

Das Programm zählt die Gesamtzahl der signifikanten Ziffern in einem bestimmten Bereich, d. h. Zahlen ohne wiederholte Ziffern. Es verwendet einen dynamischen Programmieransatz, bei dem die Funktion dp("iterator",used) die Anzahl der signifikanten Ziffern zurückgibt, die ausgehend von der Position "iterator" und in der Zahl "used" gebildet werden können.

Wir verwenden eine Memtable, um die Ergebnisse der dp-Funktion zu speichern und über den Zahlenbereich zu iterieren, um die dp-Funktion für jede Zahl aufzurufen. Die Summe der Ergebnisse der dp-Funktion für alle beginnenden „Iteratoren“ ist die Gesamtzahl der signifikanten Ziffern im Bereich.

Beispiel

#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;
}

Ausgabe

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

Fazit – In diesem Code haben wir drei Möglichkeiten besprochen, die Gesamtzahl zu zählen, ohne Zahlen im Bereich von niedrig bis hoch zu wiederholen.

Das obige ist der detaillierte Inhalt vonDie Gesamtzahl der Zahlen in einem Bereich ohne Duplikate. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!