Số Strobogrammatic III trong C++

Đếm số lượng số Strobogrammatic trong khoảng [low, high]. Số Strobogrammatic: đọc giống nhau khi xoay 180 độ (cặp: 0↔0, 1↔1, 8↔8, 6↔9, 9↔6).

Ví dụ: low = "50", high = "100" → Kết quả = 3 (69, 88, 96).

Phương pháp giải

Sinh tất cả số Strobogrammatic độ dài từ len(low) đến len(high). Đệ quy: độ dài lẻ → giữa là 0/1/8; độ dài chẵn → giữa rỗng. Mỗi bước thêm cặp (1,1), (8,8), (6,9), (9,6) hai bên; nếu không phải độ dài tối đa thì thêm (0,0). So sánh chuỗi để đếm số trong khoảng.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector findStrobogrammatic(int n) {
        vector ret;
        if (n & 1) { ret = {"0", "1", "8"}; }
        else { ret = {""}; }
        
        for (; n > 1; n -= 2) {
            vector temp;
            for (string& s : ret) {
                if (n > 3) temp.push_back("0" + s + "0");
                temp.push_back("1" + s + "1");
                temp.push_back("8" + s + "8");
                temp.push_back("6" + s + "9");
                temp.push_back("9" + s + "6");
            }
            ret = temp;
        }
        return ret;
    }
    
    bool compare(string a, string b) {
        return a.size() == b.size() ? a >= b : a.size() > b.size();
    }
    
    int strobogrammaticInRange(string low, string high) {
        int ret = 0;
        vector v;
        for (int i = low.size(); i <= high.size(); i++) {
            v = findStrobogrammatic(i);
            for (string& s : v) {
                if (compare(s, low) && compare(high, s)) ret++;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.strobogrammaticInRange("50", "100");
    return 0;
}

Đầu vào

"50", "100"

Đầu ra

3