Розпакувати розшифрований зашифрований список штрих-кодів


Рівень складності Легко
Часто запитують у Амазонка Apple Google
масив

Проблема Декомпресія розширеного кодованого списку Leetcode Solution говорить про те, що ви отримали масив або вектор, що містить послідовність. Послідовність має деяке конкретне представлення. Вхідна послідовність формується з іншої послідовності. Ми будемо називати цю іншу послідовність оригінальною. Відповідно до якого була створена вхідна послідовність. Нас просять знайти оригінальну послідовність. Кожен непарний (i-й) індекс у послідовності представляє кількість повторень наступного (i + 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 повторюється двічі. Ще раз результат правильний.

Підхід до розшифровки розширеного кодованого списку рішення Leetcode Solution

Проблема Декомпресія кодованого списку кодованого списку "Рішення" є стандартною. І часто запитується в декількох турах кодування, проведених різними компаніями. Підхід дуже простий, оскільки нам потрібно створити новий масив для зберігання вихідної послідовності. Ми просто використовуємо або масив, або вектор, і продовжуємо додавати елементи ззаду.

Ми можемо запустити цикл for, який стрибає на 2 одиниці після кожної ітерації. Це підтверджує, що ми маємо справу лише з (частотою, значенням) парами. Тепер знову з вкладеним циклом for ми додаємо елемент до i-го індексу до вектора. Ми запускаємо вкладений цикл for відповідно до елемента з i + 1-м індексом у заданій вхідній послідовності.

Код для розшифрованого розшифрованого кодованого списку рішення Leetcode Solution

Код С ++

#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

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

Аналіз складності

Складність часу

O (N), де N - довжина вихідного сигналу. Тут складність часу не залежить від вхідних даних. Замість вхідних даних складність часу залежить від результату або отриманого результату.

Складність простору

O (N), де N - довжина вихідного сигналу. Оскільки ми зберігаємо вихідні дані, тому що повертаємо їх. Простір також зайнятий нею.