উপ-অ্যারে লেটকোড সমাধানটি বিপরীত করে দুটি অ্যারে সমান করুন Make


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ফেসবুক
বিন্যাস

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

উপ-অ্যারে লেটকোড সমাধানটি বিপরীত করে দুটি অ্যারে সমান করুন Make

target = [1,2,3,4], arr = [2,4,1,3]
true

ব্যাখ্যা: আমরা সূচক 0 থেকে 2 থেকে প্রথম উপ-অ্যারেটি বিপরীত করতে পারি, তারপরে আমরা 1 থেকে 2 পর্যন্ত উপ-অ্যারেটি বিপরীত করব the । উপরের চিত্রটি দেখে এটি আরও ভালভাবে বোঝা যায়।

উপ-অ্যারে লেটকোড সমাধানটি বিপরীত করে দুটি অ্যারে সমান করে তুলুন

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

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

উপ-অ্যারে লেটকোড সলিউশনকে বিপরীত করে দু'টি অ্যারে সমান তৈরি করার কোড

সি ++ কোড

#include <bits/stdc++.h>
using namespace std;

bool canBeEqual(vector<int>& target, vector<int>& arr) {
    vector<int> cnt(1001, 0);
    for(int i=0;i<target.size();i++)
        ++cnt[target[i]];
    for (int i=0;i<arr.size();i++) {
        if (--cnt[arr[i]] < 0) {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> target = {1, 2, 3, 4};
    vector<int> arr = {2, 3, 1, 4};
    cout<<(canBeEqual(target, arr) ? "true" : "false");
}
true

জাভা কোড

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canBeEqual(int[] target, int[] arr) {
        int[] cnt = new int[1001];
        for(int i=0;i<target.length;i++)
            ++cnt[target[i]];
        for (int i=0;i<arr.length;i++) {
            if (--cnt[arr[i]] < 0) {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 2, 3, 4};
      int[] arr = {2, 3, 1, 4};
      System.out.print(canBeEqual(target, arr) ? "true" : "false");
  }
}
true

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

সময় জটিলতা

চালু), কারণ আমরা অ্যারের সমস্ত উপাদানগুলিকে অতিক্রম করি।

স্পেস জটিলতা ity

ও (1), কারণ আমরা একটি ধ্রুব আকারের ফ্রিকোয়েন্সি বা গণনা অ্যারে ব্যবহার করি।