Интерактивті шешім кодын енгізу


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма Facebook Google LinkedIn Microsoft Oracle ServiceNow Twitter қиятын
Array DataMiner сорт

Leetcode Solution интервалын енгізу проблемасы бізге кейбір аралықтардың тізімін және бір бөлек аралықты ұсынады. Содан кейін бізге осы жаңа аралықты интервалдар тізіміне енгізу керек дейді. Сонымен, жаңа интервал тізімдегі интервалдармен қиылысуы мүмкін немесе болмауы мүмкін. Егер қиылысу болса, біз интервалдарды біріктіреміз. Әйтпесе, біз жай интервалдар тізімінің өсу ретімен жүретін жерге орналастырамыз.

Интерактивті шешім кодын енгізу

мысал

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

Түсініктеме: жаңа интервал тізімдегі бірінші интервалмен қиылысады. Сонымен жаңа интервал бірінші интервалмен біріктіріледі. Міне, осылайша бізге берілген нәтиже қалады.

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

Түсініктеме: Бастапқыда, өйткені тізімде интервал болмаған. Біз жай ғана жаңа аралықты енгіздік.

Leetcode интервалын енгізу әдісі

Leetcode Solution интервалын енгізу мәселесі бізге кейбір интервалдар мен қосымша интервал берді. Сонымен, туындауы мүмкін мүмкіндіктерді имитациялай алсақ, біз мәселені шеше аламыз. Екі мүмкіндік бар, немесе жаңа интервал тізімде бар кейбір аралықтармен қиылысады немесе жоқ. Сонымен, егер ол орын алса, біз оларды біріктіреміз, әйтпесе аралықты белгілі бір позицияға орналастырамыз. Белгілі бір позиция бойынша біз тізімдегі өсу реті енгізілгеннен кейін де сақталады дегенді білдіреді.

Сонымен, мұны шешу үшін біз жаңа вектор құрамыз (массив) векторлардың. Біз интервалдарды осы жаңа құрылған векторға енгізе бастаймыз. Ағымдағы интервалдың енгізілетін аралықпен сәйкес келетіндігін тексереміз. Егер олар істесе, онда біз циклден шығамыз. Циклдан кейін біз қабаттасатын элементтің тізімдегі интервалдар арасында екенін тексереміз. Егер олар қабаттасса, біз ағымдағы интервалды жаңа интервалмен біріктіріп, қалған интервалдарды енгіземіз. Бірақ егер ол болмаса, онда элементтерді шығыс векторына интервалдың бастапқы позициясы енгізілетін интервалдың бастапқы позициясынан аз болғанша енгіземіз. Содан кейін біз тек жаңа интервалды, содан кейін қалған аралықтарды енгіземіз.

код

Insert Interval Leetcode Solution үшін C ++ коды

#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 үшін 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

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені біз тізімнен өтіп, аралықтарды шығару векторына енгіздік. Сонымен, бұл операциялардың барлығы сызықтық уақытты алады.

Ғарыштың күрделілігі

O (N), өйткені біз N немесе N + 1 элементтерін сақтайтын векторлардың жаңа векторын жасадық. Кеңістіктің күрделілігі де сызықтық болып табылады.