Κάντε ίσες δύο συστοιχίες με την αντιστροφή της λύσης Leetcode Sub-array  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Facebook
αλγόριθμοι Παράταξη κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions

Το πρόβλημα Κάντε Ίσο δύο συστοιχίες αντιστρέφοντας τις δευτερεύουσες συστοιχίες Το Leetcode Solution μας παρέχει δύο συστοιχίες. Ένας από αυτούς είναι ένας πίνακας στόχων και ο άλλος ένας πίνακας εισόδου. Χρησιμοποιώντας τον πίνακα εισαγωγής, πρέπει να φτιάξουμε τον πίνακα στόχου. Μπορούμε να αντιστρέψουμε οποιαδήποτε από τις δευτερεύουσες συστοιχίες του πίνακα εισαγωγής. Αλλά δεν μπορούμε να αλλάξουμε τα στοιχεία του πίνακα εισαγωγής. Δεν χρειάζεται να βρούμε έναν τρόπο για τον τρόπο εκτέλεσης της χειραγώγησης. Επιστρέψτε αληθές αν είναι δυνατόν αλλιώς ψευδές. Έτσι, όπως συνήθως πριν βυθιστεί κανείς στη λύση, ας ρίξουμε μια ματιά σε μερικά παραδείγματα.

Κάντε ίσες δύο συστοιχίες με την αντιστροφή της λύσης Leetcode Sub-arrayΚαρφώστε

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

Επεξήγηση: Μπορούμε να αντιστρέψουμε τον πρώτο δευτερεύοντα πίνακα από το ευρετήριο 0 έως 2 και μετά να αντιστρέψουμε τον δευτερεύοντα πίνακα από το 1 στο 2. Στο τέλος, αντιστρέφουμε το ευρετήριο 2 έως 3. Και με αυτόν τον τρόπο, μπορούμε να φτιάξουμε τον πίνακα στόχου . Μπορεί να γίνει καλύτερα κατανοητό ρίχνοντας μια ματιά στην παραπάνω εικόνα.

Προσέγγιση για τη δημιουργία ισοδύναμων δύο συστοιχιών με την αντιστροφή της λύσης Leetcode Sub-array  

Το πρόβλημα μπορεί να λυθεί εύκολα χρησιμοποιώντας τη μέθοδο μέτρησης. Η μέθοδος μέτρησης είναι μερικοί από τους τυπικούς αλγόριθμους. Χρησιμοποιείται σε είδος καταμέτρησης καθώς και σε πολλές άλλες ερωτήσεις. οπότε εδώ κρατάμε τον αριθμό των στοιχείων από τον πίνακα στόχου. Στη συνέχεια, διασχίζουμε τα στοιχεία του πίνακα εισαγωγής. Όταν συναντάμε οποιοδήποτε στοιχείο, μειώνουμε τον αριθμό του από τον πίνακα συχνότητας ή μέτρησης. Εάν κατά κάποιο τρόπο κατά τη διάρκεια αυτής της λειτουργίας, οποιοδήποτε ευρετήριο διατηρεί αρνητική τιμή, επιστρέφουμε ψευδείς.

Βλέπε επίσης
Μεγαλύτερος Subarray με μέτρηση 1s Ένα περισσότερο από Count 0s

Ένας αρνητικός αριθμός στον πίνακα συχνοτήτων δείχνει ότι ο πίνακας εισόδου έχει μεγαλύτερο αριθμό για ένα στοιχείο. Αλλά πώς επιλύει αυτό το πρόβλημα; Η απάντηση είναι απλή μόλις γνωρίζετε την παρατήρηση. Μόλις προσπαθήσετε να εκτελέσετε κάποιες αντιστροφές των υπο-συστοιχιών. Μπορείτε εύκολα να καταλάβετε ότι μπορείτε να τοποθετήσετε οποιοδήποτε στοιχείο του πίνακα εισαγωγής σε οποιοδήποτε μέρος όπου θέλετε. Έτσι, χρησιμοποιώντας αυτόν τον κανόνα πρέπει να ελέγξουμε εάν τα στοιχεία στο πίνακα στόχων είναι τα ίδια με αυτά του πίνακα εισαγωγής.

Κωδικός για να κάνετε ίσες δύο συστοιχίες με την αντιστροφή της λύσης Leetcode Sub-array  

Κωδικός 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), γιατί χρησιμοποιήσαμε έναν πίνακα συχνοτήτων ή μέτρησης σταθερού μεγέθους.

1