범위에서 반복되는 숫자가없는 총 숫자

난이도 중급
자주 묻는 질문 수행자 팩트 셋 MAQ
수학 숫자 자리조회수 33

숫자 범위 (시작, 끝)가 제공됩니다. 주어진 작업은 범위에서 반복되는 숫자가없는 숫자의 총 수를 알아 내라고 말합니다.

입력:

10 50

출력:

37

설명 :

10에는 반복되는 숫자가 없습니다. 11에는 반복되는 숫자가 있습니다. 12에는 반복되는 숫자가 없습니다. 반면 22, 33에는 반복되는 숫자가 있습니다. 따라서 반복되는 숫자가없는 숫자를 찾으면 결과에서이를 계산합니다.

범위에서 반복되는 숫자가없는 총 숫자

암호알고리즘

  1. 선언 세트 및 벡터.
  2. 0과 1을 벡터에 넣고 10이라는 용어로 모든 요인을 찾아 나머지를 세트에 저장합니다. 세트에 이미 해당 숫자가 포함되어 있으면 0을 반환하고 그렇지 않으면 1을 반환합니다.
  3. 해당 번호를 가져 와서 벡터.
  4. 모든 쿼리에 대해 vector [end]와 vector [start]의 차이를 반환합니다.

범위에서 반복되는 숫자가없는 총 숫자에 대한 설명

범위를 지정했습니다. 우리는 주어진 범위에 들어온 숫자의 총 숫자가 숫자 자체에 반복되는 숫자가 없는지 알아 보도록 요청했습니다. 이를 위해 컬렉션 프레임 워크를 사용할 것입니다. 우리는 세트와 벡터를 사용할 것입니다. 집합은 비 공통 인자 또는 숫자의 나머지를 저장하는 것이고 벡터는 집합에서 필터링 된 숫자를 저장하는 것입니다. 우리는 그들 중 10 자리 자리에있는 숫자 만이 반복되지 않는다는 것을 알고 있습니다. 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

복잡성 분석

시간 복잡성

O (1) 추가 시간이 필요하지 않습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

Translate »