Số bước trong C ++

Giả sử chúng ta có hai số nguyên thấp và cao, chúng ta phải tìm và hiển thị một danh sách được sắp xếp của tất cả các Số bậc trong phạm vi bao gồm [thấp, cao]. Số bước là một số nguyên có nghĩa là tất cả các chữ số liền kề của nó có hiệu số tuyệt đối chính xác là 1. Ví dụ:321 là Số bước nhưng 421 thì không. Vì vậy, nếu đầu vào là thấp:=0 và cao:=21, thì kết quả sẽ là [0,1,2,3,4,5,6,7,8,9,10,12,21]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo tạm thời một mảng
• tạo một phương thức có tên là giải quyết (), phương thức này sẽ chiếm giá trị cao, hạt giống và len. ban đầu len là 0
• nếu hạt giống> cao, sau đó trả lại
• chèn hạt giống vào mảng tạm thời
• nếu hạt giống là 0, thì
  • đối với tôi trong phạm vi từ 1 đến 9, thực hiện giải quyết (cao, i, 1)
• nếu không thì
  • lastDigit:=seed mod 10
  • nếu lastDigit> =1 và len + 1 <=10, thì giải (high, (seed * 10) + lastDigit - 1, len + 1)
  • nếu lastDigit <=8 và len + 1 <=10, thì giải (high, (seed * 10) + lastDigit + 1, len + 1)
• Phương pháp chính sẽ giống như -
• giải quyết (cao, 0, 0)
• sắp xếp mảng tạm thời
• tạo một mảng ans
• cho tôi trong phạm vi 0 đến kích thước tạm thời - 1
  • if temp [i]> =low, sau đó chèn temp [i] vào ans
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

0
40

Đầu ra

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