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

난이도 쉽게
자주 묻는 질문 아마존 Apple 구글
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 28

Run-Length Encoded List Leetcode Solution의 압축 해제 문제는 정렬 또는 시퀀스를 포함하는 벡터. 시퀀스에는 특정 표현이 있습니다. 입력 시퀀스는 다른 시퀀스에서 구성됩니다. 다른 시퀀스를 원래 시퀀스라고 부를 것입니다. 입력 시퀀스가 ​​생성 된 기준. 원래 시퀀스를 찾아야합니다. 시퀀스의 각 홀수 (ith) 인덱스는 원래 시퀀스에서 다음 (i + 1 번째) 인덱스가 반복되는 횟수를 나타냅니다. 따라서 항상 솔루션을 시작하기 전에 몇 가지 예를 살펴 보겠습니다.

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

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은 출력의 길이입니다. 우리는 그것을 반환하기 때문에 출력을 저장하기 때문입니다. 공간도 차지합니다.

코멘트를 남겨

Translate »
1