Праверце фарміраванне масіва шляхам канкатэнацыі рашэння Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Uber
масіў CodeSignal HashMap Род

Праблема "Праверка фарміравання масіва шляхам канкатэнацыі рашэння Leetcode" прадаставіла нам масіў масіваў. Разам з гэтым нам таксама дадзена паслядоўнасць. Затым нам кажуць, ці можам мы нейкім чынам пабудаваць зададзеную паслядоўнасць масіў масіваў. Мы можам размясціць масівы ў любым парадку, які хочам. Але мы не можам пераставіць элементы ўнутры масіва. Нам таксама кажуць, што цэлыя лікі ўнікальныя ў масіве масіваў. Такім чынам, перш чым зірнуць на рашэнне, мы павінны зірнуць на некалькі прыкладаў.

Праверце фарміраванне масіва шляхам канкатэнацыі рашэння Leetcode

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

Тлумачэнне: Мы можам размясціць элементы ў зваротным парадку. Такім чынам, апошні масіў, які складае 15, выйдзе наперадзе. Аналагічна, першы элемент пойдзе назад. Такім чынам мы можам сфармаваць дадзены масіў.

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

Тлумачэнне: Калі спачатку аб'яднаць апошні элемент, потым сярэдні масіў і ў рэшце рэшт першы масіў. Такім чынам мы можам атрымаць неабходную паслядоўнасць.

Падыход да фарміравання праверкі масіва шляхам канкатэнацыі рашэння Leetcode

Праблема Праверка фарміравання масіва шляхам канкатэнацыі Леткод-рашэнне папрасіла нас праверыць, ці можна атрымаць патрэбную паслядоўнасць з масіва масіваў. Здаецца, праблема рэкурсіўная, дзе нам трэба праверыць усе магчымасці. Рэкурсіўна мы спачатку спрабуем выбраць масіў, а потым праверыць, ці прыдатны бягучы масіў, а потым выконваем тую ж аперацыю, пакуль не вычарпаем паслядоўнасць. Але перавага ў нас тут - унікальныя элементы. Такім чынам, мы проста правяраем толькі першы элемент з першым элементам масіваў. Нават праверыўшы гэта, мы зможам перайсці да выбранага масіва.

Пасля выбару масіва мы праходзім усе элементы ў ім, правяраючы, ці ёсць у масіве ўсе элементы паслядоўнасці, пакуль мы яго не вычарпаем. Пасля знясілення той самы працэс паўтараецца. Калі ў элеменце масіва і паслядоўнасці ёсць несупадзенне, мы вяртаем false. У рэшце рэшт, калі мы не знаходзім несупадзенняў, мы вяртаемся праўдай.

Код для фарміравання чэкавага масіва шляхам канкатэнацыі рашэння 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), дзе М - колькасць масіваў у масіве.