დაითვალეთ კენტი რიცხვები ინტერვალის დიაპაზონში Leetcode ამოხსნაში


Რთული ტური Easy
ხშირად ეკითხებიან microsoft
მათემატიკის

პრობლემის განცხადება

ამ პრობლემის დროს, მოცემულია ორი არაუარყოფითი მთელი და დაბალი რიცხვი. უნდა ვიპოვოთ რამდენი უცნაური რიცხვია მოცემული ინტერვალის დიაპაზონში [დაბალი, მაღალი].

მაგალითი

low = 3, high = 7
3

განმარტება:

კენტი რიცხვები 3-სა და 7-ს შორის არის [3, 5, 7].

low = 8, high = 10
1

განმარტება:

კენტი რიცხვები 8-სა და 10-ს შორის არის [9].

მიდგომა

მოცემული ინტერვალის დიაპაზონში კენტი რიცხვების მთლიანი დათვლის ერთი გზაა ინტერვალის მარცხნიდან მარჯვნივ გადაკვეთა loop და გაზარდეთ უცნაური მრიცხველი თითოეული უცნაური რიცხვისთვის. მაგრამ ეს იქნება ძალიან კოჭლი მიდგომა დიაპაზონში უცნაური რიცხვების დათვლისთვის. ამას დასჭირდება ხაზოვანი დროის სირთულე და რომ არ გვინდა ასეთი მარტივი პრობლემა.

მოცემულ ინტერვალის დიაპაზონში ძალიან მარტივია საერთო კენტი რიცხვების პოვნა, რადგან ჩვენ ვიცით, რომ ინტერვალის დიაპაზონში თითქმის ნახევარი ლუწი და ნახევარი უცნაური რიცხვია.
მაგრამ ძალიან ფრთხილად უნდა გავითვალისწინოთ ინტერვალის საზღვრები. რისი გაკეთება შეგვიძლია არის ის, რომ შეგვიძლია ჩამოვაყალიბოთ უცნაური რიცხვების ფორმულა პირველ n ბუნებრივ რიცხვებში. მოდით, ითვლიან [n]. მაშინ უცნაური რიცხვები დაბალსა და მაღალს შორის ტოლი იქნება:
ითვლიან [დაბალი, მაღალი] = ითვლიან [მაღალი] - ითვლიან [დაბალი -1].

დაითვალეთ კენტი რიცხვები ინტერვალის დიაპაზონში Leetcode ამოხსნაში

ახლა რამდენიმე მაგალითის აღება ითვლის [i] - სთვის:

თვლა [1] = 1
თვლა [2] = 1
თვლა [3] = 2
თვლა [4] = 2
თვლა [5] = 3

ჩვენ შეგვიძლია გამოვთვალოთ ეს რიცხვი [n] = (n + 1) / 2
აქედან გამომდინარე რაოდენობა [დაბალი, მაღალი] = (მაღალი + 1) / 2 - დაბალი / 2

განხორციელება

C ++ პროგრამა (გულუბრყვილო მიდგომა) კენტი უცნაური რიცხვების შუა რიცხვებში, Leetcode ამოხსნაში

#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

ჯავას პროგრამა (გულუბრყვილო მიდგომა) უცნაური რიცხვების დათვლისთვის ინტერეტური დიაპაზონის Leetcode ხსნარში

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 ++ პროგრამა (ოპტიმალური მიდგომა)

#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

ჯავის პროგრამა (ოპტიმალური მიდგომა)

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

სირთულის ანალიზი გრაფი უცნაური რიცხვებისთვის ინტერვალური დიაპაზონის Leetcode ამოხსნაში

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

თითოეული ნომრისთვის გადახედვა დასჭირდება O (n) დროის სირთულე ფორმულის გამოყენებით ANS– ის გამოთვლისას მუდმივ დროს მოითხოვს O (1) აღსრულება.

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

O (1): დამატებითი ხსნარი არ გამოიყენება ორივე ხსნარში, გარდა ცვლადისა, რომელიც გამოიყენება შესანახად.