Birləşdirmə Leetcode həll yolu ilə bir sıra meydana gəlməsini yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Über
alqoritmlər Geyim Code Signal kodlaşdırma HashMap müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions CürBaxılıb 25

Birləşdirmə Leetcode Həll yolu ilə Bir Array Oluşumunu Yoxlayın problemi bizə bir sıra seriallar təqdim etdi. Bununla yanaşı bizə bir ardıcıllıq da verilir. Sonra bizə verilən ardıcıllığı birtəhər qura biləcəyimizi tapmağımız tapşırılır array massivlər. Dizileri istədiyimiz sırada düzəldə bilərik. Ancaq sıra içindəki elementləri yenidən düzəldə bilmərik. Tamsayıların massiv massivində misilsiz olduğu da bildirilir. Buna görə həll yoluna nəzər yetirmədən əvvəl bir neçə nümunəyə nəzər yetirməliyik.

Birləşdirmə Leetcode həll yolu ilə bir sıra meydana gəlməsini yoxlayınPin

arr = [15,88], pieces = [[88],[15]]
true

İzahat: Elementləri tərs qaydada düzəldə bilərik. Beləliklə 15 olan son sıra önə gələcək. Eynilə, ilk element də geri dönəcəkdir. Bu şəkildə verilmiş massivi əmələ gətirə bilərik.

arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
true

İzahat: Əvvəlcə son elementi birləşdirsək, orta sıra, sonunda isə birinci sıra. Bu şəkildə lazımi ardıcıllığı əldə edə bilərik.

Birləşdirmə Leetcode həll yolu ilə yoxlama massivinin formalaşmasına yanaşma

Birləşdirmə Leetcode Həll yolu ilə Bir Array Oluşumunu Yoxlayın problemi bizdən seriallardan lazımi ardıcıllığı ala biləcəyimizi yoxlamağımızı istədi. Problem, bütün imkanları yoxlamalı olduğumuz təkrarlanan bir problem kimi görünür. Rekursiv bir şəkildə əvvəlcə bir sıra seçməyə çalışırıq və sonra cari massivin uyğun olub olmadığını yoxlayırıq, sonra ardıcıllığı tükənənə qədər eyni əməliyyatı həyata keçiririk. Ancaq buradakı üstünlük misilsiz elementlərdir. Beləliklə, yalnız ilk elementi ilk element elementləri ilə yoxlayırıq. Bunu yoxlamaqla belə, seçilmiş sıra ilə irəliləyə biləcəyimizə əmin olacağıq.

Bir sıra götürdükdən sonra, içindəki bütün elementləri dizinin bütün elementlərinə sahib olub olmadığını yoxlayaraq onu tükəndiririk. Tükəndikdən sonra eyni proses təkrarlanır. Dizinin elementində və ardıcıllıqda bəzi uyğunsuzluq varsa, false olaraq qayıdırıq. Sonda heç bir uyğunsuzluq tapmadıqda gerçəkləşirik.

Birləşdirmə Leetcode həll yolu ilə yoxlama massivinin formalaşması üçün kod

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
    unordered_map<int,int> entry;
    for(int i=0;i<pieces.size();i++)
        entry[pieces[i][0]] = i;
    int i =  0;
    while(i < arr.size()){
        if(entry.count(arr[i])){
            vector<int> &piece  = pieces[entry[arr[i]]];
            for(auto x: piece)
                if(x != arr[i++])
                    return false;
        } else {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> arr = {91, 4, 64, 78};
    vector<vector<int>> pieces = {{78},{4,64},{91}};
    cout<<(canFormArray(arr, pieces) ? "true" : "false");
}
true

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canFormArray(int[] arr, int[][] pieces) {
        HashMap<Integer, Integer> entry = new HashMap<Integer, Integer>();
        for(int i=0;i<pieces.length;i++)
            entry.put(pieces[i][0], i);
        int i =  0;
        while(i < arr.length){
            if(entry.containsKey(arr[i])){
                int n = pieces[entry.get(arr[i])].length;
                int k = entry.get(arr[i]);
                for(int j=0;j<n;j++)
                    if(pieces[k][j] != arr[i++])
                        return false;
            } else {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[] arr = {91, 4, 64, 78};
      int[][] pieces = {{78},{4,64},{91}};
      System.out.print(canFormArray(arr, pieces) ? "true" : "false");
  }
}
true

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N - verilən ardıcıllıqdakı elementlərin ümumi sayı. Zamanın mürəkkəbliyi istifadə olunduğundan xətti azaldıldı HashMap.

Kosmik mürəkkəblik

O (M), burada M - massivlər massivindəki massivlərin sayı.

Şərh yaz

Translate »
1