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になります

これを解決するには、次の手順に従います-

• 1つのマップマッピングを定義する

• 有効なアレイを定義する

• 関数solve（）を定義します。これには、num、rotate、digit、N、

  が必要です。

• 回転がnumと等しくない場合、-

  • （retを1増やします）

• 初期化i：=0の場合、i <有効なサイズの場合、更新（iを1増やします）、実行-

  • dig：=valid [i]

  • num * 10 + dig> Nの場合、

    • ループから出てきます

  • resolve（num * 10 + dig、Define one map、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）

• 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