কনেকেটনেশন লেটকোড সমাধানের মাধ্যমে অ্যারে গঠন পরীক্ষা করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় উবার
বিন্যাস কোডসিগনাল হ্যাশ মানচিত্র বাছাই করা

কনটেনটেশন লেটকোড সলিউশন এর মাধ্যমে অ্যারে গঠনটি চেক করুন সমস্যাটি অ্যারেগুলির একটি অ্যারে সরবরাহ করেছিল। সেই সাথে আমাদের একটি সিকোয়েন্সও দেওয়া হয়। তারপরে আমাদের জানানো হয় যে আমরা কোনওভাবে প্রদত্ত ক্রমটি ব্যবহার করে তৈরি করতে পারি কিনা বিন্যাস অ্যারে। আমরা যে কোনও আদেশ চাইলে অ্যারেগুলি সাজিয়ে রাখতে পারি। তবে আমরা অ্যারের ভিতরে থাকা উপাদানগুলিকে পুনর্বিন্যাস করতে পারি না। আমাদের আরও বলা হয় যে অ্যারেগুলির অ্যারেতে পূর্ণসংখ্যাগুলি অনন্য। সুতরাং সমাধানটি একবার দেখার আগে আমাদের কয়েকটি উদাহরণে একবার নজর দেওয়া উচিত।

কনেকেটনেশন লেটকোড সমাধানের মাধ্যমে অ্যারে গঠন পরীক্ষা করুন

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

ব্যাখ্যা: আমরা উপাদানগুলি বিপরীত ক্রমে সাজিয়ে নিতে পারি। সুতরাং 15 এর শেষ অ্যারেটি সামনে আসবে। একইভাবে, প্রথম উপাদানটি পিছনে যাবে। এইভাবে আমরা প্রদত্ত অ্যারে গঠন করতে পারি।

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

ব্যাখ্যা: আমরা যদি সর্বশেষ উপাদানটিকে প্রথমে স্বাক্ষর করি তবে তারপরে মাঝের অ্যারে এবং শেষে প্রথম অ্যারে। এইভাবে আমরা প্রয়োজনীয় ক্রমটি পেতে পারি।

কনটেনটেশন লেটকোড সমাধানের মাধ্যমে অ্যারে গঠনের জন্য অ্যাপ্রোচ

কনটেনটেশন লেটকোড সলিউশন এর মাধ্যমে অ্যারে গঠনটি চেক করুন সমস্যাটি অ্যারের অ্যারে থেকে প্রয়োজনীয় ক্রমটি পেতে পারি কিনা তা আমাদের জানতে চেয়েছিল। সমস্যাটি একটি পুনরাবৃত্তি বলে মনে হচ্ছে, যেখানে আমাদের সমস্ত সম্ভাবনা পরীক্ষা করা দরকার। পুনরাবৃত্তিমূলক পদ্ধতিতে, আমরা প্রথমে একটি অ্যারে বাছাই করার চেষ্টা করি এবং তারপরে বর্তমান অ্যারেটি উপযুক্ত কিনা তা পরীক্ষা করে আমরা ক্রমটি শেষ না করা পর্যন্ত একই অপারেশনটি সম্পাদন করি। তবে আমাদের এখানে যে সুবিধাটি রয়েছে তা অনন্য উপাদান। সুতরাং, আমরা কেবল অ্যারের প্রথম উপাদানটির সাথে কেবল প্রথম উপাদানটি পরীক্ষা করি। এমনকি এটি যাচাই করাও নিশ্চিত করে তোলে যে আমরা বাছাই করা অ্যারে দিয়ে এগিয়ে যেতে পারি।

একটি অ্যারে বাছাইয়ের পরে, আমরা অ্যারেটিকে শেষ না করা অবধি ক্রমের সমস্ত উপাদান রয়েছে কিনা তা পরীক্ষা করে এটিতে থাকা সমস্ত উপাদানকে আমরা অতিক্রম করি। ক্লান্তির পরে, একই প্রক্রিয়া পুনরাবৃত্তি হয়। অ্যারের উপাদান এবং ক্রমগুলির মধ্যে কিছু মিল নেই তবে আমরা মিথ্যা প্রত্যাবর্তন করব। শেষ অবধি, যখন আমরা কোনও অমিল খুঁজে পাই না তখন আমরা সত্যটিতে ফিরে আসি।

কনটেনটেশন লেটকোড সমাধানের মাধ্যমে অ্যারে গঠনের জন্য কোড

সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), যেখানে এন হল প্রদত্ত ক্রমের মোট উপাদানগুলির সংখ্যা। সময় জটিলতা রৈখিক হ্রাস হয়েছে ব্যবহারের কারণে হ্যাশ মানচিত্র.

স্থান জটিলতা

ও (এম), যেখানে এম অ্যারেগুলির অ্যারেগুলির সংখ্যা।