იპოვნეთ რიცხვები, ციფრების ლუწი რიცხვით, Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Quora
Array

ამ პრობლემის დროს ჩვენ გვეძლევა მასივი პოზიტიური მთელი რიცხვების. უნდა ვიპოვოთ ციფრების ლუწი რიცხვით რიცხვების რიცხვი.

მაგალითი

Array = {123 , 34 , 3434 , 121 , 100}
2

განმარტება: მხოლოდ 34 და 3434 რიცხვებია ციფრების ლუწი რიცხვით. ასე რომ, ჩვენ ვბეჭდავთ 2-ს.

Array = {1 , 111 , 11111 , 12345}
0

განმარტება: მოცემულ მასივში არ არის მთელი რიცხვი, თუნდაც ციფრების რიცხვი.

მიდგომა

ამ პრობლემის მთავარია მთლიანი რიცხვის ციფრების დათვლა. თუ ამის გაკეთება შეგვიძლია, მაშინ შეგვიძლია განმეორდეს პროცესი მასივის ყველა მთელი რიცხვისთვის და დაითვალოს მთელი რიცხვების რიცხვი, რომლებსაც აქვთ ციფრების ლუწი რიცხვი. ორობითი რეპრეზენტაციისას, ჩვენ შეგვიძლია მარჯვნივ გადავიტანოთ მოცემული მთელი რიცხვი (ან გავყოთ 2-ზე), სანამ ის გახდება ნულოვანი, რომ დაითვალოს ბიტი მასში. ანალოგიურად, ციფრების გამოსათვლელად, შეგვიძლია განვაგრძოთ მთელი რიცხვის გაყოფა 10 თუ ის არ გახდება 0. ეს მეთოდი შეესაბამება ნებისმიერ ბაზას.

იპოვნეთ რიცხვები, ციფრების ლუწი რიცხვით, Leetcode ამოხსნა

 

ალგორითმი

  1. ჩვენ ვქმნით ფუნქციას findNumbers () იპოვონ მთელი რიცხვების რიცხვი, რომელთაც აქვთ მასივში ციფრების ლუწი რიცხვი
  2. ასევე, ჩვენ ვქმნით დამხმარე ფუნქციას numberOfDigits () ციფრების რაოდენობის დასაბრუნებლად მისთვის გადაცემული მთელი რიცხვი, როგორც:
    1. ინიციალიზაცია cnt = 0
    2. ხოლო მთელი რიცხვი, n აღემატება 0-ს:
      1. ზრდა cnt, cnt ++
      2. გაყოფა n by 10, n / = 10
    3. დაბრუნების cnt
  3. ინიციალიზაცია შედეგად = 0 მთელი რიცხვების შესანახად, რომლებსაც აქვთ ციფრების ლუწი რიცხვი
  4. მასივის ყველა ელემენტისთვის:
    1. ჩვენ ვიღებთ მასში ციფრების რაოდენობას numberOfDigits () ფუნქცია
    2. თუ მიღებული ციფრების რიცხვი კი არის:
      1. გაზრდის შედეგი, შედეგი ++
  5. დაბრუნების შედეგი

რიცხვების განხორციელება ციფრების ლუწი რაოდენობის მქონე Leetcode ამოხსნის გამოყენებით

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;

int numberOfDigits(int n)
{
    int cnt = 0;
    while(n > 0)
    {
        n /= 10;
        cnt++;
    }
    return cnt;
}

int findNumbers(vector <int> &a)
{
    int result = 0;
    for(int &i : a)
        if(numberOfDigits(i) % 2 == 0)
            result++;

    return result;
}

int main()
{
    vector <int> a = {123 , 34 , 3434 , 121 , 100};
    cout << findNumbers(a) << '\n';
    return 0;
}

ჯავა პროგრამა

class find_numbers
{
    public static void main(String args[])
    {
        int[] a = {123 , 34 , 3434 , 121 , 100};
        System.out.println(findNumbers(a));
    }

    static int numberOfDigits(int n)
    {
        int cnt = 0;
        while(n > 0)
        {
            n /= 10;
            cnt++;
        }
        return cnt;
    }

    static int findNumbers(int[] a)
    {
        int result = 0;
        for(int i = 0 ; i < a.length ; i++)
            if(numberOfDigits(a[i]) % 2 == 0)
                result++;

        return result;
    }
}
2

ციფრების პოვნის სირთულის ანალიზი Leetcode ამოხსნის ციფრების ლუწი რიცხვით

დროის სირთულე

დროის სირთულეა O (N) სადაც N = მასივის ზომა, რადგან მასივის ერთ პასს ვაკეთებთ და ციფრების რაოდენობა ხდება მუდმივ დროში.

სივრცის სირთულე

O (1) რადგან ჩვენ ვიყენებთ მხოლოდ მუდმივ მეხსიერების ადგილს.