Направете две низи еднакви со обратно решение на под-низите Leetcode решение


Ниво на тешкотија Лесно
Често прашувано во Facebook
Низа

Проблемот Направи две низи еднакви со свртување на под-низите Leetcode Solution ни овозможува две низи. Едната од нив е целна низа, а другата е влезна низа. Користејќи ја влезната низа, треба да ја направиме целната низа. Можеме да свртиме која било од под-низата во влезната низа. Но, не можеме да ги менуваме елементите на влезната низа. Не треба да најдеме начин како да ја извршиме манипулацијата. Врати се ако е можно друго, неточно. Значи, како и обично, пред да се нурнеме длабоко во решението, да разгледаме неколку примери.

Направете две низи еднакви со обратно решение на под-низите Leetcode решение

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

Објаснување: Можеме да ја смениме првата под-низа од индекс 0 до 2, а потоа да ја смениме под-низата од 1 до 2. На крајот, ќе го смениме индексот 2 до 3. И на овој начин, можеме да ја направиме целната низа . Може подобро да се разбере со поглед на горната слика.

Пристап за да се направат еднакви две низи со свртување на решенијата за кодирани линии со под-низи

Проблемот лесно може да се реши со користење на методот на броење. Методот на броење е некои од стандардните алгоритми. Се користи во вид на броење, како и во многу други прашања. така, тука го чуваме бројот на елементи од целната низа. Потоа ги минуваме елементите на влезната низа. Кога ќе се сретнеме со кој било елемент, го намалуваме неговиот број од фреквенцијата или низата броење. Ако некако за време на оваа операција, кој било индекс има негативна вредност, ние ја враќаме лажна.

Негативно сметање во низата фреквенција покажува дека влезната низа има поголемо броење за елемент. Но, како со ова се решава проблемот? Одговорот е едноставен откако ќе ја знаете набудувањето. Откако ќе се обидете да извршите неколку пресврти на под-низите. Можете лесно да сфатите дека можете да поставите кој било елемент од влезната низа на кое било место каде што сакате. Значи, користејќи го ова правило, треба да провериме дали елементите во целната низа се исти со оние на влезната низа.

Код за да се направат две низи еднакви со свртување на решенијата на Leetcode за под-низите

C ++ код

#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

Java код

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

Анализа на сложеност

Временска комплексност

НА), бидејќи ги пресекуваме сите елементи на низите.

Комплексноста на просторот

О (1), затоа што користевме низа со постојана големина на фреквенција или броење.