मान लीजिए कि हमारे पास दो पूर्णांक निम्न और उच्च हैं, हमें श्रेणी [निम्न, उच्च] सहित सभी स्टेपिंग नंबरों की एक क्रमबद्ध सूची ढूंढनी और दिखाना है। एक स्टेपिंग नंबर एक पूर्णांक है जिसका अर्थ है कि इसके सभी आसन्न अंकों का बिल्कुल 1 का अंतर है। उदाहरण के लिए, 321 एक स्टेपिंग नंबर है लेकिन 421 नहीं है। तो अगर इनपुट निम्न की तरह है:=0 और उच्च:=21, तो परिणाम [0,1,2,3,4,5,6,7,8,9,10,12,21] होगा। पी>
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक सरणी अस्थायी बनाएं
- हल () नामक एक विधि बनाएं, इसमें उच्च, बीज और लेन लगेगा। लेन शुरू में 0 . है
- अगर बीज> ऊंचा है, तो वापस आ जाएं
- अस्थायी सरणी में बीज डालें
- यदि बीज 0 है, तो
- 1 से 9 की श्रेणी में i के लिए, हल करें (उच्च, i, 1)
- अन्यथा
- lastDigit :=बीज मॉड 10
- अगर लास्टडिजिट>=1 और लेन + 1 <=10, तो हल करें(हाई, (बीज*10) + लास्टडिजिट -1, लेन + 1)
- अगर लास्टडिजिट <=8 और लेन + 1 <=10, तो हल करें(हाई, (बीज*10) + लास्टडिजिट + 1, लेन + 1)
- मुख्य विधि इस प्रकार होगी -
- समाधान (उच्च, 0, 0)
- अस्थायी सरणी को क्रमबद्ध करें
- एक सरणी उत्तर बनाएं
- मैं के लिए 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, ]