home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หมายเลข Strobogrammatic III ใน C++

สมมติว่าเราต้องการนับจำนวนตัวเลข Strobogrammatic ทั้งหมดที่อยู่ในช่วง (low, high) ตัวเลข Strobogrammatic คือตัวเลขที่ดูเหมือนเดิมเมื่อหมุน 180 องศา

เช่น ถ้าอินพุตคือ low = "50", high = "100" ผลลัพธ์จะเป็น 3 เพราะมี 3 ตัวคือ 69, 88, 96

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

  • ฟังก์ชัน findStrobogrammatic(n): สร้างตัวเลข Strobogrammatic ความยาว n แบบ recursive: ถ้า n คี่ เริ่มจาก "0","1","8" ถ้า n คู่ เริ่มจาก ""; แล้วห่อด้วยคู่ ("1","1"),("8","8"),("6","9"),("9","6") และ ("0","0") ถ้าไม่ใช่ชั้นนอกสุด
  • ฟังก์ชัน compare(a,b): เปรียบเทียบตัวเลขแบบสตริง (ความยาวก่อน แล้วค่า lexicographic)
  • main: ลูปความยาวจาก len(low) ถึง len(high) สร้างตัวเลขทุกตัว นับจำนวนที่อยู่ในช่วง [low, high] โดยใช้ compare

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector findStrobogrammatic(int n) {
        vector 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 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) ret += compare(s, low) && compare(high, s);
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.strobogrammaticInRange("50", "100"));
}

อินพุต

"50", "100"

เอาต์พุต

3