Декомпресујте решење са кодираним списком дужине покретања


Ниво тешкоће Лако
Често питани у амазонка јабука гоогле
Ред

Проблем Децомпресс Реакција кодираног пописа дужине трајања Леетцоде Солутион наводи да сте добили поредак или вектор који садржи низ. Низ има неку специфичну представу. Улазна секвенца се формира из друге секвенце. Назваћемо то другом секвенцом као оригиналном секвенцом. Према којем је креиран улазни низ. Тражимо да пронађемо оригинални низ. Сваки непарни (и-ти) индекс у секвенци представља број понављања следећег (и + 1-ог) индекса у оригиналној секвенци. Као и увек пре него што уђемо у решење, погледајмо неколико примера.

Декомпресујте решење са кодираним списком дужине покретања

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

Објашњење: Провјеримо да ли је излаз тачан? 2 се понавља 1 пут у оригиналној изјави. Дакле, у улазној секвенци требало би да буде 1, 2. После тога, 4 се понавља 3 пута, што је такође приказано у улазној секвенци Дакле, ово доказује да је излаз тачан.

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

Објашњење: Опет ако верификујемо излаз. 1 има једну копију, а 3 се понавља два пута. Још једном је исход тачан.

Приступ за декомпресовање решења са кодираним списком дужине покретања

Проблем Децомпресс Рут-Ленгтх кодирана листа Леетцоде решење је стандардни. Често се пита у неколико кругова кодирања које су спроводиле разне компаније. Приступ је врло једноставан јер морамо створити нови низ за чување оригиналне секвенце. Једноставно користимо низ или вектор и настављамо да додајемо елементе позади.

Можемо покренути фор петљу која прескаче 2 јединице након сваке итерације. Ово потврђује да имамо посла само са (фреквенцијама, вредностима) паровима. Сада опет са угнежђеном петљом фор, додајемо елемент у и-ом индексу у вектор. Изводимо угнежђену петљу фор према елементу на и + 1-ом индексу у датој улазној секвенци.

Код за решење за кодирану листу кодиране листе дужине покретања

Ц ++ код

#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

Јава код

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

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

Сложеност времена

НА), где је Н дужина излаза. Овде временска сложеност не зависи од улазних података. Уместо уноса, временска сложеност зависи од резултата или добијеног резултата.

Сложеност простора

НА), где је Н дужина излаза. Будући да излаз чувамо јер га враћамо. Простор такође заузима њиме.