සංයුක්ත ලීට්කෝඩ් විසඳුම හරහා අරා සැකැස්ම පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Uber
අරා කෝඩ් සිග්නල් හැෂ්මැප් වර්ග

කොන්ක්‍රීටේෂන් ලීට්කෝඩ් විසඳුම හරහා අරාව සැකසීම පරීක්ෂා කිරීමේ ගැටළුව අපට අරා සමූහයක් ලබා දී ඇත. ඒ සමඟම අපට අනුක්‍රමයක් ද ලබා දී ඇත. අපට ලබා දී ඇති අනුක්‍රමය කෙසේ හෝ ගොඩනගා ගත හැකිදැයි සොයා බැලීමට අපට කියනු ලැබේ අරාව අරා වල. අපට අවශ්‍ය ඕනෑම අනුපිළිවෙලකට අරා සකස් කළ හැකිය. නමුත් අපට අරාව තුළ ඇති මූලද්‍රව්‍ය නැවත සකස් කළ නොහැක. අරා සමූහයේ පූර්ණ සංඛ්‍යා අද්විතීය බව අපට කියනු ලැබේ. එබැවින් විසඳුම දෙස බැලීමට පෙර අපි උදාහරණ කිහිපයක් දෙස බැලිය යුතුය.

සංයුක්ත ලීට්කෝඩ් විසඳුම හරහා අරා සැකැස්ම පරීක්ෂා කරන්න

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මෙහි N යනු දී ඇති අනුක්‍රමයේ මුළු මූලද්‍රව්‍ය ගණන වේ. භාවිතය නිසා කාල සංකීර්ණතාව රේඛීය දක්වා අඩු කර ඇත හැෂ්මැප්.

අවකාශයේ සංකීර්ණතාව

ඕ (එම්), මෙහි M යනු අරා අරා වල අරා ගණන වේ.