Стекийг ашиглан дугаарыг буцаах


Хэцүү байдлын түвшин Easy
Байнга асуудаг MAQ Nokia o9 шийдэл
Математик Stack

Буцааж тоог ашиглан стек бодлогыг илэрхийлсэн бүхэл тоон хувьсагчийг өгсөн болно. Өгөгдсөн дугаарыг стек ашиглан буцааж хэвлэ.

Стекийг ашиглан дугаарыг буцаах

Жишээ нь

Оролт: 12345

Үр дүн: 54321

Оролт: 207

Үр дүн: 702

Стек ашиглан дугаарыг буцаах тайлбар

N = 12345 дугаарыг оруулъя

Тойрч эхэлж өгөгдсөн тооны цифрүүдийг стек дээр нэг нэгээр нь хадгалаад тоог / 10 гэж шинэчил.

  • алхам 1: n = 1234 стек = 5
  • алхам 2: n = 123 стек = 5,4
  • алхам 3: n = 12 стек = 5,4,3
  • алхам 4: n = 1 стек = 5,4,3,2
  • алхам 5: n = стек = 5,4,3,2,1

Үүний дараа стекээс элементүүдийг гаргаж, тоог дараах байдлаар үүсгэнэ.

урвуу = урвуу + (стекийн дээд талын утга * i) (энд i = 1, алхам бүрт i * 10 гэж шинэчилнэ)

Тиймээс гаралт = 54321

Стек ашиглан дугаарыг буцаах алгоритм

  1. Тоог илэрхийлэх бүхэл тоон хувьсагчийг эхлүүлнэ.
  2. Өгөгдсөн тооны цифрүүдийг хадгалахын тулд бүхэл тооны стекийг үүсгээрэй.
  3. Өгөгдсөн тооны уртыг дайран өнгөрч, тоо 0-тэй тэнцэхгүй байхад өгөгдсөн тооны 10-ийн үр дүнг стек рүү түлхэж, дараа нь өгөгдсөн тоог давталт бүрт 10-т хуваана.
  4. Өгөгдсөн тооны урвууг хадгалахын тулд бүхэл тоон хувьсагчийг үүсгээд 0 гэж эхлүүлнэ. Цифрүүдийн байрлалын утгыг барьж, 1 болгож эхлүүлэхийн тулд өөр бүхэл хувьсагчийг үүсгээрэй.
  5. Стек хоосон биш байхад хөндлөн огтлолцоорой, өөрөөр хэлбэл стекийн хэмжээ нь 0-тэй тэнцүү биш байна. Бүхэл тоон хувьсагчийг шинэчилж, өгөгдсөн тооны урвуу талыг тухайн урвуу хувьсагч дотор хадгалагдсан утга болгон хадгална. стекийг тухайн газрын утгын бүхэл хувьсагчаар үржүүлнэ.
  6. Стекийн дээд хэсэгт байрлах элементийг поп / устгаад байрлалын утгын бүхэл тоон хувьсагчийг байршлын утгын хувьсагчид хадгалагдах утга өөрөө 10-аар үржигдэх тул шинэчлэх хэрэгтэй.
  7. Өгөгдсөн тооны урвууг агуулсан бүхэл тоон хувьсагчийг хэвлэ.

C ++ програмыг стек ашиглан буцаах програм

#include <iostream>
#include <stack>
using namespace std; 
  
stack <int> st; 
  
void push_digits(int number){ 
    
    while(number != 0){ 
        st.push(number % 10); 
        number = number / 10; 
    } 
} 
  
int reverse_number(int number){ 
    push_digits(number); 
      
    int reverse = 0; 
    int i = 1; 
      
    while(!st.empty()){ 
        reverse = reverse + (st.top() * i); 
        st.pop(); 
        i = i * 10; 
    } 
      
    return reverse; 
} 
  
int main(){ 
    int number = 12345; 
      
    cout << reverse_number(number); 
      
    return 0; 
}
54321

Стек ашиглан дугаарыг буцаах Java програм

import java.util.Stack; 
  
class ReverseDigits{ 
    
    static Stack<Integer> st= new Stack<>(); 
  
    static void push_digits(int number){ 
        
        while(number != 0){ 
            st.push(number % 10); 
            number = number / 10; 
        } 
    } 
  
    static int reverse_number(int number){ 
        push_digits(number); 
        int reverse = 0; 
        int i = 1; 
  
        while (!st.isEmpty()){ 
            reverse = reverse + (st.peek() * i); 
            st.pop(); 
            i = i * 10; 
        } 
  
        return reverse; 
    } 
  
    public static void main(String[] args){ 
        int number = 12345;
        
        System.out.println(reverse_number(number));
        
    } 
}
54321

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал: O (log n), энд n нь тухайн тооны урт юм.

Туслах орон зай: O (log n), учир нь бид өгөгдсөн тооны цифрийг буцаахын тулд log n нэмэлт зайг ашигласан.

Ашигласан материал