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əsələ Insert Interval Leetcode Solution bizə bəzi aralıqların və bir ayrı aralığın siyahısını təqdim edir. Sonra bizə bu yeni aralığı fasilələr siyahısına əlavə etməyimiz deyilir. Beləliklə, yeni interval artıq siyahıda olan fasilələrlə kəsişir və ya olmaya bilər. Bir kəsişmə olması halında aralıqları birləşdiririk. Əks təqdirdə, sadəcə aralıklar siyahısının artan sırasını izlədiyi bir yerə əlavə edirik.
Mündəricat
misal
intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]
İzahat: Yeni interval siyahının ilk intervalı ilə kəsişir. Beləliklə, yeni interval ilk interval ilə birləşdirilir. Beləliklə, bizə verilən nəticə ilə qalırıq.
intervals = [], newInterval = [0,5]
[0,5]
İzahat: Başlanğıcda siyahıda fasilələr olmadığından. Sadəcə yeni aralığı əlavə etdik.
Insert Interval Leetcode Həlli üçün yanaşma
Problem İnsert Interval Leetcode Solution bizə bəzi fasilələr və əlavə edilməli olan əlavə bir fasilə təqdim etdi. Beləliklə, yarana biləcək imkanları simulyasiya edə bilsək problemi həll edə bilərik. İki ehtimal var, ya da yeni interval siyahıda mövcud olan bəzi fasilələrlə kəsişir və ya olmur. Beləliklə, bunu edərsə, sadəcə onları birləşdiririk, əks halda aralığı müəyyən bir mövqedə yerləşdiririk. Xüsusi mövqe dedikdə, siyahıdakı artan qaydanın daxil edildikdən sonra da qorunması nəzərdə tutulur.
Beləliklə, bunun üçün yeni bir vektor yaradırıq (array) vektorların. Aralıqları bu yeni yaradılan çıxış vektoruna daxil etməyə başlayırıq. Cari aralığın daxil ediləcək arayla üst-üstə düşməyini yoxlayırıq. Edərlərsə, deməli döngədən çıxarıq. Döngədən sonra üst-üstə düşən elementin siyahıda mövcud intervallar arasında olub olmadığını yoxlayırıq. Üst-üstə düşsələr, cari aralığı yeni aralıqla birləşdiririk və qalan aralıqları əlavə edirik. Ancaq etmədikləri təqdirdə, elementləri intervalın başlanğıc yeri daxil ediləcək aralığın başlanğıc mövqeyindən az olana qədər çıxma vektoruna əlavə edirik. Sonra sadəcə yeni aralığı və aralıqların qalan hissəsini əlavə edirik.
Kodu
Insert Interval Leetcode Solution üçün C ++ kodu
#include <bits/stdc++.h>
using namespace std;
bool overlap(vector<int> a, vector<int> b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i;
vector<vector<int>> newIntervals;
for(i=0;i<intervals.size();i++)
if(overlap(intervals[i], newInterval))
break;
else
newIntervals.push_back(intervals[i]);
if(i<intervals.size()){
intervals[i][0] = min(intervals[i][0], newInterval[0]);
intervals[i][1] = max(intervals[i][1], newInterval[1]);
newIntervals.push_back(intervals[i]);
int j = i;
i++;
for(;i<intervals.size();i++)
if(overlap(intervals[j], intervals[i])){
newIntervals[j][0] = min(newIntervals[j][0], intervals[i][0]);
newIntervals[j][1] = max(newIntervals[j][1], intervals[i][1]);
} else
newIntervals.push_back(intervals[i]);
return newIntervals;
}
for(i=0;i<intervals.size();i++)
if(newIntervals[i][0]>newInterval[0])
break;
newIntervals.insert(newIntervals.begin() + i, newInterval);
return newIntervals;
}
int main(){
vector<vector<int>> intervals = {{0,5}};
vector<int> newInterval = {1,6};
vector<vector<int>> output = insert(intervals, newInterval);
for(int i=0;i<output.size();i++)
cout<<output[i][0]<<" "<<output[i][1];
}
0 6
Insert Interval Leetcode Solution üçün Java kodu
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
private static boolean overlap(int[] a, int[] b){
return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}
private static int[][] insert(int[][] intervals, int[] newInterval) {
int i;
ArrayList<Integer[]> newIntervals = new ArrayList<Integer[]>();
for(i=0;i<intervals.length;i++)
if(overlap(intervals[i], newInterval))
break;
else
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
if(i<intervals.length){
intervals[i][0] = Math.min(intervals[i][0], newInterval[0]);
intervals[i][1] = Math.max(intervals[i][1], newInterval[1]);
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
int j = i;
i++;
for(;i<intervals.length;i++)
if(overlap(intervals[j], intervals[i])){
int a = Math.min(intervals[j][0], intervals[i][0]);
int b = Math.max(intervals[j][1], intervals[i][1]);
newIntervals.set(j, new Integer[]{a, b});
} else
newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
return to_return;
}
for(i=0;i<intervals.length;i++)
if(newIntervals.get(i)[0]>newInterval[0])
break;
newIntervals.add(i, new Integer[]{newInterval[0], newInterval[1]});
int[][] to_return = new int[newIntervals.size()][2];
for(i=0;i<to_return.length;i++){
to_return[i][0] = newIntervals.get(i)[0];
to_return[i][1] = newIntervals.get(i)[1];
}
return to_return;
}
public static void main (String[] args) throws java.lang.Exception {
int[][] intervals = {{0,5}};
int[] newInterval = {1,6};
int[][] output = insert(intervals, newInterval);
for(int i=0;i<intervals.length;i++)
System.out.print(output[i][0] + " " + output[i][1]);
}
}
0 6
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (N), çünki sadəcə siyahıdan keçib aralıqları çıxış vektoruna daxil etdik. Beləliklə, bu əməliyyatların hamısı xətti vaxt alır.
Kosmik Mürəkkəblik
O (N), çünki N və ya N + 1 elementlərini saxlayan yeni bir vektor vektoru yaratdıq. Məkan mürəkkəbliyi də xətti.
