Giải mã độ dài chạy tại chỗ?

Question

Cho một chuỗi được mã hóa độ dài chạy, nói "A3B1C2D1E1", giải mã chuỗi tại chỗ. Câu trả lời cho chuỗi được mã hóa là "AAABCCDE". Giả sử rằng mảng được mã hóa đủ lớn để chứa chuỗi được giải mã, tức là bạn có thể giả định rằng kích thước mảng = MAX [length (encodedstirng), length (decodedstring)].

Điều này không có vẻ tầm thường, vì chỉ giải mã A3 là 'AAA' sẽ dẫn đến ghi đè 'B' của chuỗi gốc.

Ngoài ra, người ta không thể giả định rằng chuỗi được giải mã luôn lớn hơn chuỗi được mã hóa. Ví dụ: Chuỗi được mã hóa - 'A1B1', Chuỗi được giải mã là 'AB'. Có suy nghĩ gì không?

Và nó sẽ luôn luôn là một cặp thư chữ số, ví dụ: bạn sẽ không bị yêu cầu chuyển đổi 0515-0000055555

Answer 1

Nếu chúng ta chưa biết, chúng ta nên quét qua đầu tiên, thêm các chữ số, để tính toán độ dài của chuỗi được giải mã.

Nó sẽ luôn là cặp chữ số, do đó bạn có thể xóa 1 s khỏi chuỗi mà không bị nhầm lẫn.

A3B1C2D1E1 

trở thành

A3BC2DE 

Dưới đây là một số mã, trong C++, để loại bỏ các 1 s từ chuỗi (O (n) tính phức tạp).

// 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 

Bây giờ, chuỗi này được đảm bảo ngắn hơn hoặc có độ dài tương tự như chuỗi được giải mã cuối cùng. Chúng tôi không thể đưa ra tuyên bố đó về chuỗi gốc, nhưng chúng tôi có thể làm cho chuỗi này được sửa đổi.

(Một tùy chọn, tầm thường, bước bây giờ là thay thế mọi 2 bằng chữ cái trước. A3BCCDE, nhưng chúng tôi không cần phải làm điều đó).

Bây giờ chúng tôi có thể bắt đầu làm việc từ cuối. Chúng tôi đã tính toán độ dài của chuỗi đã giải mã và do đó chúng tôi biết chính xác vị trí của ký tự cuối cùng. Chúng ta chỉ có thể sao chép các ký tự từ cuối chuỗi ngắn đến vị trí cuối cùng của chúng.

Trong quá trình sao chép này từ phải sang trái, nếu chúng ta bắt gặp một chữ số, chúng ta phải tạo nhiều bản sao của chữ nằm bên trái chữ số. Bạn có thể lo lắng rằng điều này có thể có nguy cơ ghi đè quá nhiều dữ liệu. Nhưng trước đây chúng tôi đã chứng minh rằng chuỗi được mã hóa của chúng tôi hoặc bất kỳ chuỗi con nào của chúng, sẽ không bao giờ dài hơn chuỗi được giải mã tương ứng của nó; điều này có nghĩa là sẽ luôn có đủ không gian.

Answer 2

Đây là một câu hỏi rất mơ hồ, mặc dù nó không phải là đặc biệt khó khăn nếu bạn nghĩ về nó. Như bạn nói, giải mã A3 là AAA và chỉ viết nó vào vị trí sẽ ghi đè các ký tự B và 1, vậy tại sao không chỉ di chuyển xa hơn dọc theo mảng trước?

Ví dụ: khi bạn đã đọc A3, bạn biết rằng bạn cần tạo khoảng trống cho một ký tự phụ, nếu đó là A4 bạn cần hai, v.v. Để đạt được điều này bạn sẽ tìm thấy kết thúc của chuỗi trong mảng (làm điều này trả trước và lưu trữ chỉ mục của nó).

Sau đó, vòng lặp, mặc dù di chuyển nhân vật đến khe mới của họ:

Để bắt đầu: A|3|B|1|C|2||||||| Có một biến gọi là end lưu trữ các chỉ số 5, ví dụ cuối cùng, không trống, nhập cảnh.

Bạn đã đọc trong cặp đầu tiên, sử dụng biến số cursor để lưu trữ vị trí hiện tại của bạn - vì vậy sau khi đọc trong A và 3, nó sẽ được đặt thành 1 (vị trí bằng 3).

Mã giả để di chuyển:

var n = array [cursor] - 2; // n = 1, số 3 từ A3, và sau đó trừ đi 2 để cho phép cặp.

cho (i = kết thúc; i> con trỏ; i ++) { mảng [i + n] = mảng [i]; }

này sẽ để lại cho bạn với:

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

Bây giờ A là có một lần rồi, vì vậy bây giờ bạn muốn viết n + 1A 's bắt đầu từ chỉ số lưu trữ trong cursor:

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

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

Tặng:

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

Sau đó, bạn chỉ vào đầu cặp giá trị tiếp theo, sẵn sàng quay lại. Tôi nhận ra có một số lỗ hổng trong câu trả lời này, mặc dù đó là cố ý vì nó là một câu hỏi phỏng vấn!Ví dụ: trong các trường hợp cạnh bạn đã chỉ định A1B1, bạn sẽ cần một vòng lặp khác để di chuyển các ký tự tiếp theo về sau chứ không phải chuyển tiếp.

Answer 3

Một giải pháp O (n^2) khác sau.

Do không có giới hạn về độ phức tạp của câu trả lời, giải pháp đơn giản này dường như hoạt động hoàn hảo.

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

đâu:

• Free size kích thước không gian là số phần tử trống còn lại trong mảng.

• Một yếu tố có thể mở rộng là một yếu tố rằng:

  expanded size - encoded size <= free space size 
  

Vấn đề là trong quá trình đạt từ mã chạy dài vào chuỗi mở rộng, ở mỗi bước, có ít ít nhất một phần tử có thể được mở rộng (dễ chứng minh).

Answer 4

Giải pháp sau đây là O(n) và tại chỗ. Các thuật toán không nên truy cập vào bộ nhớ nó không nên, cả đọc và viết. Tôi đã làm một số gỡ lỗi, và nó xuất hiện chính xác cho các xét nghiệm mẫu tôi ăn nó.

---

cao tổng quan về mức độ:

• Xác định độ dài mã hóa.
• Xác định độ dài được giải mã bằng cách đọc tất cả các số và tổng hợp chúng.
• Kết thúc bộ đệm là MAX (độ dài được mã hóa, độ dài được mã hóa).
• Giải mã chuỗi bằng cách bắt đầu từ cuối chuỗi. Viết từ cuối bộ đệm.
• Vì độ dài được giải mã có thể lớn hơn độ dài được mã hóa, chuỗi được giải mã có thể không bắt đầu ở đầu bộ đệm. Nếu cần, hãy sửa lại điều này bằng cách dịch chuyển chuỗi đó sang đầu.

---

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; 
}