მაქსიმალური თანმიმდევრული პირობა Leetcode Solution


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

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

Max ზედიზედ პრობლემებში მოცემულია ორობითი მასივი. ჩვენ უნდა ვიპოვოთ ზედიზედ მაქსიმალური რაოდენობა მოცემულ მასივში.
შეყვანის მასივი შეიცავს მხოლოდ 0 და 1-ს.

მაგალითი

[1,1,0,1,1,1]
3

განმარტება:
პირველი ორი ციფრი ან ბოლო სამი ციფრი ზედიზედ 1-ია.
ზედიზედ 1-ების მაქსიმალური რაოდენობაა 3.

[0,1,0]
1

განმარტება:
ზედიზედ 1-ების მაქსიმალური რაოდენობაა 1.

მიდგომა

ამ პრობლემის გადასაჭრელად მასივის ინდექსების საშუალებით შეგვიძლია განმეორება ორ ნაწილად მარყუჟის წყობილი შემდეგი ალგორითმით:

1. შექმენით ცვლადი მაქსიმუმი, რომელიც ინახავს განახლებულ მაქსიმალურ ზედიზედ 1-ებს გადაკვეთის დროს.
2. პირველი ინდექსის მქონე i ცვლადის შექმნა და ინიცირება.
3. ახლა გაუშვით რგოლიანი ხაზი, სანამ მე <მასივის ზომა.
4. მარყუჟის შიგნით შეამოწმებთ არის თუ არა ნომერი მიმდინარე ინდექსში i 1 თუ არა. თუ ეს არ არის 1-ის ტოლი, მაშინ i გაზრდის ინდექსს. სხვა, თუ ის უდრის 1-ს, მაშინ აწარმოე ჩამონტაჟებული while მარყუჟი თვლადი ცვლადის შექმნით და ინიციალიზაცია 0-ით. შემდეგ გადააადგილეთ მასივი ზედიზედ 1s- ისთვის ამ ჩამონტაჟებულ მარყუჟში. ტრავერსის მასივი, ხოლო num [i] უდრის 1 – ს, ამასთან ერთად იზრდება მიმდინარე ზედიზედ 1 –ების რაოდენობა, როგორც ნაჩვენებია ქვემოთ მოცემულ ფიგურაში:

მაქს თანმიმდევრები
5. მასივის 0-ის ან მასალის ბოლოს შეხვედრის შემდეგ განაახლეთ მაქსიმალური ცვლადი მისი ძველი მნიშვნელობის შედარებით, რიცხვის ცვლადში შენახული 1 თანმიმდევრული რიცხვის მიმდინარეობით.
6. სანამ loop ასრულებს დააბრუნე მაქსიმალური მნიშვნელობა.

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

C ++ პროგრამა მაქსიმალური თანმიმდევრული პირებისათვის Leetcode Solution

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

int findMaxConsecutiveOnes(vector<int>& nums) {

    int maximum=0;
    int i=0;

    while(i<nums.size())
    {
        int conOnes=0;
        while(i< nums.size() && nums[i]==1)
        {
            conOnes++;
            i++;
        }

        maximum=max(maximum,conOnes);
        i++;
    }

    return maximum; 
}

int main() 
{
    vector<int> nums={1,1,0,1,1,1};
    cout<<findMaxConsecutiveOnes(nums)<<endl;

  return 0; 
}
3

ჯავა პროგრამა მაქსიმალური თანმიმდევრული პირებისათვის Leetcode Solution

import java.lang.*;

class MaxOnes
{  
    public static int findMaxConsecutiveOnes(int[] nums) 
    {
        int maximum=0;
        int i=0;

        while(i<nums.length)
        {
        int conOnes=0;
        while(i< nums.length && nums[i]==1)
        {
        conOnes++;
        i++;
        }

        maximum=Math.max(maximum,conOnes);

        i++;
        }

        return maximum; 

    }
    
    public static void main(String args[])
    {
        int nums[]={1,1,0,1,1,1};

        System.out.println(findMaxConsecutiveOnes(nums));
        
    }
}
3

სირთულის ანალიზი მაქს ზედიზედ ლეეტკოდული ამოხსნისთვის

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

O (N): ჩვენ ვაკვირდებით მასივს ინდექსის დაწყებიდან ბოლო ინდექსამდე და მხოლოდ ერთხელ ვნახულობთ თითოეულ ინდექსს. ამიტომ დროის სირთულე იქნება წრფივი O (N).

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

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