ຈຳ ນວນຕົວເລກທັງ ໝົດ ທີ່ບໍ່ມີຕົວເລກທີ່ຊ້ ຳ ແລ້ວໃນຊ່ວງ Range


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ ປັດໃຈ MAQ
ຄະນິດສາດ ຕົວເລກ ໝາຍ ເລກ

ທ່ານໄດ້ຮັບລະດັບຂອງຕົວເລກ (ເລີ່ມຕົ້ນ, ທ້າຍ). ວຽກທີ່ໄດ້ຮັບນັ້ນບອກວ່າເພື່ອຊອກຫາຕົວເລກທັງ ໝົດ ຂອງຕົວເລກທີ່ບໍ່ມີຕົວເລກຊ້ ຳ ອີກໃນລະດັບໃດ ໜຶ່ງ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

10 50

ຜົນໄດ້ຮັບ:

37

ຄໍາອະທິບາຍ:

10 ບໍ່ມີຕົວເລກຊ້ ຳ ອີກ. 11 ມີຕົວເລກຊ້ ຳ ອີກ. 12 ບໍ່ມີຕົວເລກຊ້ ຳ ອີກ. ໃນຂະນະທີ່ 22, 33 ມີຕົວເລກຊ້ ຳ ແລ້ວຊ້ ຳ ອີກ. ດັ່ງນັ້ນເມື່ອພວກເຮົາພົບຕົວເລກທີ່ບໍ່ມີຕົວເລກຊ້ ຳ ອີກ, ພວກເຮົາຈະນັບວ່າໃນຜົນຂອງພວກເຮົາ.

ຈຳ ນວນຕົວເລກທັງ ໝົດ ທີ່ບໍ່ມີຕົວເລກທີ່ຊ້ ຳ ແລ້ວໃນຊ່ວງ Range

ລະບົບວິເຄາະ

  1. ປະກາດກ ທີ່ກໍານົດໄວ້ ແລະ vector.
  2. ຍູ້ 0 ແລະ 1 ເຂົ້າໄປໃນ vector ແລະຊອກຫາປັດໃຈທັງຫມົດໃນໄລຍະ 10, ແລະເກັບຮັກສາສ່ວນທີ່ເຫຼືອໄວ້ໃນຊຸດ. ຖ້າທີ່ ກຳ ນົດໄວ້ແລ້ວມີ ຈຳ ນວນນັ້ນກັບຄືນ 0 ອີກອັນ ໜຶ່ງ ຈະສົ່ງຄືນ 1.
  3. ເອົາເລກນັ້ນແລະເພີ່ມເຂົ້າໃນ vector.
  4. ສຳ ລັບທຸກໆ ຄຳ ຖາມ, ໃຫ້ຄືນຄວາມແຕກຕ່າງຂອງ vector [ສິ້ນສຸດ] ແລະ vector [ເລີ່ມຕົ້ນ].

ຄໍາອະທິບາຍສໍາລັບຕົວເລກທັງຫມົດໂດຍບໍ່ມີຕົວເລກທີ່ເຮັດຊ້ໍາອີກໃນຂອບເຂດ

ພວກເຮົາໄດ້ມອບຊ່ວງ ໜຶ່ງ. ພວກເຮົາໄດ້ຮ້ອງຂໍໃຫ້ຊອກຫາຕົວເລກທັງ ໝົດ ຂອງຕົວເລກທີ່ເຂົ້າມາໃນຂອບເຂດໃດ ໜຶ່ງ ບໍ່ມີຕົວເລກຊ້ ຳ ອີກໃນຕົວເລກຕົວມັນເອງ. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາ ກຳ ລັງຈະ ນຳ ໃຊ້ກອບການເກັບ ກຳ ຂໍ້ມູນ. ພວກເຮົາຈະໃຊ້ຊຸດແລະ vector. ຊຸດແມ່ນການເກັບຮັກສາປັດໃຈທີ່ບໍ່ ທຳ ມະດາຫລືສ່ວນທີ່ເຫຼືອຂອງ ຈຳ ນວນແລະ vector ແມ່ນການເກັບ ຈຳ ນວນທີ່ຖືກກັ່ນຕອງຈາກຊຸດ. ພວກເຮົາຮູ້ວ່າບໍ່ຫຼາຍປານໃດຂອງພວກເຂົາພຽງແຕ່ຕົວເລກໃນສະຖານທີ່ 10 ຕົວເລກໃດໆກໍ່ບໍ່ໄດ້ເຮັດຊ້ ຳ ອີກ, ເຊັ່ນຈາກ 1 ເຖິງ 10, ບໍ່ມີຕົວເລກທີ່ເຮັດຊ້ ຳ ອີກ. ຕັ້ງແຕ່ວັນທີ 11 ເຖິງ 10 ແລະ 21 ຫາ 30, ມີສອງຕົວເລກທີ່ມີຕົວເລກຊ້ ຳ ອີກເປັນ 11 ແລະ 22, ນີ້ກໍ່ຄືກັນ.

ພວກເຮົາຈະເພີ່ມເລກ 0 ແລະ 1 ເຂົ້າໃສ່ແວ່ນຕາ, ຈາກຄ່າ 2 ເຖິງມູນຄ່າທີ່ໄດ້ຮັບ, ອັນໃດກໍ່ຕາມມັນກໍ່ສາມາດເປັນໄດ້. ເອົາເລກທີ່ມີປັດໃຈຫລືສ່ວນທີ່ເຫຼືອໃນເງື່ອນໄຂ 10 ດັ່ງທີ່ກ່າວມາຂ້າງເທິງ. ພວກເຮົາຈະໄດ້ສ່ວນທີ່ເຫຼືອເຫຼົ່ານັ້ນແລະຕື່ມເຂົ້າໃນຊຸດຖ້າ ກຳ ນົດແລ້ວມີ ຈຳ ນວນດັ່ງກ່າວເປັນ ຈຳ ນວນທີ່ເຫຼືອ. ສົ່ງຄືນ 0 ອີກອັນ ໜຶ່ງ ທີ່ຍັງເຫຼືອໃຫ້ກັບທີ່ ກຳ ນົດໄວ້. ຍ້ອນວ່າມັນຈະເປັນຕົວເລກ ໃໝ່ ຫຼືຍັງເຫຼືອຢູ່ແລະກັບຄືນມາ 1. ເກັບຕົວຢ່າງຈົນກ່ວາມູນຄ່າຈະກາຍເປັນ 0. ໃນທີ່ນີ້ພວກເຮົາຈະໄດ້ເລກຈາກຕົວເລກ 0 ຫລື 1, ແລະຕື່ມໃສ່ມັນດ້ວຍເລກທີ່ດຶງມັນຜ່ານ vector, ແລະຍູ້ການນັບ ກັບ vector ຕົວມັນເອງ.

ສຳ ລັບການສອບຖາມແຕ່ລະຂໍ້ໃຫ້, ພວກເຮົາຈະກັບຄືນຄວາມແຕກຕ່າງຂອງຕົວເລກຢູ່ ຕຳ ແໜ່ງ ທີ່ຖືກຕ້ອງ, ຊຶ່ງ ໝາຍ ເຖິງຊ່ວງທີ່ຖືກຕ້ອງ, ແລະຕົວເລກທີ່ ຕຳ ແໜ່ງ ຊ້າຍ ໝາຍ ຄວາມວ່າເລກທີ່ຢູ່ເບື້ອງຊ້າຍໃນ vector. ພວກເຮົາຈະກັບຄືນຄວາມແຕກຕ່າງນີ້, ນີ້ພວກເຮົາຈະເປັນ ຄຳ ຕອບທີ່ ຈຳ ເປັນ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບໂຕເລກລວມໂດຍບໍ່ມີຕົວເລກທີ່ຊ້ ຳ ແລ້ວໃນຊ່ວງ Range

#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 ສຳ ລັບ ຈຳ ນວນໂຕເລກທັງ ໝົດ ໂດຍບໍ່ມີຕົວເລກທີ່ຊ້ ຳ ແລ້ວໃນ Range

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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.