מאַכן צוויי ערייז גלייַך דורך ריווערסינג סאַב-ערייז Leetcode סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין facebook
מענגע

די פּראָבלעם מאַכן צוויי אַררייַס גלייַך דורך ריווערסינג סאַב-ערייז, Leetcode סאַלושאַן גיט אונדז צוויי ערייז. איינער פון זיי איז אַ ציל מענגע און די אנדערע איז אַ ינפּוט מענגע. ניצן די ינפּוט מענגע מיר דאַרפֿן צו מאַכן די ציל מענגע. מיר קענען פאַרקערט קיין פון די סאַב-מענגע אין די ינפּוט מענגע. אָבער מיר קענען נישט טוישן די יסודות פון די ינפּוט מענגע. מיר טאָן ניט דאַרפֿן צו געפֿינען אַ וועג צו פירן מאַניפּיאַליישאַן. צוריקקומען אמת אויב מעגלעך אַנדערש פאַלש. אַזוי ווי געוויינטלעך איידער דייווינג טיף אין דער לייזונג, לאָזן אונדז נעמען עטלעכע ביישפילן.

מאַכן צוויי ערייז גלייַך דורך ריווערסינג סאַב-ערייז Leetcode סאַלושאַן

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

דערקלערונג: מיר קענען פאַרקערט די ערשטער סאַב-מענגע פֿון אינדעקס 0 צו 2, און מיר פאַרקערט די סאַב-מענגע פון ​​1 צו 2. אין די סוף, מיר פאַרקערט אינדעקס 2 צו 3. און אין דעם וועג, מיר קענען מאַכן די ציל מענגע. . עס קען זיין בעסער פארשטאנען דורך אַ קוק אין די אויבן בילד.

צוגאַנג צו מאַכן צוויי ערייז גלייַך דורך ריווערסינג סאַב-ערייז Leetcode סאַלושאַן

דער פּראָבלעם קענען זיין לייכט סאַלווד מיט קאַונטינג אופֿן. די קאַונטינג אופֿן איז עטלעכע פון ​​די נאָרמאַל אַלגערידאַמז. עס איז געניצט אין ציילן סאָרט ווי געזונט ווי אין פילע אנדערע פֿראגן. אַזוי דאָ מיר האַלטן ציילן פון עלעמענטן פֿון דער ציל מענגע. דערנאָך מיר אַריבער די יסודות פון די ינפּוט מענגע. ווען מיר טרעפן אַן עלעמענט, מיר פאַרקלענערן די ציילן פון די אָפטקייַט אָדער ציילן מענגע. אויב עפעס בעשאַס די אָפּעראַציע, קיין אינדעקס האט אַ נעגאַטיוו ווערט מיר קערט פאַלש.

א נעגאַטיוו ציילן אין די אָפטקייַט מענגע ווייזט אַז די ינפּוט מענגע האט אַ גרעסערע ציילן פֿאַר אַן עלעמענט. אָבער ווי אַזוי טאָן דאָס סאָלווע די פּראָבלעם? דער ענטפער איז פּשוט אַמאָל איר וויסן די אָבסערוואַציע. אַמאָל איר פּרובירן צו דורכפירן ריווערסאַלז פון סאַב-ערייז. איר קענט לייכט אויס אַז איר קענען שטעלן קיין עלעמענט פון די ינפּוט מענגע אין קיין אָרט וואוהין איר ווילט. אויב איר נוצן דעם הערשן, מיר דאַרפֿן צו קאָנטראָלירן אויב די עלעמענטן אין דער ציל מענגע זענען די זעלבע ווי די פון די ינפּוט מענגע.

קאָד פֿאַר מאַכן צוויי ערייז גלייַך דורך ריווערסינג סאַב-ערייז 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), ווייַל מיר אַריבער אַלע די יסודות פון די ערייז.

ספעיס קאַמפּלעקסיטי

אָ (1), ווייַל מיר געוויינט אַ קעסיידערדיק סייזד אָפטקייַט אָדער ציילן מענגע.