C++의 스테핑 숫자

낮고 높은 두 개의 정수가 있다고 가정하고 [낮음, 높음] 범위에 있는 모든 스테핑 번호의 정렬된 목록을 찾아 표시해야 합니다. 스테핑 번호는 정수이며 인접한 모든 숫자의 절대 차이가 정확히 1임을 의미합니다. 예를 들어 321은 스테핑 번호이지만 421은 그렇지 않습니다. 따라서 입력이 low :=0 및 high :=21인 경우 결과는 [0,1,2,3,4,5,6,7,8,9,10,12,21]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 어레이 임시 생성
• solve()라는 메서드를 하나 만들면 high, seed 및 len이 필요합니다. len은 처음에 0입니다.
• 시드> 높으면 반환
• 임시 배열에 시드 삽입
• 시드가 0이면
  • 1~9 범위의 i에 대해 solve(high, i, 1) 수행
• 그렇지 않으면
  • lastDigit :=시드 모드 10
  • lastDigit>=1이고 len + 1 <=10이면 해결(high, (seed*10) + lastDigit – 1, len + 1)
  • lastDigit <=8이고 len + 1 <=10이면 해결(high, (seed*10) + lastDigit + 1, len + 1)
• 주요 방법은 다음과 같습니다 -
• 해결(높음, 0, 0)
• 임시 배열 정렬
• 하나의 배열을 만들고
• i 범위 0에서 임시 크기 – 1
  • temp[i]>=낮으면 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, ]