Տեղադրեք միջանկյալ Leetcode լուծում  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon խնձոր facebook Google LinkedIn Microsoft Պատգամախոս ServiceNow- ը ծլվլոց Uber
ալգորիթմները Դասավորություն կոդավորում Դատամինր հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions Տեսակ

Insert Interval Leetcode Solution- ի խնդիրը մեզ տալիս է որոշ ընդմիջումների ցուցակ և մեկ առանձին ընդմիջում: Հետո մեզ ասում են, որ այս նոր ընդմիջումը տեղադրենք ընդմիջումների ցուցակի մեջ: Այսպիսով, նոր ընդմիջումը կարող է հատվել այն ընդմիջումներով, որոնք արդեն կան ցուցակում, կամ կարող է ոչ: Խաչմերուկ լինելու դեպքում մենք միացնում ենք ընդմիջումները: Հակառակ դեպքում մենք պարզապես տեղադրում ենք մի դիրքում, երբ այն հետևում է ընդմիջումների ցուցակի աճման կարգին:

Տեղադրեք միջանկյալ Leetcode լուծումPin

Օրինակ  

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

Բացատրություն. Նոր միջակայքը հատվում է ցուցակի առաջին ընդմիջման հետ: Այսպիսով, նոր ընդմիջումը միաձուլվում է առաջին ընդմիջման հետ: Եվ այդպես մեզ մնում է տրված արդյունքը:

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

Բացատրություն. Ի սկզբանե, քանի որ ցուցակում ընդմիջումներ չկային: Մենք պարզապես տեղադրեցինք նոր ընդմիջումը:

Տեղադրեք ինտերվալային Leetcode լուծման մոտեցումը  

Insert Interval Leetcode Solution- ի խնդիրը մեզ տրամադրեց որոշ ընդմիջումներ և լրացուցիչ ընդմիջում, որը պետք է տեղադրվի: Այսպիսով, մենք կարող ենք լուծել խնդիրը, եթե կարողանանք մոդելավորել հնարավորությունները, որոնք կարող են առաջանալ: Կա երկու հնարավորություն. Կա՛մ նոր միջակայքը հատվում է ցուցակում արդեն իսկ առկա միջակայքերի հետ, կա՛մ չի համապատասխանում: Այսպիսով, եթե դա անում է, մենք պարզապես դրանք միաձուլում ենք, և ընդմիջումը դնում ենք որոշակի դիրքում: Հատուկ դիրքորոշում ասելով `մենք նկատի ունենք, որ ցուցակում աճման կարգը պահպանվում է նույնիսկ տեղադրումից հետո:

Տես նաեւ,
Բոլոր նարինջները փտելու համար անհրաժեշտ նվազագույն ժամանակը

Այսպիսով, դրանով զբաղվելու համար մենք ստեղծում ենք նոր վեկտոր (դասավորություն) վեկտորների: Մենք սկսում ենք ինտերվալները ներմուծել այս նորաստեղծ ելքային վեկտորի մեջ: Մենք ստուգում ենք, արդյոք ընթացիկ միջակայքը համընկնում է տեղադրվող ընդմիջման հետ: Եթե ​​դրանք տեղի ունենան, ապա մենք դուրս ենք գալիս օղակից: Օղակից հետո մենք ստուգում ենք, թե արդյոք համընկնող տարրը ցուցակում առկա ընդմիջումներից է: Եթե ​​դրանք համընկնում են, մենք միաձուլում ենք ընթացիկ ընդմիջումը նոր ընդմիջման հետ և տեղադրում ենք մնացած ընդմիջումները: Բայց եթե դրանք չեն, ապա մենք տարրերը ներմուծում ենք ելքային վեկտորի մեջ, մինչև ընդմիջման մեկնարկային դիրքը պակաս լինի տեղադրվող միջակայքի մեկնարկային դիրքից: Դրանից հետո մենք պարզապես տեղադրում ենք նոր ընդմիջում, ապա `մնացած ընդմիջումներով:

Կոդ  

C ++ կոդ `Interval Leetcode Solution- ի ներդրման համար

#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 լուծման Java կոդ

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պարզապես անցել ենք ցուցակի վրայով և ընդմիջումները մտցրել ելքային վեկտորի մեջ: Այսպիսով, այս բոլոր գործողությունները գծային ժամանակ են պահանջում:

Տես նաեւ,
Նվազագույն հեռավորությունը BST հանգույցների միջև Leetcode Solution

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք ստեղծեցինք վեկտորների նոր վեկտոր, որը պահում է N կամ N + 1 տարրերը: Տիեզերական բարդությունը նույնպես գծային է:

1