מצא מספרים עם מספר ספרות זוגי של פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות Quora
מערך

בבעיה זו ניתן לנו מערך של מספרים שלמים חיוביים. עלינו למצוא את ספירת המספרים עם מספר זוגי של ספרות.

דוגמה

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

הסבר: רק 34 ו- 3434 הם מספרים שלמים עם מספר ספרות אחיד. אז אנו מדפיסים 2.

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

הסבר: אין מספר שלם עם מספר זוגי של ספרות במערך הנתון.

גישה

ליבת הבעיה היא לספור את מספר הספרות במספר שלם. אם נוכל לעשות זאת, נוכל לחזור על התהליך עבור כל מספר שלם במערך ולספור את מספר המספרים השלמים בעלי מספר זוגי של ספרות. בייצוגים בינאריים, אנו יכולים להזיז ימינה מספר שלם נתון (או לחלק אותו ב -2) עד שהוא הופך לאפס לספור מספר ביטים בּוֹ. באופן דומה, עבור ספירת ספרות, אנו יכולים להמשיך ולחלק מספר שלם לפי 10 אלא אם כן זה הופך להיות 0. שיטה זו נכונה לכל בסיס.

מצא מספרים עם מספר ספרות זוגי של פתרון Leetcode

 

אַלגוֹרִיתְם

  1. אנו יוצרים פונקציה findNumbers () כדי למצוא את מספר המספרים השלמים שמספרם הספרות השווה בכל מערך המועבר אליו
  2. כמו כן, אנו יוצרים פונקציית עוזר כמות הספרות() להחזרת מספר הספרות במספר שלם שהועבר אליו כ:
    1. לאתחל Cnt = 0
    2. בעוד שהמספר השלם, n גדול מ- 0:
      1. תוֹסֶפֶת Cnt, cnt ++
      2. לחלק n by 10, n / = 10
    3. לַחֲזוֹר Cnt
  3. אתחל תוצאה = 0 כדי לאחסן את ספירת המספרים השלמים עם מספר זוגי של ספרות
  4. לכל רכיב במערך:
    1. אנו מאחזרים את ספירת הספרות בו באמצעות כמות הספרות() פונקציה
    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

מורכבות זמן

מורכבות הזמן היא עַל) כאשר N = גודל המערך כשאנחנו מבצעים מעבר יחיד של המערך ומספר הספרות נשלף בזמן קבוע.

מורכבות בחלל

O (1) כיוון שאנו משתמשים רק במרחב זיכרון קבוע.