C ++中令人困惑的数字II

假设我们现在有一个数字，如果我们将其旋转180度以形成新的数字。当0、1、6、8、9旋转180度时，它们分别变为0、1、9、8、6。但是，将2、3、4、5和7旋转180度时，它们将无效。

令人困惑的数字是当旋转180度时变成一个新数字的数字。因此，如果我们有一个正整数N，我们必须找出介于1和N之间（含1和N）的令人困惑的数字的数量。

因此，如果输入为20，则输出为6

为了解决这个问题，我们将遵循以下步骤-

• 定义一个映射映射

• 定义一个有效的数组

• 定义一个函数solve()，它将使用num，rotate，digit，N，

• 如果rotate不等于num，则-

• （增加ret 1）

• 对于初始化i：= 0，当i <有效大小时，更新（将i增加1），执行-

• 从循环中出来

• 挖：=有效[i]

• 如果num * 10 + dig> N，则

• resolve（num * 10 + dig，定义一张映射，数字* 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)

• 返回ret

让我们看下面的实现以更好地理解-

示例

#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