C ++中的步进数字

假设我们有两个整数低和高,我们必须找到并显示[低,高]范围内的所有步进编号的排序列表。步进号是整数,表示其所有相邻数字的绝对差都为1。例如,321是步进号,而421不是。因此,如果输入像低:= 0和高:= 21,那么结果将是[0,1,2,3,4,5,6,7,8,9,10,12,21]

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

  • 创建一个数组临时

  • 制作一种称为的方法solve(),这将需要高,种子和len。len最初为0

  • 如果种子>高,则返回

  • 将种子插入临时数组

  • 如果种子为0,则

    • 对于1到9范围内的i,执行solve(high,i,1)

  • 除此以外

    • lastDigit:=种子mod 10

    • 如果lastDigit> = 1且len + 1 <= 10,则solve(high,(seed * 10)+ lastDigit – 1,len + 1)

    • 如果lastDigit <= 8并且len + 1 <= 10,则求解(high,(seed * 10)+ lastDigit + 1,len + 1)

  • 主要方法将是-

  • 解决(高,0,0)

  • 排序临时数组

  • 使一个数组ans

  • 对于我,范围从0到临时大小– 1

    • 如果temp [i]> = low,则将temp [i]插入ans

  • 返回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, ]