Subarray Məhsulu K-dən Az LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Facebook LinkedIn microsoftBaxılıb 74

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.

Problem bəyanat

K-dən kiçik subbarray məhsulu LeetCode Həlli – Tam ədədlər massivi verilmişdir nums və tam ədəd k, qayıt alt massivdəki bütün elementlərin hasilinin ciddi şəkildə az olduğu bitişik alt massivlərin sayı k.

misal

Test işi 1:

Input:

inputArr = [10, 5, 2, 6]

k = 100

Çıxış:

8

Test işi 2:

inputArr = [1,2,3]
k = 0

Çıxış:

0

K-dən az olan Subarray Məhsulu üçün izahat LeetCode Həlli:

i) 1-ci sınaq işi üçün məhsulu 100-dən az olan alt massivlər bunlardır: [10], [5], [2], [6], [10. 5], [5, 2], [2, 6], [5, 2 ,6]. Beləliklə, ümumi sayı 8-dir.

ii) 2-ci sınaq işi üçün məhsulu 0-dan kiçik olan heç bir alt massiv yoxdur. Beləliklə, nəticə 0-dır.

Yanaşma

  1. İdeya, məhsulu k-dən az olan bir pəncərə etməkdir.
    sol: pəncərənin başlanğıc nöqtəsi
    Sağda: massivdən (və ya pəncərənin sonundan) keçəcək göstərici
  2. A[sağ] daxil edildikdən sonra 2 Mümkün Hal var:

    MƏHSUL 1: məhsul k-dən azdır
    Bu o deməkdir ki, mən əvvəlki Altarrayların bir hissəsi ola bilərəm (sağ-sol) və həmçinin məndən (+1) alt massiv başlaya bilərəm.
    Beləliklə, ümumi olaraq alt xətlər sayını artırır (sağ-sol+1)

    MƏHSUL 2: Məhsul k-dən böyük olacaq
    Məhsul k-dən az olana qədər elementi soldan buraxmağa başlayın.
    İndi 1-ci Case ilə eyni məntiq.

    Verilmiş məhdudiyyətə əsasən: k>=0 və massivdəki qiymətlər s/b 0-dan 1000-ə qədər ola bilər.
    Məhsulları k-dan ciddi şəkildə kiçik olan alt massivləri istədiyimiz kimi.
    belə ki, əgər (k<=1) 0 qaytarır.
    və xoşbəxtlikdən burada nömrə hasilinin Integer.Max Range-i keçməsi ilə bağlı probleminiz yoxdur.

Idea:

  1. Fikir həmişə saxlamaqdır maksimum məhsul pəncərəsi az k;
  2. Hər dəfə sağa (j) yeni bir nömrə əlavə edərək pəncərəni dəyişdirin, əgər məhsul k-dən böyükdürsə, alt massiv məhsulu ondan kiçik olana qədər soldakı (i) nömrələri azaltmağa çalışın. k yenə, (alt sətir boş ola bilər);
  3. Hər bir addım təqdim edir x yeni alt massivlər, burada x cari pəncərənin ölçüsüdür (j-i+1).

Bu, əsasən dəyişən ölçülüdür sürüşmə pəncərəsi problem.

Kodu

Java Proqramı

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) return 0;
        int cnt = 0;
        int pro = 1;
        for (int i = 0, j = 0; j < nums.length; j++) {
            pro *= nums[j];
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;        
    }
}

C ++ Proqramı

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int cnt = 0;
        int pro = 1;
        for (int i = 0, j = 0; j < nums.size(); j++) {
            pro *= nums[j];
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;
    }
};

Python proqramı

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k == 0:
            return 0
        start, prod, cnt = 0, 1, 0
        for end in range(len(nums)):
            while start <= end and prod*nums[end] >= k:
                prod = prod/nums[start]
                start += 1
            prod = 1 if start > end else prod*nums[end]
            cnt = cnt if start > end else cnt+(end-start+1)
        return cnt

LeetCode Həlli K-dən az olan Subarray Məhsulu üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

, Harada N uzunluğu nömrə. Zaman yalnız maksimum artırıla bilər N dəfə.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1), istifadə etdiyi yer prod, Zamanil.

Referans: https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples

Crack Sistemi Dizayn Müsahibələri
Translate »