કનેકેટેશન લીટકોડ સોલ્યુશન દ્વારા એરે ફોર્મેશન તપાસો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ઉબેર
અરે કોડસિગ્નલ હેશમેપ સૉર્ટ

કન્કેટેશન લીટકોડ સોલ્યુશન દ્વારા એરેની રચના તપાસો સમસ્યા અમને એરેની એરે પ્રદાન કરી. તેની સાથે આપણને સિક્વન્સ પણ આપવામાં આવે છે. ત્યારબાદ અમને કહેવાનું કહેવામાં આવે છે કે જો આપણે આપેલ ક્રમનો ઉપયોગ કરીને કોઈક રીતે બનાવી શકીએ કે નહીં એરે એરે. આપણને જોઈએ તે રીતે અમે એરે ગોઠવી શકીએ છીએ. પરંતુ આપણે એરેની અંદરના તત્વોને ફરીથી ગોઠવી શકતા નથી. અમને એ પણ કહેવામાં આવે છે કે એરેની એરેમાં પૂર્ણાંકો અનન્ય છે. તેથી સોલ્યુશન પર એક નજર કરતાં પહેલાં, આપણે થોડા ઉદાહરણો પર એક નજર નાખવી જોઈએ.

કનેકેટેશન લીટકોડ સોલ્યુશન દ્વારા એરે ફોર્મેશન તપાસો

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

સમજૂતી: અમે તત્વોને વિપરીત ક્રમમાં ગોઠવી શકીએ છીએ. આમ છેલ્લું એરે જે 15 ની છે તે સામે આવશે. એ જ રીતે, પ્રથમ તત્વ પાછળ જશે. આ રીતે આપણે આપેલ એરે બનાવી શકીએ.

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

સમજૂતી: જો આપણે છેલ્લું તત્વ પહેલા કatenનટેટ કરીએ, તો પછી મધ્યમ એરે, અને અંતે પ્રથમ એરે. આ રીતે આપણે જરૂરી ક્રમ મેળવી શકીએ છીએ.

કનેકેટેશન લીટકોડ સોલ્યુશન દ્વારા એરે ફોર્મેશન માટે અભિગમ

કન્કેટેનેશન લીટકોડ સોલ્યુશન દ્વારા એરેની રચના તપાસો સમસ્યા અમને એરેની એરેમાંથી જરૂરી ક્રમ મેળવી શકે છે કે કેમ તે તપાસવા માટે પૂછ્યું. સમસ્યા એક પુનરાવર્તિત જેવી લાગે છે, જ્યાં આપણે બધી શક્યતાઓ તપાસવાની જરૂર છે. રિકરિવ રીતે, આપણે પહેલા એરે પસંદ કરવાનો પ્રયાસ કરીએ છીએ અને પછી તપાસો કે જો વર્તમાન એરે યોગ્ય છે કે નહીં ત્યાં સુધી તે જ ઓપરેશન કરીએ ત્યાં સુધી આપણે સિક્વન્સ એક્ઝોસ્ટ ન કરીએ ત્યાં સુધી. પરંતુ અમારે અહીં જે ફાયદો છે તે અનન્ય તત્વો છે. તેથી, આપણે ફક્ત એરેના પ્રથમ તત્વ સાથે ફક્ત પ્રથમ તત્વ તપાસીએ છીએ. આ પણ તપાસવાથી ખાતરી કરવામાં આવશે કે અમે ચૂંટેલા એરે સાથે આગળ વધી શકીશું.

એરે ચૂંટ્યા પછી, અમે એમાં બધા તત્વો વટાવીએ છીએ એ તપાસ્યા સુધી કે એરેમાં ક્રમના બધા તત્વો છે કે જ્યાં સુધી આપણે તેને સમાપ્ત નહીં કરીએ. થાક પછી, તે જ પ્રક્રિયા પુનરાવર્તિત થાય છે. જો એરે અને સિક્વન્સના તત્વમાં થોડો મેળ ખાતો નથી, તો આપણે ખોટા પાછા વળવું. અંતે, જ્યારે અમને કોઈ મેળ ખાતું નથી, ત્યારે આપણે સાચું પાછા ફરો.

કનેકેટેશન લીટકોડ સોલ્યુશન દ્વારા ચેક એરે રચના માટેનો કોડ

સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જ્યાં એન આપેલ ક્રમના તત્વોની કુલ સંખ્યા છે. સમય જટિલતાના ઉપયોગને લીધે રેખીય પર ઘટાડવામાં આવી છે હેશમેપ.

જગ્યાની જટિલતા

ઓ (એમ), જ્યાં એમ એરેની એરેમાં એરેની સંખ્યા છે.