Yığın istifadə edərək bir Sətri tərs çevirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Capgemini Çatdırılma Fanatics Fourkites
Qalaq SimBaxılıb 48

Biz verdik sim n uzunluğunda kiçik hərflər, böyük hərflər, tam ədədlər və bəzi xüsusi işarələr olan s. Verilmiş sətri istifadə edərək tərsinə çevirin qalaq. Daha yaxşı başa düşmək üçün bəzi nümunələrə baxaq.

Yığın istifadə edərək bir Sətri tərs çevirinPin

misal

Input 

s = "TutorialCup"

Buraxılış 

puClairotuT

Input

s = “Yığın”

Buraxılış

kcatS

Stack istifadə

Yığından istifadə edərək bir Sətri tərsləşdirmək üçün alqoritm

  1. N uzunluğunda bir simli başlayın.
  2. Simvolları saxlamaq üçün eyni ölçüdə bir yığın yaradın.
  3. Sətri keçin və hər bir simvolu bir-bir yığına itələyin.
  4. Yenidən keçin və simvolları atmağa başlayın və onları bir sətirdə birləşdirin.
  5. Tərs sətri çap edin.

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){
    
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1; 
}  
  
void push(Stack* stack, char item){  
    if (isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){
    if (isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  
  
void reverse(char s[]){  
    int n = strlen(s);  
    Stack* stack = createStack(n);  
  
    int i;  
    for(i = 0; i < n; i++){  
        push(stack, s[i]); 
    }    
  
    for(i = 0; i < n; i++){  
        s[i] = pop(stack);
    }    
}  
  
int main(){  
    char s[] = "TutorialCup";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}
puClairotuT

Java Proqramı

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return (top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if (top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
} 
  
  
class Main{ 
    public static void reverse(StringBuffer s){ 
        int n = s.length(); 
        Stack obj = new Stack(n); 
          
        int i; 
        for(i = 0; i < n; i++){ 
            obj.push(s.charAt(i));
        }    
      
        for(i = 0; i < n; i++){  
            char ch = obj.pop(); 
            s.setCharAt(i,ch); 
        } 
    }  
      
    public static void main(String args[]){ 
         
        StringBuffer s= new StringBuffer("TutorialCup"); 
          
        reverse(s); 
          
        System.out.println(s); 
    } 
}
puClairotuT

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n simldəki simvol sayıdır.

Köməkçi məkan: O (n), çünki n işarəni saxlamaq üçün yığında yer istifadə etdik.

Stack istifadə etmədən

Yığından istifadə edərək bir Sətri tərsləşdirmək üçün alqoritm

  1. N uzunluğunda bir simli başlayın.
  2. Sətrin uzunluğunun yarısına qədər keçin və cari indeksdəki simvolu uzunluğu - cari indeks - 1 mövqeyi ilə dəyişdirin.
  3. Sətri çap edin.

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
void swap(char *a, char *b){  
    char temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
void reverse(char s[]){  
      
    int n = strlen(s), i;  
  
    for (i = 0; i < n/2; i++)  
        swap(&s[i], &s[n-i-1]);  
}  
  
int main(){  
    char s[] = "animatedworld";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}
dlrowdetamina

Java Proqramı

class stringRev{ 

    static void swap(char a[], int index1, int index2){ 
        char temp = a[index1]; 
        a[index1] = a[index2]; 
        a[index2] = temp; 
    } 
  
    static void reverse(char s[]){ 
    
        int n = s.length, i; 
  
        for(i = 0; i < n/2; i++) { 
            swap(s, i, n-i-1); 
        } 
    } 
  
    public static void main(String[] args){
        
        char s[] = "animatedworld".toCharArray(); 
  
        reverse(s); 
        System.out.printf(String.valueOf(s)); 
        
    } 
}
dlrowdetamina

Yığın istifadə edərək bir Sətri Ters çevirmək üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (n), burada n simldəki simvol sayıdır.

Köməkçi məkan: O (1), çünki daimi əlavə yerdən istifadə edirik.

References

Translate »