Садоноки баръакси ҳалли Leetcode сатр


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Facebook Google
сатр Ду ишора

Изҳороти мушкилот

Дар ин масъала а данд дода мешавад ва мо бояд танҳо садонокҳои ин сатрро баргардонем.

мисол

"hello"
"holle"

Шарҳ:
пеш аз бозгашт: “hello"
пас аз бозгашт: “holle"

"leetcode"
"leotcede"

Шарҳ:
Садоноки баръакси ҳалли Leetcode сатр

Муносибати 1 (Истифода тӯда)

Мо танҳо бояд садонокҳои дар сатри вуруд мавҷудбударо баргардонем. Ҳамин тавр, мо метавонем ҳамаи садонокҳоро дар стек бо ҳамон тартиб аз чап ба рост нигоҳ дорем. Он гоҳ бори дигар мо метавонем сатрро убур кунем ва барои ҳар як аломати садонок аз чап ба рост онро бо арзиши болоии стака иваз намоем.

Алгоритм

  • Ҳама аломатҳои садонокро дар маҷмӯъ нигоҳ доред.
  • Стек эҷод кунед ва ҳамаи аломатҳои садоноки дар сатри вуруд мавҷудбударо аз чап ба рост пахш кунед.
  • Акнун боз барои ҳар як аломат сатрро убур кунед. Агар аломати ҷорӣ садонок бошад, онро бо аломати болоии стак (аломати рости сатри вуруд) иваз кунед ва аз стек хориҷ кунед.
  • Сатри табдилёфтаро баргардонед.

Татбиқи садонокҳои баръакси ҳалли сатри Leetcode

Барномаи 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

Таҳлили мураккабӣ барои садонокҳои баръакси ҳалли Leetcode сатр

Мураккабии вақт

О (Н): Мо сатрро танҳо ду бор убур кардем. Амалиёти пушту поп дар стек вақти доимиро мегирад ва маҷмӯи садонокҳо танҳо 10 элемент дорад (яъне барои ёфтани аломат вақти доимӣ лозим аст), аз ин рӯ мураккабии вақт O (N) мебошад.

Мураккабии фазо 

О (Н): Дар бадтарин стак метавонад ҳамаи аломатҳои сатри вуруд дошта бошад. Аз ин рӯ, мураккабии фазо O (N) мебошад.

Муносибати 2 (Як гузариш бо истифодаи ду нишондиҳанда)

Мо инчунин метавонем садонокҳоро дар гузаргоҳи ягона бо истифодаи ду нишоннамо бо алгоритми зерин баргардонем:

  • Ду тағирёбанда созед Таърихи оѓоз ва Поён барои ишора ба садонокҳо мутаносибан аз чап ва рост.
  • Оғоз ҳамчун Таърихи оѓоз= 0 ва Поён= дарозӣ (сатр) -1.
  • Ҳоло давраеро иҷро кунед оғоз.
  • Дар дохили ин ҳалқа ду ҳалқа барои ҳаракат кардани ин ду нишондиҳанда мутаносибан аз чап ба рост ва рост ба чап ба итмом мерасанд, то онҳо ба садоноки навбатӣ ишора кунанд.
  • Ду аломати садонокро, ки бо оғоз ва хотима ишора шудаанд, иваз кунед.
  • Афзоиш Таърихи оѓоз ва кам Поён аз ҷониби 1.
  • Сатри навро ҳангоми бозгаштан Таърихи оѓоз бузургтар мешавад охири.

Татбиқи садонокҳои баръакси ҳалли сатри Leetcode

Барномаи 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

Таҳлили мураккабӣ барои садонокҳои баръакси ҳалли Leetcode сатр

Мураккабии вақт

О (Н): Ҳар як аломати сатр танҳо як маротиба ташриф оварда мешавад, аз ин рӯ мураккабии вақт O (N) мебошад.

Мураккабии фазо 

О (1): Ғайр аз маҷмӯи садонокҳо, ки ҳамагӣ 10 унсур доранд (яъне фазои доимӣ), ҳеҷ фазои иловагӣ истифода намешавад. Аз ин рӯ, мураккабии фазо O (1) мебошад.