Συνολικοί αριθμοί χωρίς επαναλαμβανόμενα ψηφία σε εύρος


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Απολύτως Γεγονότα MAQ
μαθηματικά Αριθμός-ψηφία

Σας δίνεται ένα εύρος αριθμών (αρχή, τέλος). Η δεδομένη εργασία λέει να μάθετε τους συνολικούς αριθμούς των αριθμών χωρίς επαναλαμβανόμενα ψηφία σε μια περιοχή.

Παράδειγμα

εισόδου:

10 50

Παραγωγή:

37

Επεξήγηση:

Το 10 δεν έχει επαναλαμβανόμενο ψηφίο. Το 11 έχει επαναλαμβανόμενο ψηφίο. Το 12 δεν έχει επαναλαμβανόμενο ψηφίο. ενώ το 22, 33 έχει επαναλαμβανόμενο ψηφίο. Έτσι, όταν βρήκαμε τους αριθμούς που δεν έχουν επαναλαμβανόμενο ψηφίο, θα το μετρήσουμε στο αποτέλεσμα μας.

Συνολικοί αριθμοί χωρίς επαναλαμβανόμενα ψηφία σε εύρος

Αλγόριθμος

  1. Δήλωση α σετ και ένα διάνυσμα.
  2. Σπρώξτε τα 0 και 1 στο διάνυσμα και ανακαλύψτε όλους τους παράγοντες σε όρους 10 και αποθηκεύστε τα υπόλοιπα στο σετ. Εάν το σετ περιέχει ήδη αυτόν τον αριθμό επιστροφή 0 άλλο επιστρέψτε 1.
  3. Λάβετε αυτόν τον αριθμό και προσθέστε τον στο διάνυσμα.
  4. Για κάθε ερώτημα, επιστρέψτε τη διαφορά του διανύσματος [τέλος] και του διανύσματος [έναρξη].

Επεξήγηση για συνολικούς αριθμούς χωρίς επαναλαμβανόμενα ψηφία σε εύρος

Έχουμε δώσει μια σειρά. Ζητήσαμε να μάθουμε ότι ο συνολικός αριθμός του αριθμού που περιλαμβάνεται σε ένα συγκεκριμένο εύρος δεν έχει επαναλαμβανόμενο ψηφίο στον ίδιο τον αριθμό. Για αυτό, θα χρησιμοποιήσουμε το πλαίσιο συλλογής. Θα χρησιμοποιούμε το σετ και το διάνυσμα. Το σετ είναι η αποθήκευση των ασυνήθιστων παραγόντων ή το υπόλοιπο ενός αριθμού και το διάνυσμα είναι η αποθήκευση του αριθμού που φιλτράρεται από το σύνολο. Γνωρίζουμε ότι λίγα από αυτά μόνο ένας αριθμός σε οποιαδήποτε θέση των 10s δεν επαναλαμβάνεται, όπως από το 1 έως το 10, δεν υπάρχει επαναλαμβανόμενος αριθμός. Από 11 έως 10 και 21 έως 30, υπάρχουν δύο αριθμοί που έχουν επαναλαμβανόμενα ψηφία ως 11 και 22, αυτό ισχύει το ίδιο.

Θα προσθέσουμε τον αριθμό 0 και 1 στο διάνυσμα, από την τιμή 2 έως τη δεδομένη τιμή, όποια κι αν είναι. Λάβετε τον αριθμό που έχει συντελεστή ή υπόλοιπο σε 10, όπως αναφέρεται παραπάνω. Θα πάρουμε αυτά τα υπολείμματα και θα προσθέσουμε στο σύνολο εάν το σύνολο περιέχει ήδη αυτόν τον αριθμό ως υπόλοιπο. Επιστρέψτε 0 αλλιώς προσθέστε το υπόλοιπο στο σύνολο. Καθώς θα είναι ένας νέος αριθμός ή υπόλοιπο και επιστροφή 1. Συνεχίστε να διασχίζετε μέχρι να γίνει η τιμή 0. Εδώ θα λάβουμε τον αριθμό από τα παρόμοια 0 ή 1, και θα τον προσθέσουμε με τον αριθμό που τον παίρνει μέσω ενός διανύσματος και θα ωθήσει τον αριθμό στον ίδιο τον φορέα.

Για κάθε δόση ερωτήματος, θα επιστρέφουμε τη διαφορά αριθμών στη σωστή θέση, που σημαίνει το σωστό εύρος, και οι αριθμοί στην αριστερή θέση σημαίνει τον αριθμό στο αριστερό εύρος στο διάνυσμα. Θα επιστρέψουμε αυτήν τη διαφορά, αυτή θα είναι η απαιτούμενη απάντηση.

Εκτέλεση

Πρόγραμμα C ++ για συνολικούς αριθμούς χωρίς επαναλαμβανόμενα ψηφία σε εύρος

#include <iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int MAX = 1000;

vector<int> numbers = {0};

int getRepeatedNumber(int n)
{

    unordered_set<int> SET;
    int rem;

    while (n != 0)
    {
        rem = n % 10;
        if (SET.find(rem) != SET.end())
            return 0;

        SET.insert(rem);
        n = n / 10;
    }
    return 1;
}

void buildSetOfNumbers(int MAX)
{

    numbers.push_back(getRepeatedNumber(1));

    for (int i = 2; i < MAX + 1; i++)
        numbers.push_back(getRepeatedNumber(i) + numbers[i-1]);
}

int getNumber(int left,int right)
{
    return numbers[right] - numbers[left-1];
}
int main()
{
    int Left = 10, Right = 50;
    buildSetOfNumbers(MAX);

    cout << getNumber(Left, Right) << endl;

    return 0;
}
37

Πρόγραμμα Java για συνολικούς αριθμούς χωρίς επαναλαμβανόμενα ψηφία σε εύρος

import java.util.Vector;
import java.util.HashSet;

class repeatedDigits
{
    private static int MAX = 100;
    private static Vector<Integer> numbers = new Vector<>();
    
    static int getRepeatedNumber(int n)
    {
        HashSet<Integer> set = new HashSet<>();
        int rem;

        while (n != 0)
        {
            rem = n % 10;

            if (set.contains(rem))
                return 0;

            set.add(rem);
            n /= 10;
        }
        return 1;
    }
    
    static void buildSetOfNumbers()
    {
        numbers.add(0);
        numbers.add(getRepeatedNumber(1));

        for (int i = 2; i < MAX + 1; i++)
            numbers.add(getRepeatedNumber(i) + numbers.elementAt(i - 1));
    }
    
    static int getNumber(int left, int right)
    {
        return numbers.elementAt(right) - numbers.elementAt(left - 1);
    }
    
    public static void main(String[] args)
    {
        int Left = 10, Right = 50;

        buildSetOfNumbers();
        System.out.println(getNumber(Left, Right));
    }
}
37

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (1) καθώς δεν απαιτείται επιπλέον χρόνος.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.