Проверка формирования массива с помощью решения Leetcode для конкатенации  


Сложный уровень Легко
Часто спрашивают в Uber
алгоритмы массив CodeSignal кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Сортировать

Проблема Проверить формирование массива с помощью конкатенации 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 попросила нас проверить, можем ли мы получить требуемую последовательность из массива массивов. Проблема кажется рекурсивной, и нам нужно проверить все возможности. Рекурсивным образом мы сначала пытаемся выбрать массив, а затем проверяем, подходит ли текущий массив, а затем выполняем ту же операцию, пока не исчерпаем последовательность. Но преимущество, которое у нас есть, - это уникальные элементы. Итак, мы просто проверяем только первый элемент с первым элементом массивов. Даже проверка этого гарантирует, что мы сможем продолжить работу с выбранным массивом.

Смотрите также
Запись о посещаемости студентов I Leetcode Solution

После выбора массива мы просматриваем все элементы в нем, проверяя, есть ли в массиве все элементы последовательности, пока не исчерпаем его. После истощения повторяется тот же процесс. Если есть несоответствие в элементе массива и последовательности, мы возвращаем false. В конце концов, когда мы не находим несоответствия, мы возвращаем true.

Код для проверки формирования массива с помощью решения 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

Анализ сложности  

Сложность времени

НА), где N - общее количество элементов в данной последовательности. Сложность времени была уменьшена до линейной из-за использования HashMap.

Пространство сложности

О (М), где M - количество массивов в массиве массивов.

1