Обратни самогласки на решетка за низа код


Ниво на тешкотија Лесно
Често прашувано во Амазон Facebook Google
Стринг Два покажувачи

Изјава за проблем

Во овој проблем a низа е даден и ние треба да ги свртиме само самогласките од оваа низа.

пример

"hello"
"holle"

објаснување:
пред да свртиме назад: „жello"
по пресврт: „жolle"

"leetcode"
"leotcede"

објаснување:
Обратни самогласки на решетка за низа код

Пристап 1 (Користење Магацинот)

Треба само да ги свртиме самогласките присутни во влезната низа. Така, можеме да ги зачуваме сите самогласки во магацинот во истиот редослед од лево надесно. Потоа повторно можеме да ја пресечеме низата и за секој карактер на самогласка од лево надесно ќе ја замениме со најголемата вредност на оџакот.

Алгоритам

  • Чувајте ги сите карактери на самогласка во сет.
  • Создадете оџак и турнете ги сите самогласки карактери присутни во влезната низа од лево надесно.
  • Сега повторно поминете низ низата за секој карактер. Ако тековниот карактер е самогласка, заменете го со највисокиот карактер на оџакот (десниот самогласен карактер на влезната низа) и извадете го од оџакот.
  • Вратете ја конвертираната низа.

Имплементација за обратни самогласки на решетка за низа код

Програма C ++

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};
    stack<char> stack;
    for(char c:s)
    {
        if(vowels.count(c)) stack.push(c);
    }

    for(char& c:s)
    {
        if(vowels.count(c)) 
        {
            c=stack.top();
            stack.pop();
        }
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

Програма за Java

import java.util.*;

class Rextester
{ 
    public static String reverseVowels(String s) {

        char[] arr= s.toCharArray();

        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');

        Stack<Character> stack=new Stack<Character>();

        for(char c:arr)
        {
            if(vowels.contains(c)) stack.push(c);
        }

        for(int i=0;i<arr.length;i++)
        {
            if(vowels.contains(arr[i])) 
            {
                arr[i]=stack.pop();
            }
        }

        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

Анализа на сложеност за обратни самогласки на решетка за низа код

Временска комплексност

НА): Ја поминавме низата само два пати. Исто така, притискањето и поп-операцијата на оџакот траат постојано време и множеството самогласки има само 10 елементи (т.е. ќе биде потребно постојано време за наоѓање на карактер), затоа, сложеноста на времето е О (Н).

Комплексноста на просторот 

НА): Во најлош случај, оџакот може да ги има сите карактери на влезната низа. Оттука, комплексноста на просторот е O (N).

Пристап 2 (единечно додавање со користење на две покажувачи)

Ние исто така можеме да ги свртиме самогласките во единечен премин користејќи два покажувачи со следење на алгоритам:

  • Создадете две променливи Почеток крајот за укажување на самогласките соодветно од лево и од десно.
  • Иницијализира како Почеток= 0 и крајот= должина (стринг) -1.
  • Сега извршете јамка додека започнете.
  • Внатре во оваа јамка извршете две јамки за движење на овие две покажувачи да започнат и да завршат од лево надесно и десно одлево, соодветно, така што тие ќе покажат на следната самогласка.
  • Разменете ги двата самогласки карактери посочени со почеток и крај.
  • Зголеми Почеток и намалување крајот од 1.
  • Вратете ја новата низа кога Почеток станува поголема крајот.

Имплементација за обратни самогласки на решетка за низа код

Програма C ++

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};

    int start=0,end=s.length()-1;
    while(start<end)
    {
        while(start<end && !vowels.count(s[start])) start++;

        while(start<end && !vowels.count(s[end])) end--;

        char temp=s[start];
        s[start]=s[end];
        s[end]=temp;

        start++;
        end--;
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

Програма за Java

import java.util.*;

class Rextester
{ 
    public static String reverseVowels(String s) {

       char[] arr= s.toCharArray();
        
        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');
        
       int start=0,end=arr.length-1;
        while(start<end)
        {
            while(start<end && !vowels.contains(arr[start])) start++;
            
            while(start<end && !vowels.contains(arr[end])) end--;
            
            char temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            
            start++;
            end--;
        }
        
        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

Анализа на сложеност за обратни самогласки на решетка за низа код

Временска комплексност

НА): Секој карактер на стрингот се посетува само еднаш, затоа, временската сложеност е O (N).

Комплексноста на просторот 

О (1): Не се користи дополнителен простор освен множество самогласки што имаат само 10 елементи (т.е. постојан простор). Оттука, комплексноста на просторот е О (1).