Beralih Huruf II

2381. Beralih Huruf II

Kesukaran: Sederhana

Topik: Tatasusunan, Rentetan, Jumlah Awalan

Anda diberi rentetan s huruf Inggeris huruf kecil dan tatasusunan integer 2D beralih di mana anjakan[i] = [mula_i, tamat_i, arah_i]. Untuk setiap i, anjakan aksara dalam s daripada indeks bermula_i ke hujung indeks_i (inklusif) ke hadapan jika arah_i = 1, atau alihkan aksara ke belakang jika arah_i = 0.

Menukar aksara ke hadapan bermaksud menggantikannya dengan huruf seterusnya dalam abjad (membalut supaya 'z' menjadi 'a'). Begitu juga, mengalihkan aksara ke belakang bermaksud menggantikannya dengan huruf sebelumnya dalam abjad (membalut supaya 'a' menjadi 'z').

Kembalikan rentetan akhir selepas semua peralihan kepada s digunakan.

Contoh 1:

• Input: s = "abc", anjakan = [[0,1,0],[1,2,1],[0,2,1]]
• Output: "ace"
• Penjelasan: Mula-mula, alihkan aksara daripada indeks 0 kepada indeks 1 ke belakang. Sekarang s = "zac".
  • Kedua, alihkan aksara daripada indeks 1 kepada indeks 2 ke hadapan. Sekarang s = "zbd".
  • Akhir sekali, alihkan aksara daripada indeks 0 kepada indeks 2 ke hadapan. Sekarang s = "ace".

Contoh 2:

• Input: s = "dztz", anjakan = [[0,0,0],[1,1,1]]
• Output: "catz"
• Penjelasan: Mula-mula, alihkan aksara daripada indeks 0 kepada indeks 0 ke belakang. Sekarang s = "cztz".
  • Akhir sekali, alihkan aksara daripada indeks 1 kepada indeks 1 ke hadapan. Sekarang s = "catz".

Kekangan:

• 1 <= s.length, shifts.length <= 5 * 10⁴
• anjakan[i].panjang == 3
• 0 <= mula_i <= tamat_i < s.panjang
• 0 <= arah_i <= 1
• s terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Daripada mengalihkan setiap watak dalam setiap syif, bolehkah anda menjejaki watak yang dialihkan dan berapa banyak merentas semua syif?
2. Cuba tandakan permulaan dan tamat setiap syif, kemudian lakukan jumlah awalan syif.

Penyelesaian:

Kita perlu mengelak daripada menukar aksara satu demi satu untuk setiap syif, kerana ini akan menjadi terlalu perlahan untuk input yang besar. Sebaliknya, kita boleh menggunakan pendekatan yang lebih optimum dengan memanfaatkan teknik yang dipanggil jumlah awalan.

Langkah-langkah:

1. Tandai sempadan anjakan: Daripada mengalihkan setiap aksara serta-merta, kami menandakan kesan anjakan pada permulaan dan penghujung setiap julat.
2. Gunakan jumlah awalan: Selepas menandakan semua anjakan, kita boleh mengira anjakan kumulatif pada setiap aksara menggunakan teknik jumlah awalan. Ini membolehkan kami menggunakan anjakan kumulatif dengan cekap pada setiap aksara.
3. Lakukan anjakan: Setelah kita mengetahui jumlah anjakan untuk setiap aksara, kita boleh menggunakan anjakan (sama ada ke hadapan atau ke belakang) pada rentetan.

Mari laksanakan penyelesaian ini dalam PHP: 2381. Beralih Huruf II

  
  
  Penjelasan:



Untuk setiap anjakan [mula, tamat, arah], kami akan menambah tatasusunan anjakan pada permulaan dan susut pada penghujung 1. Ini membolehkan kami menjejaki permulaan dan penghujung julat anjakan.
Selepas memproses semua anjakan, kami menggunakan jumlah awalan pada tatasusunan anjakan untuk mendapatkan anjakan kumulatif pada setiap indeks.
Akhir sekali, kami menggunakan anjakan kumulatif pada setiap aksara dalam rentetan.



  
  
  Penjelasan Kod:




Penghuraian Input: Kami menukar rentetan input s kepada susunan aksara untuk manipulasi yang lebih mudah.

Shift Array: Kami memulakan tatasusunan anjakan saiz n 1 kepada sifar. Tatasusunan ini digunakan untuk menjejaki kesan anjakan. Untuk setiap anjakan [mula, tamat, arah], kami melaraskan nilai pada anjakan[mula] dan anjakan[akhir 1] untuk mencerminkan permulaan dan akhir anjakan.

Jumlah Awalan: Kami mengira jumlah anjakan untuk setiap aksara dengan mengulangi tatasusunan anjakan dan mengekalkan jumlah terkumpul anjakan.

Peralihan Aksara: Untuk setiap aksara dalam rentetan, kami mengira aksara teranjak terakhir menggunakan formula (ord(currentChar) - ord('a') totalShift) % 26, yang merangkumi sifat bulat bagi abjad.

Keputusan Pengembalian: Rentetan akhir diperoleh dengan menukar tatasusunan aksara kembali menjadi rentetan dan mengembalikannya.



  
  
  Kerumitan Masa:




Kerumitan masa: O(n m), dengan n ialah panjang rentetan s dan m ialah bilangan anjakan. Ini kerana kami mengulangi rentetan dan senarai anjakan sekali setiap satu.

Kerumitan ruang: O(n), dengan n ialah panjang rentetan s, disebabkan ruang yang diperlukan untuk tatasusunan anjakan.


Penyelesaian ini menangani masalah dengan cekap walaupun dengan had atas kekangan input.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Beralih Huruf II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!