Tìm ký tự thứ k của chuỗi giải mã - Tập 2 trong C++

Khái niệm

Cho chuỗi được mã hóa, nơi lặp lại chuỗi con được biểu thị bằng chuỗi con theo sau là số lần lặp. Ví dụ: chuỗi mã hóa "pq2rs2" và k=5, kết quả là 'r' vì chuỗi giải mã là "pqpqrsrs" và ký tự thứ 5 là 'r'.

Tần suất lặp có thể nhiều hơn một chữ số. Ví dụ: "pq12r3", pq lặp 12 lần. Không có số 0 dẫn đầu trong tần suất.

Đầu vào

"p2q2r3", k = 6

Đầu ra

r

Chuỗi giải mã: "ppqqrrr"

Đầu vào

"pq4r2ts3", k = 11

Đầu ra

t

Chuỗi giải mã: "pqpqpqpqrrtststs"

Phương pháp

Thuật toán từng bước:

• Xác định độ dài chuỗi con hiện tại. Dùng hai con trỏ: một con trỏ cố định tại đầu chuỗi con, con trỏ khác đi đến khi gặp chữ số.
• Xác định tần suất lặp bằng cách di chuyển con trỏ thứ hai cho đến khi gặp chữ cái.
• Tính độ dài chuỗi con khi lặp bằng tần suất nhân độ dài gốc.
• Nếu độ dài này nhỏ hơn k, ký tự cần tìm nằm ở chuỗi con tiếp theo. Trừ độ dài này khỏi k để đếm số ký tự còn cần duyệt.
• Nếu độ dài lớn hơn hoặc bằng k, ký tự cần tìm nằm trong chuỗi con hiện tại. Vì k đánh chỉ số từ 1, giảm k đi 1 và lấy modulo với độ dài chuỗi con gốc. Ký tự cần tìm là ký tự thứ k từ đầu chuỗi con được trỏ bởi con trỏ đầu.

Ví dụ

// Chương trình C++ tìm ký tự thứ K trong chuỗi giải mã
#include <bits/stdc++.h>
using namespace std;

// Hàm tìm ký tự thứ K trong chuỗi mã hóa
char encodedChar(string str, int k){
    int a, b;
    int m = str.length();
    int len1; // độ dài chuỗi con
    int num1; // độ dài chuỗi con khi lặp
    int freq1; // tần suất chuỗi con
    a = 0;
    while (a < m) {
        b = a;
        len1 = 0;
        freq1 = 0;
        // Xác định độ dài chuỗi con
        while (b < m && isalpha(str[b])) {
            b++;
            len1++;
        }
        // Xác định tần suất lặp
        while (b < m && isdigit(str[b])) {
            freq1 = freq1 * 10 + (str[b] - '0');
            b++;
        }
        // Độ dài khi lặp
        num1 = freq1 * len1;
        // Nếu độ dài lặp nhỏ hơn k
        if (k > num1) {
            k -= num1;
            a = b;
        }
        // Nếu độ dài lặp lớn hơn hoặc bằng k
        else {
            k--;
            k %= len1;
            return str[a + k];
        }
    }
    // Trường hợp không có lặp lại, ví dụ str="abced"
    return str[k - 1];
}

// Chương trình chính
int main(){
    string str1 = "pqpqpqpqrrtststs";
    int k1 = 11;
    cout << encodedChar(str1, k1) << endl;
    string str2 = "p2q2r3";
    int k2 = 6;
    cout << encodedChar(str2, k2) << endl;
    return 0;
}

Đầu ra

t r