Giả sử chúng ta có một chữ số, bây giờ nếu chúng ta xoay chữ số đó đi 180 độ để tạo thành các chữ số mới. Khi các 0, 1, 6, 8, 9 được xoay 180 độ, chúng trở thành 0, 1, 9, 8, 6 tương ứng. Nhưng khi 2, 3, 4, 5 và 7 được xoay 180 độ, chúng sẽ trở nên không hợp lệ.
Một số khó hiểu là một số mà khi xoay 180 độ sẽ trở thành một số mới. Vì vậy, nếu chúng ta có một số nguyên dương N, chúng ta phải tìm số lượng các số khó hiểu giữa 1 và N.
Vì vậy, nếu đầu vào là 20, thì đầu ra sẽ là 6
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một ánh xạ bản đồ
-
Xác định một mảng hợp lệ
-
Xác định một hàm giải quyết (), điều này sẽ lấy num, xoay, chữ số, N,
-
nếu xoay không bằng num, thì -
-
(tăng ret lên 1)
-
-
để khởi tạo i:=0, khi i
-
dig:=valid [i]
-
nếu num * 10 + dig> N, thì
-
Ra khỏi vòng lặp
-
-
giải quyết (num * 10 + dig, Xác định một bản đồ, chữ số * 10, N)
-
-
Từ phương thức chính, hãy làm như sau -
-
ret:=0
-
hợp lệ:={0, 1, 6, 8, 9}
-
ánh xạ [0]:=0
-
ánh xạ [1]:=1
-
ánh xạ [6]:=9
-
ánh xạ [9]:=6
-
ánh xạ [8]:=8
-
giải quyết (1, 1, 10, N)
-
giải quyết (6, 9, 10, N)
-
giải quyết (9, 6, 10, N)
-
giải quyết (8, 8, 10, N)
-
trả lại ret
Hãy cùng chúng tôi xem cách 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