ჩადეთ ინტერვალის Leetcode ამოხსნა


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Apple Facebook Google LinkedIn microsoft Oracle სერვისი Twitter Uber
Array დათამინრ დალაგება

პრობლემა ჩადეთ ინტერვალი Leetcode Solution გვაწვდის რამდენიმე ინტერვალის ჩამონათვალს და ერთ ცალკე ინტერვალს. შემდეგ გვეუბნებიან, რომ ეს ახალი ინტერვალი ჩადეთ ინტერვალების სიაში. ასე რომ, ახალი ინტერვალი შეიძლება გადაკვეთოს ინტერვალებით, რომლებიც უკვე სიაშია, ან შეიძლება არა. გადაკვეთის შემთხვევაში, ჩვენ ვაერთიანებთ ინტერვალებს. წინააღმდეგ შემთხვევაში, ჩვენ უბრალოდ ჩავსვამთ იმ პოზიციას, სადაც ის მიჰყვება ინტერვალთა სიის აღმავალ რიგს.

ჩადეთ ინტერვალის Leetcode ამოხსნა

მაგალითი

intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]

განმარტება: ახალი ინტერვალი იკვეთება სიაში პირველ ინტერვალთან. ასე რომ, ახალი ინტერვალი ერწყმის პირველ ინტერვალს. და ასე გვრჩება მოცემული შედეგი.

intervals = [], newInterval = [0,5]
[0,5]

განმარტება: თავდაპირველად, რადგან სიაში არ იყო ინტერვალი. ჩვენ უბრალოდ ჩავსვით ახალი ინტერვალი.

მიდგომა ჩასმა ინტერვალის Leetcode ამოხსნისთვის

პრობლემა Leetcode Solution ინტერვალის ჩასმა მოგვცა გარკვეული ინტერვალებით და დამატებითი ინტერვალით, რომელიც უნდა ჩასვათ. ამრიგად, პრობლემის მოგვარება შეგვიძლია, თუ შეგვიძლია წარმოვიდგინოთ შესაძლებლობების სიმულაცია. ორი შესაძლებლობა არსებობს, ან ახალი ინტერვალი იკვეთება სიაში უკვე არსებული გარკვეული ინტერვალებით, ან არა. თუ ასეა, ჩვენ უბრალოდ ვუერთდებით მათ და ვათავსებთ ინტერვალს კონკრეტულ პოზიციაზე. სპეციფიკური პოზიციის თანახმად, ჩვენ ვგულისხმობთ, რომ სიაში აღმავალი რიგი შენარჩუნებულია ჩასმის შემდეგაც.

ასე რომ, ამის გასაკეთებლად ჩვენ ვქმნით ახალ ვექტორს (მასივი) ვექტორების. ჩვენ დავიწყებთ ინტერვალების ჩასმას ამ ახლად შექმნილ გამომავალ ვექტორში. ჩვენ ვამოწმებთ, ახლდება თუ არა მიმდინარე ინტერვალი ჩასასმელად ინტერვალს. თუ ისინი ასე იქცევიან, ჩვენ გამოვდივართ მარყუჟიდან. მარყუჟის შემდეგ, ჩვენ ვამოწმებთ არის თუ არა გადახურული ელემენტი სიაში მოცემულ ინტერვალებს შორის. თუ ისინი გადახურვაა, ჩვენ ვაერთიანებთ მიმდინარე ინტერვალს ახალ ინტერვალთან და ჩავსვამთ დანარჩენ ინტერვალებს. თუ ეს ასე არ არის, მაშინ ელემენტებს ჩასვამთ გამომავალ ვექტორში, სანამ ინტერვალის საწყისი პოზიცია არ იქნება ჩასმული ინტერვალის საწყისი პოზიციაზე ნაკლები. შემდეგ უბრალოდ ჩავსვამთ ახალ ინტერვალს და შემდეგ დანარჩენ ინტერვალებს.

კოდი

C ++ კოდი ინტერვალის Leetcode ამოხსნის ჩასმა

#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

ჯავა კოდი ჩასმა ინტერვალით Leetcode Solution

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

სირთულის ანალიზი

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

O (N), რადგან ჩვენ უბრალოდ გადავკვეთეთ სიას და ჩასვით ინტერვალი გამომავალ ვექტორში. ასე რომ, ყველა ეს ოპერაცია ხაზოვან დროს იღებს.

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

O (N), რადგან ჩვენ შევქმენით ვექტორების ახალი ვექტორი, რომელიც ინახავს N ან N + 1 ელემენტებს. სივრცის სირთულე ასევე ხაზოვანია.