C++의 혼란스러운 숫자 II

<시간/>

숫자가 있다고 가정해 보겠습니다. 이제 해당 숫자를 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, rotate, digit, N,
가 필요합니다.
회전이 num과 같지 않으면 -
- (ret 1 증가)
초기화 i :=0의 경우, i <유효한 크기일 때 업데이트(i를 1만큼 증가), −
- 발굴 :=유효[i]
- num * 10 + dig> N이면
  - 루프에서 나오세요
- solve(num * 10 + dig, 하나의 맵 정의, digit * 10, N)
주요 방법에서 다음을 수행하십시오 -
ret :=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));
}