Муж дахь давталтгүй цифргүй нийт тоо  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Мэдээллийн багц MAQ
Математик Тоо-цифр

Танд тооны хүрээ (эхлэл, төгсгөл) өгдөг. Өгөгдсөн даалгаварт муж дотор давтагдах оронгүй тоонуудын нийт тоог олохыг хэллээ.

Жишээ нь  

Орц:

10 50

Үр дүн:

37

Тайлбар:

10-д давтагдсан цифр байхгүй. 11 нь давтагдсан оронтой байна. 12-т давтагдсан цифр байхгүй. харин 22, 33 нь давтагдсан цифртэй байна. Тиймээс давтагдсан цифргүй тоог олсон тохиолдолд бид үүнийг үр дүндээ тооцох болно.

Муж дахь давталтгүй цифргүй нийт тооPin

Алгоритм  

  1. Мэдүүлэх a нь чансаанд ба вектор.
  2. 0 ба 1-ийг вектор руу түлхэж, 10-р хугацааны бүх хүчин зүйлийг олж мэдээд үлдэгдлийг багцад хадгална. Хэрэв уг багцад аль хэдийн буцаах тоо байгаа бол 0, өөрөөр 1 буцаана.
  3. Энэ дугаарыг аваад дотор нь нэмнэ үү вектор.
  4. Асуулга болгоны хувьд векторын [төгсгөл] ба векторын [эхлэл] зөрүүг буцаана.

Муж дахь давталтын цифргүй нийт тоонуудын тайлбар  

Бид хүрээ өгсөн. Тухайн мужид орж ирсэн тооны нийт тоог тухайн тоогоор давтагдах цифр байхгүй болохыг олж мэдэхийг бид хүссэн. Үүний тулд бид цуглуулгын хүрээг ашиглах гэж байна. Бид set ба векторыг ашиглах болно. Set гэдэг нь ердийн бус хүчин зүйл эсвэл тооны үлдэгдлийг хадгалах бөгөөд вектор нь уг багцаас шүүсэн тоог хадгалах явдал юм. Тэдгээрийн цөөхөн нь 10-аад оронтой тооны тоо давтагдахгүй, 1-ээс 10 хүртэлх тоо давтагддаггүй, давтагдашгүй тоо байдаггүйг бид мэднэ. 11-ээс 10 ба 21-ээс 30 хүртэл 11 ба 22 гэж давтагдсан цифрүүдтэй хоёр тоо байна, энэ нь ижил байна.

мөн үзнэ үү
Массивт байгаа бүтээгдэхүүнүүдийн тоог хосоор нь тоол

Бид вектор дээр 0 ба 1 тоог 2-оос өгөгдсөн утга хүртэл, юу ч байж болно нэмнэ. Дээр дурьдсанчлан 10-тай тэнцүү хүчин зүйл эсвэл үлдэгдэлтэй тоог авна уу. Хэрэв бид эдгээр үлдэгдлийг авч, багцад энэ дугаарыг үлдэгдэл хэлбэрээр оруулсан бол багцад нэмэх болно. 0-ийг буцааж буцааж багцад нэмнэ үү. Энэ нь шинэ тоо эсвэл үлдэгдэл байх тул буцах болно. Утга нь 1 болтлоо үргэлжлүүлэн явна уу. Энд бид ижил төстэй 0 эсвэл 0-ээс тоог олж, вектороор авч байгаа тоогоор нэмээд тооллыг дарна. вектор өөрөө.

Асуулт өгөх бүрт бид зөв байрлал дахь тооны зөрүүг буцааж өгөх бөгөөд энэ нь зөв мужийг, зүүн байрлал дахь тоонууд нь вектор дахь зүүн муж дахь тоог илэрхийлнэ. Бид энэ ялгааг буцааж өгөх болно, энэ нь бид шаардлагатай хариулт байх болно.

Хэрэгжүүлэх  

Дахин давтах цифргүй нийт тоонуудад зориулсан 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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (1) нэмэлт цаг шаардагдахгүй тул.

мөн үзнэ үү
Бүтээгдэхүүний хамгийн дээд хэмжээ

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.