Tək bir Ədədləri İnterval Aralığı Leetcode həllində sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur microsoft
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 53

Problem bəyanat

Bu problemdə bizə aşağı və yüksək iki mənfi olmayan tam ədədi verilir. Verilən interval aralığında nə qədər tək rəqəm olduğunu tapmaq məcburiyyətindəyik [aşağı, yüksək].

misal

low = 3, high = 7
3

Explanation:

3 ilə 7 arasındakı tək rəqəmlər [3, 5, 7].

low = 8, high = 10
1

Explanation:

8 ilə 10 arasındakı tək rəqəmlər [9].

Yanaşma

Verilən interval aralığında tək ədədlərin ümumi sayını tapmağın bir yolu, aralığın soldan sağ sərhədinə keçməkdir. loop və hər tək say üçün tək sayğacı artırın. Ancaq bu, aralığdakı tək nömrələrin sayılması üçün çox topal bir yanaşma olacaqdır. Bu, xətti zaman mürəkkəbliyi alacaq və belə asan bir problem istəmirik.

Verilən interval aralığında cəmi tək ədəd tapmaq çox asandır, çünki bir aralıq aralığında demək olar ki, yarısı və yarısı tək ədəd olduğunu bilirik.
Ancaq aralıq sərhədlərini çox diqqətlə nəzərdən keçirməliyik. Beləliklə, nə edə bilərik ki, ilk n təbii ədədə tək sayların sayılması üçün düstur yarada bilərik. Sayılsın [n]. O zaman alçaq və yüksək arasındakı tək rəqəmlər bərabər olacaqdır:
say [aşağı, yüksək] = say [yüksək] - say [aşağı-1].

Tək bir Ədədləri İnterval Aralığı Leetcode həllində sayın

İndi [i] saymaq üçün bəzi nümunələr götürürük:

saymaq [1] = 1
saymaq [2] = 1
saymaq [3] = 2
saymaq [4] = 2
saymaq [5] = 3

[N] = (n + 1) / 2 sayını çıxara bilərik
Beləliklə say [aşağı, yüksək] = (yüksək + 1) / 2 - aşağı / 2

Həyata keçirilməsi

C ++ Proqramı (Sadəlövh Yanaşma) İnterval Aralığındakı Leetcode həllində tək ədədlər üçün

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
    int count=0;
    for(int i=low;i<=high;i++)
        if(i%2==1) count++;
        
    return count;
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

Interval Range Leetcode həllində tək nömrələri saymaq üçün Java proqramı (sadəlövh yanaşma)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        int count=0;
        for(int i=low;i<=high;i++)
            if(i%2==1) count++;
        
        return count;
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

C ++ Proqramı (Optimum Yanaşma)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
   return (high + 1) / 2 - low / 2;       
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

Java Proqramı (Optimum Yanaşma)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        return (high + 1) / 2 - low / 2;   
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

Interval Range Leetcode həllində tək nömrələrin sayı üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

Hər bir nömrə üçün səyahət etmək lazımdır O (n) düsturdan istifadə edərək ans hesablanarkən zaman mürəkkəbliyi daimi vaxt tələb edir O (1) icra etmək.

Kosmik Mürəkkəblik 

O (1): Ans-ləri saxlamaq üçün istifadə olunan dəyişən xaricində hər iki həlldə əlavə yer istifadə olunmur.

Şərh yaz

Translate »
1