លុបធាតុកណ្តាលនៃជង់


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
ការហៅខ្លួនឯង ជង់

សេចក្តីថ្លែងការណ៍បញ្ហា។

បានផ្តល់រចនាសម្ព័ន្ធទិន្នន័យ (ជង់) ។ សរសេរកម្មវិធីដើម្បីលុបធាតុពាក់កណ្តាលនៃជង់ដែលបានផ្តល់ឱ្យដោយប្រើមុខងារមូលដ្ឋាននៃជង់ -

  • push () - ដើម្បីបញ្ចូលធាតុនៅក្នុងជង់។
  • pop () - ដើម្បីលុប / លុបធាតុខាងលើចេញពីជង់។
  • ទទេ () - ដើម្បីពិនិត្យមើលថាតើទំហំជង់ធំជាង ០ រឺក៏អត់។

បោះពុម្ពជង់ដែលបានធ្វើបច្ចុប្បន្នភាពពោលគឺជង់បន្ទាប់ពីការលុបធាតុនៅកណ្តាល។ ការប្រើប្រាស់រចនាសម្ព័ន្ធទិន្នន័យផ្សេងទៀតមិនត្រូវបានអនុញ្ញាតទេ។

លុបធាតុកណ្តាលនៃជង់

ឧទាហរណ៍

1 2 3 4 5
1 2 4 5
10 20 30 40 50 60
10 20 40 50 60

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមក ជង់ រចនាសម្ព័ន្ធទិន្នន័យនិងជំរុញធាតុនៅក្នុងវា។
  2. បង្កើតមុខងារ deleteMiddle ដែលទទួលយកជង់វាមានទំហំនិងអថេរដើម្បីតំណាងឱ្យសន្ទស្សន៍បច្ចុប្បន្នដែលជាប៉ារ៉ាម៉ែត្ររបស់វា។ កំណត់តម្លៃលំនាំដើមនៃអថេរលិបិក្រមបច្ចុប្បន្ន ០ ។
  3. ពិនិត្យមើលថាតើជង់ទទេឬអថេរសន្ទស្សន៍បច្ចុប្បន្នស្មើនឹងទំហំជង់ត្រឡប់មកវិញ។
  4. បង្កើតអថេរ x និងទុកផ្នែកខាងលើនៃជង់នៅក្នុងវា។ ដក / លុបធាតុនៅខាងលើជង់។
  5. ហៅការហៅឡើងវិញទៅមុខងារខ្លួនវាជាមួយជង់ទំហំជង់និងតម្លៃនៃអថេរសន្ទស្សន៍បច្ចុប្បន្ន + 1 ដូចដែលវាជាប៉ារ៉ាម៉ែត្រ។
  6. ពិនិត្យមើលថាតើតម្លៃនៃអថេរសន្ទស្សន៍បច្ចុប្បន្នមិនស្មើនឹងពាក់កណ្តាលនៃទំហំជង់ទេ។ ប្រសិនបើតម្លៃនៃអថេរសន្ទស្សន៍បច្ចុប្បន្នមិនស្មើនឹងសន្ទស្សន៍ពាក់កណ្តាលនៃជង់ជម្រុញអថេរ x ត្រឡប់មកវិញនៅក្នុងជង់។
  7. បន្ទាប់ពីនោះឆ្លងកាត់ខណៈពេលដែលទំហំនៃជង់មិនស្មើនឹង ០ បង្កើតបង្កើតអថេរអថេរនិងរក្សាទុកជួរខាងលើនៃជង់ដាក់លើកំពូលនៃជង់ហើយបោះពុម្ភអថេរ p សម្រាប់រាល់ការធ្វើចលនា។

វាដំណើរការពីព្រោះយើងកំពុងជួយក្នុងការហៅខ្លួនឯងដើម្បីរក្សាជង់ខាងលើដែលយើងបានរក្សាទុកក្នុងអថេរ x ដើម្បីរក្សាទុក។ យើងបន្តយកធាតុចេញពីជង់ដើមហើយបន្តរក្សាទុកនៅខាងក្នុងអថេរ ដែលនៅទីនេះដើរតួជាជង់បណ្តោះអាសន្ន។ ហើយយើងបញ្ចូលធាតុទាំងអស់ទៅក្នុងជង់ដើមលើកលែងតែធាតុណាដែលតម្លៃបច្ចុប្បន្ន = n / 2 ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីលុបធាតុកណ្តាលនៃជង់

#include<iostream>
#include<stack> 
using namespace std; 

void deleteMiddle(stack<char> &s, int n, int current=0){ 
    if(s.empty() || current == n){ 
        return; 
    }
    int x = s.top(); 
    s.pop();
    
    deleteMiddle(s, n, current+1); 
    
    if(current != n/2){ 
        s.push(x); 
    }
}

int main(){ 
    stack<char> st; 
    
    st.push('5'); 
    st.push('4'); 
    st.push('3'); 
    st.push('2'); 
    st.push('1'); 
    
    deleteMiddle(st, st.size()); 
    
    while(!st.empty()){ 
        char p=st.top(); 
        st.pop(); 
        cout << p << " "; 
    } 
    
    return 0; 
}
1 2 4 5

ចាវ៉ាកម្មវិធីដើម្បីលុបធាតុកណ្តាលនៃជង់

import java.io.*; 
import java.util.*; 
  
class delMiddle{ 
  
    static void deleteMiddle(Stack<Character> st, int n, int curr){ 
          
        if(st.empty() || curr == n){ 
            return; 
        }
          
        char x = st.pop(); 
          
        deleteMiddle(st, n, curr+1); 
          
        if(curr != n/2){ 
            st.push(x); 
        }
    } 
      
    public static void main(String args[]){
        
        Stack<Character> st = new Stack<Character>(); 
      
        st.push('5'); 
        st.push('4'); 
        st.push('3'); 
        st.push('2'); 
        st.push('1'); 
        
        deleteMiddle(st, st.size(), 0); 
      
        while(!st.empty()){ 
            char p=st.pop(); 
            System.out.print(p + " "); 
        } 
    } 
}
1 2 4 5

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N) ដែល n ជាចំនួនធាតុនៅក្នុងជង់។ ដោយសារតែយើងបានយកធាតុទាំងអស់ចេញពីជង់ហើយបន្ទាប់មកបញ្ចូលវាម្តងទៀតទៅក្នុងជង់។ ការបញ្ចូលនិងបញ្ចូលធាតុចេញពីជង់ត្រូវចំណាយពេល O (1) ។ ដូច្នេះភាពស្មុគស្មាញពេលវេលាសម្រាប់ក្បួនដោះស្រាយគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N) ពីព្រោះយើងកំពុងប្រើការហៅខ្លួនឯងដែលនឹងប្រើកន្លែងផ្ទុកធាតុដែលបានដកចេញ។