Yalnız hərfləri tərsinə çevirin LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma google microsoftBaxılıb 75

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Yalnız hərfləri tərsinə çevirmək LeetCode Həlli – Sətir verilir s, aşağıdakı qaydalara uyğun olaraq sətri tərsinə çevirin:

  • İngilis hərfləri olmayan bütün simvollar eyni mövqedə qalır.
  • Bütün ingilis hərfləri (kiçik və ya böyük hərf) tərsinə çevrilməlidir.

Qayıtmaq s tərsinə çevirdikdən sonra.Yalnız hərfləri tərsinə çevirin LeetCode HəlliPin

Input: s = "ab-cd"
Output: "dc-ba"

Izahat

-nin personajlarını yazın S bir bir. Hərflə qarşılaşdığımız zaman sətirdən geriyə doğru təkrarlansaq, yaranacaq növbəti hərfi yazmaq istəyirik.

Beləliklə, biz bunu edirik: göstəricini izləyin j ki, simli geriyə doğru iterasiya edir. Məktub yazmaq lazım olanda ondan istifadə edirik.

Əgər yaxından baxsaq, sətri tərsinə çevirməliyik, lakin yalnız hərfləri nəzərə almalıyıq ki, biz iki göstərici saxlaya bilək: biri başlanğıcda, biri sonunda, sonra isə verilmiş şərtə cavab verərsə, başlanğıc və son dəyərlərini dəyişdirməyə davam edin.

Başqa bir yanaşma:

hərflərini toplayın S ayrı-ayrılıqda yığına daxil edin ki, yığını açmaq hərfləri tərsinə çevirsin. (Alternativ olaraq, hərfləri bir massivdə toplayıb massivi tərsinə çevirə bilərdik.)

Sonra personajları yazarkən S, hər hansı bir məktuba ehtiyacımız olduqda, yerinə hazırladığımız məktubu istifadə edirik.

Kodu

Yalnız tərs hərflər üçün C++ kodu

class Solution {
public:
     string reverseOnlyLetters(string S) {
        for (int i = 0, j = S.length() - 1; i < j;) {
            if (!isalpha(S[i]))
                ++i;
            else if (!isalpha(S[j]))
                --j;
            else
                swap(S[i++], S[j--]);
        }
        return S;
    }
};

Yalnız tərs hərflər üçün Java kodu

class Solution {
    public String reverseOnlyLetters(String S) {
        StringBuilder sb = new StringBuilder(S);
        for (int i = 0, j = S.length() - 1; i < j;) {
            if (!Character.isLetter(sb.charAt(i))) {
                ++i;
            } else if (!Character.isLetter(sb.charAt(j))) {
                --j;
            } else {
                sb.setCharAt(i, S.charAt(j));
                sb.setCharAt(j--, S.charAt(i++));
            }
        }
        return sb.toString();
    }
}

Yalnız tərs hərflər üçün Python kodu

class Solution:
    def reverseOnlyLetters(self, S):
        S, i, j = list(S), 0, len(S) - 1
        while i < j:
            if not S[i].isalpha():
                i += 1
            elif not S[j].isalpha():
                j -= 1
            else:
                S[i], S[j] = S[j], S[i]
                i, j = i + 1, j - 1
        return "".join(S)

Yalnız tərs hərflər üçün mürəkkəblik təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O(n/2) -> Tək keçid

Kosmik Mürəkkəblik

O(1) -> yox əlavə yer iki dəyişəndən başqa istifadə olunur

Referans: https://algodaily.com/lessons/using-the-two-pointer-technique

Crack Sistemi Dizayn Müsahibələri
Translate »