కాంకెటనేషన్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా అర్రే ఫార్మేషన్‌ను తనిఖీ చేయండి  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది ఉబెర్
అల్గోరిథంలు అర్రే కోడ్‌సిగ్నల్ కోడింగ్ హాష్ మ్యాప్ ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions క్రమీకరించు

సమస్య చెక్ అర్రే ఫార్మేషన్ త్రూ కాంకాటనేషన్ లీట్కోడ్ సొల్యూషన్ మాకు శ్రేణుల శ్రేణిని అందించింది. దానితో పాటు మనకు ఒక సీక్వెన్స్ కూడా ఇస్తారు. ఇచ్చిన క్రమాన్ని ఉపయోగించి మనం ఎలాగైనా నిర్మించగలమా అని కనుగొనమని చెబుతారు అమరిక శ్రేణుల. మనకు కావలసిన క్రమంలో శ్రేణులను అమర్చవచ్చు. కానీ మేము శ్రేణిలోని మూలకాలను క్రమాన్ని మార్చలేము. శ్రేణుల శ్రేణిలో పూర్ణాంకాలు ప్రత్యేకమైనవని కూడా మాకు చెప్పబడింది. కాబట్టి పరిష్కారాన్ని పరిశీలించే ముందు, మనం కొన్ని ఉదాహరణలను పరిశీలించాలి.

కాంకెటనేషన్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా అర్రే ఫార్మేషన్‌ను తనిఖీ చేయండిపిన్

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

వివరణ: మేము మూలకాలను రివర్స్ క్రమంలో అమర్చవచ్చు. ఆ విధంగా 15 ఉన్న చివరి శ్రేణి ముందు వస్తుంది. అదేవిధంగా, మొదటి మూలకం వెనుకకు వెళ్తుంది. ఈ విధంగా మనం ఇచ్చిన శ్రేణిని ఏర్పరచవచ్చు.

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

వివరణ: మేము మొదట చివరి మూలకాన్ని సంయోగం చేస్తే, మధ్య శ్రేణి, చివరికి మొదటి శ్రేణి. ఈ విధంగా మనం అవసరమైన క్రమాన్ని పొందవచ్చు.

కాంకాటనేషన్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా చెక్ అర్రే నిర్మాణం కోసం విధానం  

సమస్య కాంకటనేషన్ ద్వారా అర్రే ఫార్మేషన్‌ను తనిఖీ చేయండి లీట్‌కోడ్ సొల్యూషన్ శ్రేణుల శ్రేణి నుండి అవసరమైన క్రమాన్ని పొందగలదా అని తనిఖీ చేయమని కోరింది. సమస్య పునరావృతమయ్యేలా ఉంది, ఇక్కడ మేము అన్ని అవకాశాలను తనిఖీ చేయాలి. పునరావృత పద్ధతిలో, మేము మొదట శ్రేణిని ఎంచుకునేందుకు ప్రయత్నిస్తాము, ఆపై ప్రస్తుత శ్రేణి అనుకూలంగా ఉందో లేదో తనిఖీ చేసి, ఆ క్రమాన్ని ఖాళీ చేసే వరకు అదే ఆపరేషన్ చేయండి. కానీ ఇక్కడ మనకు ఉన్న ప్రయోజనం ప్రత్యేకమైన అంశాలు. కాబట్టి, శ్రేణుల మొదటి మూలకంతో మొదటి మూలకాన్ని మాత్రమే తనిఖీ చేస్తాము. దీన్ని తనిఖీ చేయడం కూడా మనం ఎంచుకున్న శ్రేణితో ముందుకు సాగగలదని నిర్ధారిస్తుంది.

ఇది కూడ చూడు
స్టూడెంట్ అటెండెన్స్ రికార్డ్ I లీట్‌కోడ్ సొల్యూషన్

శ్రేణిని ఎంచుకున్న తరువాత, మేము దానిలోని అన్ని మూలకాలను ప్రయాణించి, శ్రేణిలో అన్ని మూలకాలు ఉన్నాయా అని తనిఖీ చేస్తాము. అలసట తరువాత, అదే ప్రక్రియ పునరావృతమవుతుంది. శ్రేణి యొక్క మూలకం మరియు క్రమం లో కొంత అసమతుల్యత ఉంటే, మేము తప్పుడు తిరిగి ఇస్తాము. చివరికి, మనకు అసమతుల్యత కనిపించనప్పుడు మేము నిజం అవుతాము.

కాంకాటనేషన్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా చెక్ అర్రే నిర్మాణం కోసం కోడ్  

సి ++ కోడ్

#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

జావా కోడ్

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 అనేది ఇచ్చిన క్రమంలోని మొత్తం మూలకాల సంఖ్య. వాడకం వల్ల సమయ సంక్లిష్టత సరళంగా తగ్గించబడింది హాష్ మ్యాప్.

స్థల సంక్లిష్టత

O (M), ఇక్కడ M అనేది శ్రేణుల శ్రేణిలోని శ్రేణుల సంఖ్య.

1