İşləmə uzunluğu kodlanmış siyahı leetkod həllini açın

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

Problemin işlənmə uzunluğunun şifrələnmiş siyahısı Leetcode həllinin dekompressiyası sizə verildiyini bildirir array və ya ardıcıllığı olan vektor. Ardıcıllığın müəyyən bir təqdimatı var. Giriş ardıcıllığı başqa bir ardıcıllıqdan meydana gəlir. Bunu orijinal ardıcıllıqla başqa bir ardıcıllıqla adlandıracağıq. Buna görə giriş ardıcıllığı yaradılmışdır. Orijinal ardıcıllığı tapmağımız istənir. Ardıcıllıqdakı hər bir tək (ith) indeks, aşağıdakı (i + 1-ci) indeksin orijinal ardıcıllıqla neçə dəfə təkrarlandığını göstərir. Beləliklə, həmişə olduğu kimi həll yoluna dalmadan əvvəl bir neçə nümunəyə nəzər salaq.

İşləmə uzunluğu kodlanmış siyahı leetkod həllini açınPin

nums = [1,2,3,4]
[2,4,4,4]

İzahat: Çıxışın düzgün olub olmadığını yoxlayaq? 2 orijinal ifadəsində 1 dəfə təkrarlanır. Beləliklə, giriş ardıcıllığında 1, 2 olmalıdır. Bundan sonra 4, 3 dəfə təkrarlanır, bu da giriş ardıcıllığında göstərilir, belə ki, bu, çıxışın doğru olduğunu sübut edir.

nums = [1,1,2,3]
[1,3,3]

İzahat: Çıxışı doğrulayırıqsa yenə. 1-in tək nüsxəsi var və 3-ü iki dəfə təkrarlanır. Bir daha çıxış doğrudur.

Dekompressiya Çalışma Uzunluğu Kodlanmış Siyahı Leetcode Həlli üçün yanaşma

Problemin işləmə uzunluğunun şifrələnmiş siyahısı Leetcode həllinin açılması standartdır. Müxtəlif şirkətlər tərəfindən aparılan bir neçə kodlaşdırma turunda tez-tez soruşulur. Orijinal ardıcıllığı saxlamaq üçün yeni bir sıra yaratmaq lazım olduğundan yanaşma çox sadədir. Sadəcə bir sıra və ya bir vektordan istifadə edirik və arxada elementlər əlavə etməyə davam edirik.

Hər təkrarlamadan sonra 2 vahid atlayan bir for döngəsini işə sala bilərik. Bu, yalnız (tezlik, dəyər) cütləri ilə məşğul olduğumuzu təsdiqləyir. İndi yenidən iç içə döngə ilə, ith indeksindəki elementi vektora əlavə edirik. Verilən giriş ardıcıllığındakı i + 1-ci indeksdəki elementə uyğun olaraq iç içə döngə işlədirik.

İşləmə uzunluğu şifrələnmiş siyahı lekodu həllinin dekompressiyası kodu

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

vector<int> decompressRLElist(vector<int>& nums) {
    vector<int> tmp;
    for(int i=0;i<nums.size();i+=2){
        for(int j=0;j<nums[i];j++)
            tmp.push_back(nums[i+1]);
    }
    return tmp;
}

int main(){
    vector<int> input = {1,2,3,4};
    vector<int> output = decompressRLElist(input);
    for(auto x: output)cout<<x<<" ";
}
2 4 4 4

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int[] decompressRLElist(int[] nums) {
        int size = 0, k = 0;
        for(int i=0;i<nums.length;i+=2)
            size += nums[i];
        int[] tmp = new int[size];
        for(int i=0;i<nums.length;i+=2){
            for(int j=0;j<nums[i];j++)
                tmp[k++] = nums[i+1];
        }
        return tmp;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] input = {1,2,3,4};
      int[] output = decompressRLElist(input);
      for(Integer x: output)System.out.print(x+" ");
  }
}
2 4 4 4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N çıxışın uzunluğudur. Burada zamanın mürəkkəbliyi girişdən asılı deyil. Giriş əvəzinə, zamanın mürəkkəbliyi əldə edilən nəticəyə və ya nəticəyə bağlıdır.

Kosmik Mürəkkəblik

O (N), burada N çıxışın uzunluğudur. Çıxışı geri qaytardığımız üçün saxladığımız üçün. Məkan da onun tərəfindən işğal olunur.

Şərh yaz

Translate »
1