สมมติว่าเรามีตัวเลขแล้ว หากเราหมุนตัวเลขนั้น 180 องศาเพื่อสร้างตัวเลขใหม่ เมื่อหมุน 0, 1, 6, 8, 9 180 องศา จะกลายเป็น 0, 1, 9, 8, 6 ตามลำดับ แต่เมื่อหมุน 2, 3, 4, 5 และ 7 180 องศา จะไม่ถูกต้อง
ตัวเลขที่สับสนคือตัวเลขที่เมื่อหมุน 180 องศา จะกลายเป็นตัวเลขใหม่ ดังนั้น หากเรามีจำนวนเต็มบวก N เราต้องหาจำนวนตัวเลขที่น่าสับสนระหว่าง 1 ถึง N
ดังนั้นหากอินพุตเท่ากับ 20 เอาต์พุตจะเป็น 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดแผนที่หนึ่งแผนที่
-
กำหนดอาร์เรย์ที่ถูกต้อง
-
กำหนดฟังก์ชัน Solve() จะใช้ num, หมุน, ตัวเลข, N,
-
ถ้าการหมุนไม่เท่ากับ num แล้ว −
-
(เพิ่มการถอยกลับโดย 1)
-
-
สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดที่ถูกต้อง ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
ขุด :=ถูกต้อง[i]
-
ถ้า num * 10 + dig> N แล้ว
-
ออกจากวง
-
-
แก้ (num * 10 + dig, กำหนดหนึ่งแผนที่, หลัก * 10, N)
-
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ยกเลิก :=0
-
ถูกต้อง :={ 0, 1, 6, 8, 9 }
-
การทำแผนที่[0] :=0
-
การทำแผนที่[1] :=1
-
การทำแผนที่[6] :=9
-
การทำแผนที่[9] :=6
-
การทำแผนที่[8] :=8
-
แก้ (1, 1, 10, N)
-
แก้(6, 9, 10, N)
-
แก้(9, 6, 10, N)
-
แก้ (8, 8, 10, N)
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
20
ผลลัพธ์
6
