Beralih Huruf II

Mary-Kate Olsen
Lepaskan: 2025-01-05 22:30:39
asal
268 orang telah melayarinya

Shifting Letters 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] = [mulai, tamati, arahi]. Untuk setiap i, anjakan aksara dalam s daripada indeks bermulai ke hujung indeksi (inklusif) ke hadapan jika arahi = 1, atau alihkan aksara ke belakang jika arahi = 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 * 104
  • anjakan[i].panjang == 3
  • 0 <= mulai <= tamati < s.panjang
  • 0 <= arahi <= 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:

  1. 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.
  2. Selepas memproses semua anjakan, kami menggunakan jumlah awalan pada tatasusunan anjakan untuk mendapatkan anjakan kumulatif pada setiap indeks.
  3. Akhir sekali, kami menggunakan anjakan kumulatif pada setiap aksara dalam rentetan.

Penjelasan Kod:

  1. Penghuraian Input: Kami menukar rentetan input s kepada susunan aksara untuk manipulasi yang lebih mudah.
  2. 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.
  3. Jumlah Awalan: Kami mengira jumlah anjakan untuk setiap aksara dengan mengulangi tatasusunan anjakan dan mengekalkan jumlah terkumpul anjakan.
  4. 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.
  5. 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!

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan