전체 실행 길이 디코딩?

Question

실행 길이로 인코딩 된 문자열, 예를 들어 "A3B1C2D1E1"이 제공되면 문자열을 적절한 위치에서 디코딩하십시오. 인코딩 된 문자열에 대한 대답은 "AAABCCDE"입니다. 인코딩 된 배열이 디코딩 된 문자열을 수용 할만큼 충분히 크다고 가정합니다. 즉, 배열 크기 = MAX [length (encodedstirng), length (decodedstring)]라고 가정 할 수 있습니다.

A3를 'AAA'로 단순히 디코딩하면 원래 문자열의 'B'를 덮어 쓰게되므로이 작업은 사소한 것처럼 보이지 않습니다.

또한 디코딩 된 문자열이 항상 인코딩 된 문자열보다 큰 것으로 가정 할 수 없습니다. 예 : 인 코드 된 문자열 - 'A1B1', 디코딩 된 문자열은 'AB'입니다. 이견있는 사람? 당신이 그것에 대해 생각하는 경우가 특히 어려운 일이 아니다 비록

그리고 항상 편지 자리 쌍 것, 즉 당신은 0000055555

Answer 1

아직 알지 못하는 경우 먼저 디코딩 된 문자열의 길이를 계산하기 위해 숫자를 합산하여 스캔해야합니다.

항상 문자 숫자 쌍이므로 문자열에서 1을 혼동하지 않고 삭제할 수 있습니다.

A3B1C2D1E1 

여기

A3BC2DE 

된다 문자열 (O (N)의 복잡성)로부터 1 S를 제거하고, C++, 일부 코드이다.

// remove 1s 
int i = 0; // read from here 
int j = 0; // write to here 
while(i < str.length) { 
    assert(j <= i); // optional check 
    if(str[i] != '1') { 
     str[j] = str[i]; 
     ++ j; 
    } 
    ++ i; 
} 
str.resize(j); // to discard the extra space now that we've got our shorter string 

이제이 문자열은 최종 디코딩 된 문자열보다 짧거나 길이가 보장됩니다. 원래 문자열에 대한 주장을 할 수는 없지만이 수정 된 문자열에 대해 만들 수 있습니다.

(선택 사항, 이제 모든 단계는 이전의 문자 2을 이전 문자 A3BCCDE으로 바꿔야합니다.하지만 그렇게 할 필요는 없습니다).

이제 작업을 시작할 수 있습니다. 이미 디코딩 된 문자열의 길이를 계산 했으므로 최종 문자의 위치를 ​​정확히 알 수 있습니다. 짧은 문자열 끝에있는 문자를 최종 위치로 복사하기 만하면됩니다.

오른쪽에서 왼쪽으로 복사하는 과정에서 숫자를 보게되면 문자 왼쪽에 여러 개의 복사본을 만들어야합니다. 너무 많은 데이터를 덮어 쓸 위험이 있음을 염려 할 수도 있습니다. 그러나 우리는 이전에 인코딩 된 문자열 또는 그 부분 문자열이 해당 디코드 된 문자열보다 길지 않을 것이라고 이전에 입증했습니다. 이는 항상 충분한 공간이 있음을 의미합니다.

Answer 2

이것은 매우 모호한 질문으로 전환 0515로하라는 메시지가 표시되지 않습니다. 다시 말하면, A3을 AAA으로 디코딩하고 그 자리에 글자를 쓰면 문자 B과 1을 덮어 쓰게됩니다. 그래서 먼저 배열을 따라 더 멀리 이동하지 않는 것이 어떻습니까?

예를 들어, A3을 읽은 후에는 여분의 문자 한 개를 넣을 공간이 필요하다는 것을 알 수 있습니다. A4이면 두 개가 필요합니다. 이것을 달성하기 위해 배열에서 문자열의 끝을 찾을 수 있습니다 (이 작업은 미리 수행하고 인덱스를 저장합니다).

그런 다음 루프하지만, 그들의 새로운 슬롯 문자를 이동 :

시작하려면 A|3|B|1|C|2||||||| 즉 마지막으로, 공백이 아닌, 엔트리 인덱스 5, 저장 end라는 변수 되세요.

당신은 당신의 현재 위치를 저장하는 cursor라는 변수를 사용하여 첫 번째 쌍에서 읽은 것 - 그래서 A과 3가합니다 (3 슬롯)을 1로 설정 될 수에서 읽은 후. 이동 대

의사 코드 :

VAR의 N = 배열 ​​[커서] - 2; // n = 1, A3에서 3, 그리고 쌍을 허용하려면 2입니다.

for (i = end; i> 커서; i ++) { array [i + n] = array [i];

: 그래서 지금 당신이 n + 1 A 's이 (가) cursor에 저장된 인덱스부터 시작하여 쓰고 싶은,

A|3|A|3|B|1|C|2|||||

이제 A 이미 한 번있다 : }

이 당신을 떠날 것이다

for(i = cursor; i < cursor + n + 1; i++) 
{ 
    array[i] = array[cursor - 1]; 
} 

// increment the cursor afterwards! 
cursor += n + 1; 

주는 :

A|A|A|A|B|1|C|2|||||

다음 값 쌍 시작 위치를 가리키며 다시 준비가됩니다. 나는이 답변에 몇 가지 구멍이 있음을 알고 있습니다.하지만 이는 인터뷰 질문이기 때문에 의도적 인 것입니다!예를 들어, A1B1으로 지정된 가장자리의 경우, 후속 문자를 전달하지 않고 뒤로 이동하려면 다른 루프가 필요합니다.

Answer 3

다른 O (n^2) 솔루션이 뒤 따른다.

답변의 복잡성에 제한이 없으므로이 간단한 해결책은 완벽하게 작동하는 것 같습니다.

• 여유 공간의 크기가 배열에 남아있는 빈 요소의 수는 다음과 같습니다

  while (there is an expandable element): 
      expand that element 
      adjust (shift) all of the elements on the right side of the expanded element 
  

  .

  expanded size - encoded size <= free space size 
  

포인트가 각 단계에서 발포 문자열 런 렝스 코드로부터 도달하는 과정에서이 있다는 :

확장 가능한 요소는 원소이고 최소 확장 가능 (입증하기 쉬운) 한 요소.

Answer 4

다음 솔루션은 O(n)입니다. 알고리즘은 읽거나 쓰지 말아야하는 메모리에 액세스해서는 안됩니다. 일부 디버깅을했는데 샘플 테스트에 맞았습니다.

---

높은 수준의 개요 :

• 는 코드 길이를 결정합니다.
• 모든 숫자를 읽고 합계하여 디코딩 길이를 결정하십시오.
• 버퍼의 끝은 MAX (디코딩 된 길이, 인코딩 된 길이)입니다.
• 문자열의 끝에서 시작하여 문자열을 디코딩합니다. 버퍼의 끝에서 씁니다.
• 디코딩 된 길이가 인코딩 된 길이보다 클 수 있으므로 디코딩 된 문자열은 버퍼의 시작 부분에서 시작되지 않을 수 있습니다. 필요한 경우 문자열을 처음으로 이동하여이 문제를 해결하십시오.

---

int isDigit (char c) { 
    return '0' <= c && c <= '9'; 
} 

unsigned int toDigit (char c) { 
    return c - '0'; 
} 

unsigned int intLen (char * str) { 
    unsigned int n = 0; 
    while (isDigit(*str++)) { 
     ++n; 
    } 
    return n; 
} 

unsigned int forwardParseInt (char ** pStr) { 
    unsigned int n = 0; 
    char * pChar = *pStr; 
    while (isDigit(*pChar)) { 
     n = 10 * n + toDigit(*pChar); 
     ++pChar; 
    } 
    *pStr = pChar; 
    return n; 
} 

unsigned int backwardParseInt (char ** pStr, char * beginStr) { 
    unsigned int len, n; 
    char * pChar = *pStr; 
    while (pChar != beginStr && isDigit(*pChar)) { 
     --pChar; 
    } 
    ++pChar; 
    len = intLen(pChar); 
    n = forwardParseInt(&pChar); 
    *pStr = pChar - 1 - len; 
    return n; 
} 

unsigned int encodedSize (char * encoded) { 
    int encodedLen = 0; 
    while (*encoded++ != '\0') { 
     ++encodedLen; 
    } 
    return encodedLen; 
} 

unsigned int decodedSize (char * encoded) { 
    int decodedLen = 0; 
    while (*encoded++ != '\0') { 
     decodedLen += forwardParseInt(&encoded); 
    } 
    return decodedLen; 
} 

void shift (char * str, int n) { 
    do { 
     str[n] = *str; 
    } while (*str++ != '\0'); 
} 

unsigned int max (unsigned int x, unsigned int y) { 
    return x > y ? x : y; 
} 

void decode (char * encodedBegin) { 
    int shiftAmount; 
    unsigned int eSize = encodedSize(encodedBegin); 
    unsigned int dSize = decodedSize(encodedBegin); 
    int writeOverflowed = 0; 
    char * read = encodedBegin + eSize - 1; 
    char * write = encodedBegin + max(eSize, dSize); 
    *write-- = '\0'; 
    while (read != encodedBegin) { 
     unsigned int i; 
     unsigned int n = backwardParseInt(&read, encodedBegin); 
     char c = *read; 
     for (i = 0; i < n; ++i) { 
      *write = c; 
      if (write != encodedBegin) { 
       write--; 
      } 
      else { 
       writeOverflowed = 1; 
      } 
     } 
     if (read != encodedBegin) { 
      read--; 
     } 
    } 
    if (!writeOverflowed) { 
     write++; 
    } 
    shiftAmount = encodedBegin - write; 
    if (write != encodedBegin) { 
     shift(write, shiftAmount); 
    } 
    return; 
} 

int main (int argc, char ** argv) { 
    //char buff[256] = { "!!!A33B1C2D1E1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char buff[256] = { "!!!A2B12C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    //char buff[256] = { "!!!A1B1C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char * str = buff + 3; 
    //char buff[256] = { "A1B1" }; 
    //char * str = buff; 
    decode(str); 
    return 0; 
}