Hướng Dẫn Bài Run-length Encoding

Ý tưởng:

Hàm solve1: in ra xâu với số lần xuất hiện của từng kí tự từ xâu cho trước

Hàm solve2: in ra xâu gồm các kí tự và số lần xuất hiện cho trước từ xâu ban đầu

Lưu ý: Chỉ kham khảo, không nên chép code.

Code mẫu:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;
void solve1(string s) {
    int n = s.size();
    if (n == 0) return;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            cnt++;
        } else {
            cout << cnt << s[i - 1];
            cnt = 1;
        }
    }
    cout << cnt << s[n - 1];
}
void solve2(string s){
    int n = s.size();
    string res = "";
    for(int i = 0; i < n; i++){
        int cnt = 0;
        while(i < n && isdigit(s[i])){
            cnt = cnt * 10 + (s[i] - '0');
            i++;
        }
        if(i < n && isalpha(s[i])){
            res += string(cnt, s[i]);
        }   
    }
    cout << res;
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    string s1, s2;
    cin >> s1 >> s2;
    solve1(s1);
    cout << endl;
    solve2(s2);
    return 0;
} 

Hướng dẫn giải bài Run-length encoding

Lưu ý: Chỉ kham khảo không nên chép code

Ý tưởng:

solve1: in ra xâu chứa số lần xuất hiện của từng kí tự trong xâu ban đầu

solve2: in ra xâu từ xâu cho trước số lần xuất hiện của kí tự

Code mẫu:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;
void solve1(string s){
    int n = s.size();
    unordered_map<char, int> mp;
    for(char c : s) mp[c]++;
    unordered_set<int> pr;
    for(char c : s){
        if(pr.find(c) == pr.end()){
            cout << mp[c] << c;
            pr.insert(c);
        }
    }   
}
void solve2(string s){
    int n = s.size();
    string res = "";
    for(int i = 0; i < n; i++){
        int cnt = 0;
        while(i < n && isdigit(s[i])){
            cnt = cnt * 10 + (s[i] - '0');
            i++;
        }
        if(i < n && isalpha(s[i])){
            res += string(cnt, s[i]);
        }   
    }
    cout << res;
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    string s1, s2;
    cin >> s1 >> s2;
    solve1(s1);
    cout << endl;
    solve2(s2);
    return 0;
}

Lời giải (Python)

Chỉ nên tham khảo

Hướng giải

Đầu tiên ta phân tích đầu vào của hệ thống, nhận thấy ta cần sử dụng hai hàm để giải quyết hai vấn đề (mã hóa và giải mã) > Với mã hóa

• Ta nhận thấy đầu vào là một dãy kí tự giống nhau sẽ liền kề, ta sẽ đếm theo các kí tự giống nhau liên tiếp để in ra phần số của mã hóa
• Sau khi có đếm xong ta in kết quả với dạng <số><chữ>

def mahoa(x):
    last = x[0] # kí tự đầu tiên giống
    count = 0 # đếm số kí tự thỏa mãn
    s = "" # một xâu rỗng để thêm kết quả
    for i in x:
        if i == last: # nếu kí tự này vẫn nằm trong một chuỗi liên tiếp
            count += 1
        else:
            s = s + str(count) + last # thêm số và kí tự vào đáp án 
            last = i; # Khởi tạo biến lại như ban đầu
            count = 1 # Tại vì mình set cả kí tự này nên sẽ đếm từ 1
    s = s + str(count) + last # thêm vào đáp án chuỗi kí tự giống nhau cuối cùng
    return s

> Với giải mã

• Tiếp tục xác định phần số và phần chữ
• Vì là chữ số nên ta phải thêm chữ số cho đến khi gặp kí tự để tạo thành số lần lặp hoàn chỉnh

def giaima(x):
    number = ""
    s = ""
    for i in x:
        if "0" <= i <= "9": # kiểm tra xem có phải chữ số / thêm vào để tạo thành số hoàn chỉnh
            number += i
        else:
          s = s + i*int(number) # in ra kết quả dựa theo chữ số và số đã set
          number = ""
    return s;