Alt massivləri Leccode həllini geri çevirərək iki massivi bərabərləşdirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Facebook
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 71

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Məsələ, alt massivləri geri çevirərək iki massivi bərabərləşdirin Leetcode Solution bizə ikisini təmin edir seriallar. Onlardan biri hədəf massivi, digəri isə giriş massividir. Giriş massivindən istifadə edərək hədəf massivi yaratmalıyıq. Giriş massivindəki alt dizinin hər hansı birini tərsinə çevirə bilərik. Ancaq giriş massivinin elementlərini dəyişdirə bilmərik. Manipulyasiyanın necə aparılacağına dair bir yol tapmağa ehtiyacımız yoxdur. Mümkünsə doğru qayıdın başqa yanlış. Beləliklə, hər zamankı kimi həllin dərinliyinə dalmadan əvvəl bir neçə nümunəyə nəzər salaq.

Alt massivləri Leccode həllini geri çevirərək iki massivi bərabərləşdirinPin

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

İzahat: İlk alt massivi indeks 0-dan 2-yə çevirə bilərik, sonra alt sıranı 1-dən 2-ə çevirə bilərik. Sonda indeks 2-dən 3-ə tərs oluruq. Və bu şəkildə hədəf massivi düzəldə bilərik. . Yuxarıdakı şəkilə nəzər salmaqla daha yaxşı başa düşülə bilər.

Alt serialları Leetcode Solution-un tərsinə çevirərək iki massivi bərabərləşdirmək üçün yanaşma

Problem sayma üsulu ilə asanlıqla həll edilə bilər. Sayma metodu standart alqoritmlərdən bir neçəsidir. Bu say sayında və digər bir çox suallarda istifadə olunur. Beləliklə, burada hədəf massivindəki elementlərin sayını saxlayırıq. Sonra giriş massivinin elementlərini keçirik. Hər hansı bir elementlə qarşılaşdığımızda, sayını tezlikdən və ya sayma massivindən azaldırıq. Bu əməliyyat zamanı bir şəkildə hər hansı bir indeks mənfi dəyəri saxlayırsa, yalan olaraq qaytarırıq.

Tezlik cərgəsindəki mənfi bir say giriş elementinin bir element üçün daha böyük bir sayına sahib olduğunu göstərir. Bəs bunu etmək problemi necə həll edir? Müşahidəni bildikdən sonra cavab sadədir. Bir dəfə alt serialların əksini tapmağa çalışdıqda. Giriş massivinin istənilən elementini istədiyiniz yerdə istədiyiniz yerdə yerləşdirə biləcəyinizi asanlıqla anlaya bilərsiniz. Beləliklə, bu qaydanı istifadə edərək hədəf massivindəki elementlərin giriş sıra ilə eyni olub olmadığını yoxlamalıyıq.

Yarımkod Leetcod Solution-un tərsinə çevrilərək iki massivi bərabərləşdirmə kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki biz massivlərin bütün elementlərini keçirik.

Kosmik Mürəkkəblik

O (1), çünki sabit ölçülü bir tezlik və ya sayma sıra istifadə etdik.

Crack Sistemi Dizayn Müsahibələri
Translate »
1