Լարային կոդերի լուծման հակադարձ ձայնավորներ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon facebook Google
String Երկու ցուցիչ

Խնդիրի հայտարարություն

Այս խնդրում ա լարային տրված է, և մենք պետք է հետ շուռ տանք այս լարի միայն ձայնավորները:

Օրինակ

"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

Լարային ծածկագիր լուծույթի հակադարձ ձայնավորների բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ): Մենք լարն անցանք ընդամենը երկու անգամ: Դաշտի վրա մղել և փոփ գործելակերպը տևում է անընդհատ ժամանակ, և ձայնավորների հավաքածուն ունի ընդամենը 10 տարր (այսինքն `բնույթ գտնելու համար անհրաժեշտ կլինի անընդհատ ժամանակ), ուստի ժամանակի բարդությունը O է (N):

Տիեզերական բարդություն 

ՎՐԱ): Ամենավատ դեպքերում stack- ը կարող է ունենալ մուտքային տողի բոլոր նիշերը: Ուստի տարածության բարդությունը 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

Լարային ծածկագիր լուծույթի հակադարձ ձայնավորների բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ): Լարի յուրաքանչյուր նիշ այցելվում է միայն մեկ անգամ, ուստի ժամանակի բարդությունը O (N) է:

Տիեզերական բարդություն 

O (1): Ոչ մի լրացուցիչ տարածք չի օգտագործվում, բացառությամբ ձայնավորների հավաքածուի, որն ունի ընդամենը 10 տարր (այսինքն ՝ անընդհատ տարածություն): Ուստի տարածության բարդությունը O է (1):