C++でのステッピング番号

低と高の2つの整数があるとすると、[低、高]の範囲内のすべてのステッピング番号のソートされたリストを見つけて表示する必要があります。ステッピング番号は整数であり、隣接するすべての数字の絶対差が正確に1であることを意味します。たとえば、321はステッピング番号ですが、421はそうではありません。したがって、入力がlow：=0およびhigh：=21のようである場合、結果は[0,1,2,3,4,5,6,7,8,9,10,12,21]になります。

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

• 1つのアレイ一時を作成
• solve（）という1つのメソッドを作成します。これには、high、seed、lenが必要です。 lenは最初は0です
• シードが>高い場合は、戻ります
• シードを一時配列に挿入します
• シードが0の場合、
  • 1〜9の範囲のiについて、solve（high、i、1）を実行します
• それ以外の場合
  • lastDigit：=seed mod 10
  • lastDigit>=1かつlen+1 <=10の場合、solve（high、（seed * 10）+ lastDigit – 1、len + 1）
  • lastDigit<=8かつlen+1 <=10の場合、solve（high、（seed * 10）+ lastDigit + 1、len + 1）
• 主な方法は次のようになります-
• Solve（high、0、0）
• 一時配列を並べ替える
• 1つの配列を作成します
• 0から一時サイズの範囲のiの場合– 1
  • temp [i]> =lowの場合、temp[i]をansに挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
   vector <lli> temp;
   void solve(int high,lli seed=0, int len =0){
      if(seed>high){
         return;
      }
      temp.push_back(seed);
      if(!seed){
         for(int i =1;i<=9;i++){
            solve(high,i,1);
         }
      } else {
         int lastDigit = seed%10;
         if(lastDigit>=1 && len+1<=10)
            solve(high, (seed*10) + lastDigit-1,len+1);
         if(lastDigit<=8 && len+1<=10)
         solve(high, (seed*10) + lastDigit+1,len+1);
      }
   }
   vector<int> countSteppingNumbers(int low, int high) {
      solve(high);
      sort(temp.begin(),temp.end());
      vector <int> ans;
      for(int i =0;i<temp.size();i++){
         if(temp[i]>=low)ans.push_back(temp[i]);
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.countSteppingNumbers(0,40));
}

入力

0
40

出力

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, ]