เลขสโทรโบกรاماتิก II ใน C++

สมมติว่าเรามีความยาว n เราต้องหาเลขสโทรโบกรاماتิก (strobogrammatic numbers) ทั้งหมดที่มีความยาว n

เลขสโทรโบกรاماتิกคือเลขที่ดูเหมือนเดิมเมื่อหมุน 180 องศา คู่ตัวเลขที่ใช้ได้คือ: 0↔0, 1↔1, 8↔8, 6↔9, 9↔6

ตัวอย่าง: n = 2 ผลลัพธ์: ["11","69","88","96"]

วิธีแก้ปัญหา

1. เริ่มจากฐาน: ถ้า n คี่ ให้เริ่มจาก ["0","1","8"] มิฉะนั้นเริ่มจาก [""]
2. สร้างทีละชั้นโดยเพิ่มคู่ตัวเลขที่ตรงกันทั้งสองข้าง
3. ไม่ให้ตัวเลขนำหน้าเป็น 0 (ยกเว้น n=1)
4. ทำซ้ำจนครบความยาว n

ตัวอย่างโค้ด C++

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

void print_vector(vector<string> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    vector<string> findStrobogrammatic(int n) { 
        vector<string> ret; 
        if (n & 1) { 
            ret.push_back("0"); 
            ret.push_back("1"); 
            ret.push_back("8"); 
        } else { 
            ret.push_back(""); 
        } 
        for (; n > 1; n -= 2) { 
            vector<string> temp; 
            for (int i = 0; i < ret.size(); i++) { 
                string s = ret[i]; 
                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; 
    } 
}; 

int main(){ 
    Solution ob; 
    print_vector(ob.findStrobogrammatic(3)); 
}

ข้อมูลนำเข้า

3

ผลลัพธ์

[101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 986, ]