1s sayını 0s sayından bir çox olan ən uzun subarray

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Biz verdik array tam ədədi. Bir sıra yalnız 1 və 0'dan ibarətdir. Problem ifadəsi, 1 rəqəmli kəmiyyətinin bir alt serialdakı 0 sayından yalnız bir çox olduğu ən uzun Sub-Arrayın uzunluğunu tapmağı xahiş edir.

misal

Input:

arr [] = {1,0,1,1,0,0,0}

Çıxış:

5

Explanation:

0-dan 4-ə qədər göstərici, {1, 0, 1, 1, 0}, üçü var 1 və iki 0. 1-dən 0-dan daha çox say.

Input:

arr [] = {1,0,1,0,0}

Çıxış:

3

Explanation:

0-dan 2-yə qədər, {1, 0, 1}, iki 1 və bir 0 var. 1-dən 0-dan daha çox say.

Alqoritm

1. Xəritəni elan edin.
2. Cəmi və outputLength-i 0-a qoyun.
3. I = 0-dan i <n-ə qədər sıra ilə hərəkət edin.
   1. Arr [i] -in 0-a bərabər olub olmadığını yoxlayın, sonra true-a əlavə edin.
   2. Başqa cəmi +1 əlavə edin.
   3. Olmadığını yoxlayın cəmi bərabərdir 1-ə, sonra outputLength dəyərini 1 artırın.
   4. Başqa bir vəziyyətdə, xəritənin cəmi olub olmadığını yoxlayın, əgər doğrudursa, cəmini və cari dəyərini cəmi ilə birlikdə xəritəyə qoyun.
   5. Bir xəritədə (cəmi-1) olub-olmadığını yoxlayın.
   6. OutputLength i-indeksdən azdırsa (cəmi xəritədəki dəyər).
      1. Doğrudursa, onda outputLength-i indeksinə qədər yeniləyin.
4. Çıxış uzunluğunu qaytarın.

Izahat

Elan edəcəyik xəritə. Həmin xəritədə, şərt yerinə yetərsə cəmi və indeksin cari dəyərini saxlayacağıq. İki dəyişən götürün və cəmi 0-a, outputLength-i 0-a qoyun. Massivdən keçərkən bir sıra hər bir elementini seçəcəyik və arr [i] -nin 0-a bərabər olub olmadığını yoxlayırıq, bərabər olduğu aşkar edilərsə əlavə edəcəyik Cəmləmək üçün -1 və onu cəmləmək üçün saxlayırıq, əks halda 0 olduğunu tapmadıqda, cəmləmək üçün müsbət 1 əlavə edəcəyik və cəm olaraq saxlayacağıq.

Bu mənfi 1 və müsbət 1-in səbəbi budur ki, biz 0-u -1 kimi göstəririk və 1-i əlavə edirik, beləliklə 0-u həmişə əldə edəcəyik. Ancaq cəmdə müsbət 1-i yoxlayacağıq, bu da 1-un sayından sonra əlavə 0-ə sahib olacağımızı göstərir.

Fərz edək ki, 1-ı -0 kimi göstərsək, 1, 0, 1-i alacağıq, ilk 0 rəqəmi ilə 2-ı alacağıq və üçüncü nömrə ilə şərtimizin yerinə yetirildiyini tapa bilərik. 1-dən 0-ə bərabər bir 1-dan çox əlavə sayla 0-a bərabər bir sıra əldə etdik. Vəziyyətimizi təmin edirik. Buna görə cəmi bir alqoritmin növbəti mərhələsində 1-ə bərabər olub olmadığını və outputLength uzunluğunu yeniləyəcəyini axtaracağıq. Sonuncusu, əgər bəyanat, yeni çıxış uzunluğunu əldə etsək, əvvəlkini cari outputLength ilə yeniləməyimiz lazımdır və outputLength-i qaytaracağıq.

Həyata keçirilməsi

C ++ proqramı, ən uzun subarray üçün 1s sayını 0s sayından bir çox etmək

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}

Length of the longest Sub-Array : 5

Ən uzun Subarray üçün 1s sayını 0s sayından bir dəfə çox olmaq üçün Java proqramı

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}

Length of the longest Sub-Array : 5

Sayı sayı 1-dan çox 0s-ə bərabər olan ən uzun subarray üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara "N"  massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N"  massivdəki elementlərin sayıdır.