Bir simli Leetcode həllinin əks saitləri

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Facebook google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Sim İki işarəBaxılıb 40

Problem bəyanat

Bu problemdə a sim verilmişdir və bu sətrin yalnız saitlərini tərs çevirməliyik.

misal

"hello"
"holle"

Explanation:
geri dönmədən əvvəl: “hello"
geri döndükdən sonra: “holle"

"leetcode"
"leotcede"

Explanation:
Bir simli Leetcode həllinin əks saitləri

Yanaşma 1 (istifadə olunur Qalaq)

Yalnız giriş sətrində mövcud olan saitləri tərs çevirməliyik. Beləliklə, bütün saitləri bir yığında soldan sağa eyni qaydada saxlaya bilərik. Sonra yenə də simdən keçə bilərik və hər sait xarakter üçün soldan sağa yığının ən üst qiyməti ilə əvəz edəcəyik.

Alqoritm

  • Bütün sait simvollarını bir dəstdə saxlayın.
  • Bir yığın yaradın və giriş simlindəki bütün sait simvolları soldan sağa itələyin.
  • İndi hər bir simvol üçün yenidən simli keçin. Əgər cari xarakter saitdirsə, onu yığının ən üst işarəsi ilə əvəz edin (giriş sətrinin ən sağ səsi xarakteri) və yığından çıxarın.
  • Dönüştürülmüş sətri qaytarın.

Bir Simli Leetcode həllinin tərs saitləri üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Bir Simli Leetcode həllinin tərs saitləri üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (N): Simdən cəmi iki dəfə keçdik. Yığındakı push və pop əməliyyatı daim vaxt tələb edir və saitlər cəmi 10 elementdən ibarətdir (yəni bir simvol tapmaq üçün daimi vaxt tələb olunur), buna görə zaman mürəkkəbliyi O (N) -dir.

Kosmik Mürəkkəblik 

O (N): Ən pis yığında giriş sətrinin bütün simvolları ola bilər. Beləliklə kosmik mürəkkəblik O (N) -dir.

Yanaşma 2 (İki göstəricidən istifadə edərək tək keçid)

Aşağıdakı alqoritmlə iki göstəricidən istifadə edərək saitləri tək keçiddə geri çevirə bilərik:

  • İki dəyişən yaradın Başlamaqson sırasıyla soldan və sağdan saitlərə işarə üçün.
  • Kimi başlayın Başlamaq= 0 və son= uzunluq (simli) -1.
  • İndi bir müddət çalıştırın başlamaq.
  • Bu döngənin içərisində, bu iki göstəricinin başlanğıc və bitişini sıradan soldan sağa və sağdan sola hərəkət etdirmək üçün növbəti səsi göstərməsi üçün iki döngə işlədin.
  • Başlanğıc və son ilə göstərilən iki sait simvolunu dəyişdirin.
  • Artırmaq Başlamaq və azalma son 1 tərəfindən.
  • Zaman yeni simli qaytarın Başlamaq daha böyük olur son.

Bir Simli Leetcode həllinin tərs saitləri üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Bir Simli Leetcode həllinin tərs saitləri üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (N): Sətrin hər bir simvolu yalnız bir dəfə ziyarət olunur, buna görə zamanın mürəkkəbliyi O (N) -dir.

Kosmik Mürəkkəblik 

O (1): Yalnız 10 elementdən ibarət olan sait dəsti xaricində əlavə boşluq istifadə olunmur (yəni daimi boşluq). Beləliklə kosmik mürəkkəblik O (1) -dir.

Şərh yaz

Translate »
1