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;
}

Java програм

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) бид зөвхөн тогтмол санах ойн зайг ашигладаг тул.