Confusing Number II (ตัวเลขสับสน ระดับ 2) ใน C++

สมมติว่าเรามีหลักเลข ถ้าเราหมุนหลักเลขนั้น 180 องศา เพื่อสร้างหลักเลขใหม่ เมื่อ 0, 1, 6, 8, 9 ถูกหมุน 180 องศา จะกลายเป็น 0, 1, 9, 8, 6 ตามลำดับ แต่เมื่อ 2, 3, 4, 5 และ 7 ถูกหมุน 180 องศา จะกลายเป็น invalid

Confusing Number คือ ตัวเลขที่เมื่อหมุน 180 องศา จะกลายเป็นตัวเลขใหม่ (ต่างจากตัวเดิม) ถ้าเรามีจำนวนเต็มบวก N เราต้องหาจำนวน confusing numbers ระหว่าง 1 ถึง N รวมทั้งสองขอบ

ดังนั้น หากอินพุทคือ 20 ผลลัพธ์จะเป็น 6

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

• กำหนด map mapping

• กำหนดอาเรย์ valid

• กำหนดฟังก์ชัน solve() รับ num, rotate, digit, N

• ถ้า rotate != num: เพิ่ม ret

• for i := 0 ถึงขนาดของ valid - 1:

  • dig := valid[i]

  • ถ้า num * 10 + dig > N: break

  • solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N)

• จาก main method:

  • ret := 0

  • valid := {0, 1, 6, 8, 9}

  • mapping[0]=0, mapping[1]=1, mapping[6]=9, mapping[9]=6, mapping[8]=8

  • solve(1, 1, 10, N), solve(6, 9, 10, N), solve(9, 6, 10, N), solve(8, 8, 10, N)

  • คืนค่า ret

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

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

typedef long long int lli;

class Solution {
public:
    int ret;
    map mapping;
    vector valid;

    void solve(lli num, lli rotate, lli digit, lli N) {
        if (rotate != num) {
            ret++;
        }
        for (int i = 0; i < valid.size(); i++) {
            int dig = valid[i];
            if (num * 10 + dig > N) {
                break;
            }
            solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N);
        }
    }

    int confusingNumberII(int N) {
        ret = 0;
        valid = {0, 1, 6, 8, 9};
        mapping[0] = 0;
        mapping[1] = 1;
        mapping[6] = 9;
        mapping[9] = 6;
        mapping[8] = 8;
        solve(1, 1, 10, N);
        solve(6, 9, 10, N);
        solve(9, 6, 10, N);
        solve(8, 8, 10, N);
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.confusingNumberII(20));
    return 0;
}

อินพุต

20

เอาต์พุต

6