Run-Length 인코딩 된 목록 Leetcode 솔루션의 압축 해제-TutorialCup

Run-Length Encoded List Leetcode Solution의 압축 해제 문제는 정렬 또는 시퀀스를 포함하는 벡터. 시퀀스에는 특정 표현이 있습니다. 입력 시퀀스는 다른 시퀀스에서 구성됩니다. 다른 시퀀스를 원래 시퀀스라고 부를 것입니다. 입력 시퀀스가 생성 된 기준. 원래 시퀀스를 찾아야합니다. 시퀀스의 각 홀수 (ith) 인덱스는 원래 시퀀스에서 다음 (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은 두 번 반복됩니다. 다시 한 번 출력이 정확합니다.

차례

Run-Length Encoded List Leetcode 솔루션의 압축 해제 접근 방식

Run-Length Encoded List Leetcode Solution의 압축 해제 문제는 표준 솔루션입니다. 그리고 여러 회사에서 수행하는 여러 코딩 라운드에서 자주 질문됩니다. 원래 시퀀스를 저장할 새 배열을 만들어야하므로 접근 방법은 매우 간단합니다. 우리는 단순히 배열이나 벡터를 사용하고 뒤에 요소를 계속 추가합니다.

반복 할 때마다 2 단위를 점프하는 for 루프를 실행할 수 있습니다. 이것은 우리가 (주파수, 값) 쌍만을 다룬다는 것을 확인합니다. 이제 중첩 된 for 루프를 사용하여 i 번째 인덱스에있는 요소를 벡터에 추가합니다. 주어진 입력 시퀀스에서 i + 1 번째 인덱스의 요소에 따라 중첩 된 for 루프를 실행합니다.

실행 길이 인코딩 된 목록 Leetcode 솔루션의 압축 해제 코드

C ++ 코드

#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

복잡성 분석

시간 복잡성

의 위에), 여기서 N은 출력의 길이입니다. 여기서 시간 복잡도는 입력에 의존하지 않습니다. 입력 대신 시간 복잡도는 얻은 출력 또는 결과에 따라 다릅니다.

공간 복잡성

의 위에), 여기서 N은 출력의 길이입니다. 우리는 그것을 반환하기 때문에 출력을 저장하기 때문입니다. 공간도 차지합니다.

실행 길이로 인코딩 된 목록 Leetcode 솔루션의 압축 해제