home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Stepping Numbers ใน C++: หาตัวเลขที่ตัวเลขติดกันต่างกัน 1

โจทย์

Stepping Number คือจำนวนเต็มที่ตัวเลขติดกันทุกคู่มีความต่างสัมบูรณ์ = 1 (เช่น 321 ✓, 421 ✗) หา Stepping Numbers ทั้งหมดในช่วง [low, high] เรียงลำดับ

ตัวอย่าง: low=0, high=21 → [0,1,2,3,4,5,6,7,8,9,10,12,21]

แนวคิด: DFS สร้างตัวเลขแบบเพิ่มหลักท้ายทีละตัว

เริ่มจาก 0-9 สร้างต่อโดยเพิ่มหลักท้าย ±1 จากหลักสุดท้าย จนเกิน high

ขั้นตอน

  1. ฟังก์ชัน solve(high, seed, len):
    • ถ้า seed > high → return
    • เพิ่ม seed ลง temp
    • ถ้า seed == 0 → เรียก solve(high, i, 1) สำหรับ i=1..9
    • มิฉะนั้น:
      • last = seed % 10
      • ถ้า last >= 1 && len+1 <= 10 → solve(high, seed*10 + last-1, len+1)
      • ถ้า last <= 8 && len+1 <= 10 → solve(high, seed*10 + last+1, len+1)
  2. เรียก solve(high, 0, 0)
  3. เรียง temp แล้วกรองเฉพาะ ≥ low

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
    vector<long long> temp;
    void solve(int high, long long seed = 0, int len = 0) {
        if (seed > high) return;
        temp.push_back(seed);
        if (seed == 0) {
            for (int i = 1; i <= 9; i++) solve(high, i, 1);
        } else {
            int last = seed % 10;
            if (last >= 1 && len + 1 <= 10) solve(high, seed * 10 + last - 1, len + 1);
            if (last <= 8 && len + 1 <= 10) solve(high, seed * 10 + last + 1, len + 1);
        }
    }
public:
    vector<int> countSteppingNumbers(int low, int high) {
        solve(high);
        sort(temp.begin(), temp.end());
        vector<int> ans;
        for (long long x : temp) if (x >= low) ans.push_back(x);
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.countSteppingNumbers(0, 40));
    return 0;
}

อินพุต / เอาต์พุต

Input: 0 40

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

ความซับซ้อน

  • Time: O(จำนวน Stepping Numbers) - สร้างเฉพาะตัวเลขที่ถูกต้อง
  • Space: O(จำนวน Stepping Numbers) - เก็บผลลัพธ์ชั่วคราว

ข้อสังเกต

จำกัดความยาว ≤ 10 หลัก เพราะ int สูงสุด ~2×10^9 (10 หลัก)