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.
Mündəricat
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
- İ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 - 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:
- Fikir həmişə saxlamaqdır maksimum məhsul pəncərəsi az k;
- 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);
- 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, Zamanvə il.
Referans: https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples
