สมมติว่าเรามีจำนวนเต็มสองตัวต่ำและสูง เราต้องหาและแสดงรายการที่เรียงลำดับของหมายเลขก้าวทั้งหมดในช่วง [ต่ำ สูง] รวม Stepping Number เป็นจำนวนเต็มหมายความว่าตัวเลขที่อยู่ติดกันทั้งหมดมีความแตกต่างที่แน่นอนของ 1 ตัวอย่างเช่น 321 คือ Stepping Number แต่ 421 ไม่ใช่ ดังนั้นหากอินพุตมีค่าต่ำ :=0 และสูง :=21 ผลลัพธ์จะเป็น [0,1,2,3,4,5,6,7,8,9,10,12,21]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างหนึ่งอาร์เรย์ชั่วคราว
- สร้างเมธอดหนึ่งวิธีที่เรียกว่า Solve() ซึ่งจะต้องใช้ high, seed และ len len เริ่มต้น 0
- ถ้าเมล็ด> สูงก็คืน
- ใส่เมล็ดลงในอาร์เรย์ชั่วคราว
- ถ้าเมล็ดเป็น 0 แล้ว
- สำหรับ i ในช่วง 1 ถึง 9 ให้ดำเนินการแก้ปัญหา (สูง, i, 1)
- อย่างอื่น
- lastDigit :=seed mod 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)
- จัดเรียงอาร์เรย์ชั่วคราว
- สร้างอาร์เรย์หนึ่งอัน
- สำหรับฉันในช่วง 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, ]
