Leetcode-ийн уусмалаар массив үүсэхийг шалгана уу


Хэцүү байдлын түвшин Easy
Байнга асуудаг Uber
Array CodeSignal HashMap эрэмбэлэх

Leetcode Solution-ийг нэгтгэх замаар массив үүсэхийг шалгах нь бидэнд олон массивыг өгсөн. Үүнтэй хамт бидэнд дараалал өгдөг. Дараа нь бид өгөгдсөн дарааллыг ашиглан ямар нэгэн байдлаар бүтээж чадах эсэхийг олохыг бидэнд хэлэв массив массив. Бид хүссэн дарааллаараа массивыг байрлуулж болно. Гэхдээ бид массив доторх элементүүдийг өөрчилж чадахгүй. Массивын массивт бүхэл тоонууд давтагдашгүй байдаг гэж бидэнд хэлдэг. Тиймээс шийдлийг авч үзэхээсээ өмнө цөөн хэдэн жишээг авч үзэх хэрэгтэй.

Leetcode-ийн уусмалаар массив үүсэхийг шалгана уу

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

Тайлбар: Бид элементүүдийг урвуу дарааллаар байрлуулж болно. 15-ийн сүүлчийн массив урд гарч ирнэ. Үүнтэй адилаар эхний элемент буцаж орно. Энэ аргаар бид өгөгдсөн массивыг бүрдүүлж чадна.

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

Тайлбар: Хэрэв бид эхлээд сүүлчийн элементийг нэгтгэвэл дунд массив, эцэст нь эхний массивыг нэгтгэнэ. Энэ аргаар бид шаардлагатай дарааллыг олж авах боломжтой.

Leetcode шийдлийг нэгтгэх замаар шалгах массивыг бий болгох арга

Leetcode Solution-ийг нэгтгэх замаар массивын формацийг шалгах нь массиваас шаардлагатай дарааллыг авч чадах эсэхийг шалгахыг биднээс хүссэн юм. Асуудал нь бүх боломжуудыг шалгах шаардлагатай тул рекурсив шинжтэй байх шиг байна. Рекурсив хэлбэрээр бид эхлээд массивыг сонгоод дараа нь тухайн массив тохирох эсэхийг шалгаж дараа нь дарааллыг дуустал ижил үйлдлийг хийнэ. Гэхдээ энд байгаа давуу тал бол өвөрмөц элементүүд юм. Тиймээс бид зөвхөн массивын эхний элементтэй зөвхөн эхний элементийг шалгана. Үүнийг шалгасан ч гэсэн бид сонгосон массивыг үргэлжлүүлж чадна гэдэгт итгэлтэй байх болно.

Массивыг сонгосны дараа бид массивыг дарааллын бүх элементүүдтэй эсэхийг шалгах хүртэл бүх элементүүдээр дамжин өнгөрнө. Ядарсны дараа ижил процесс давтагдана. Хэрэв массивын элемент ба дараалалд таарахгүй байгаа бол бид худал гэсэн утгыг буцаана. Эцэст нь үл тохирох зүйл олоогүй тохиолдолд бид үнэн болно.

Leetcode шийдэлтэй холбож шалгах массив үүсгэх код

C ++ код

#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 код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), энд N нь өгөгдсөн дарааллын элементүүдийн нийт тоо юм. Ашигладаг тул цаг хугацааны нарийн төвөгтэй байдал шугаман болж буурсан HashMap.

Сансрын нарийн төвөгтэй байдал

O (M), энд M нь массивын массивын тоо юм.