Giả sử chúng ta có một chữ số, bây giờ nếu xoay chữ số đó 180 độ để tạo chữ số mới. Khi 0, 1, 6, 8, 9 được xoay 180 độ, chúng lần lượt thành 0, 1, 9, 8, 6. Nhưng khi 2, 3, 4, 5 và 7 xoay 180 độ, chúng trở nên không hợp lệ.
Một số gây nhầm lẫn là số mà khi xoay 180 độ thành một số mới. Vì vậy, nếu chúng ta có số nguyên dương N, chúng ta phải tìm số lượng số gây nhầm lẫn giữa 1 và N bao gồm cả hai đầu.
Vì vậy, nếu đầu vào là 20, đầu ra sẽ là 6
Để giải quyết, chúng ta sẽ làm theo các bước:
Định nghĩa một map mapping
Định nghĩa mảng valid
Định nghĩa hàm solve(), nhận num, rotate, digit, N,
nếu rotate không bằng num, thì:
(tăng ret lên 1)
Khởi tạo i := 0, khi i < kích thước valid, cập nhật (tăng i lên 1), làm:
dig := valid[i]
nếu num * 10 + dig > N, thì
Thoát khỏi vòng lặp
solve(num * 10 + dig, Định nghĩa một map, digit * 10, N)
Từ phương thức main làm sau:
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)
Trả về ret
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int ret; map <int, int> mapping; vector <int> 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; } }; main(){ Solution ob; cout << (ob.confusingNumberII(20)); }Đầu vào
20
Đầu ra
6