Dalam satu langkah, Anda dapat memilih sub-array arr yang tidak kosong dan membalikkannya. Anda diizinkan untuk melakukan sejumlah langkah
Kembalikan True jika Anda dapat membuat arr sama dengan target, atau False jika sebaliknya
Contoh
Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Input: target = [7], arr = [7]
Output: true
Input: target = [1,12], arr = [12,1]
Output: true
Masuk ke mode layar penuh Keluar dari mode layar penuh
Larutan
Karena saya dapat membalikkan subarray sebanyak yang saya butuhkan, ide pertama saya adalah mengurutkan dua array dan membandingkan nilainya
def can_be_equal[target, arr]:
return target == arr or sorted[target] == sorted[arr]
Masuk ke mode layar penuh Keluar dari mode layar penuh
Saya baru saja menambahkan logika sebelum mencoba menyortir. jika mereka memiliki nilai yang sama, kembalikan benar. Jika tidak, urutkan dan bandingkan
Solusi ini adalah O[NlogN] karena algoritma pengurutan memiliki kompleksitas ini
Pendekatan lain adalah menghitung elemen dari setiap larik dalam peta hash. Kuncinya adalah item dan nilainya adalah penghitungnya. Pada akhirnya, jika penghitungnya genap, itu karena kedua array memiliki item yang sama
def can_be_equal[target, arr]:
counter = {}
for index in range[len[target]]:
target_item, arr_item = target[index], arr[index]
if target_item in counter:
counter[target_item] += 1
else:
counter[target_item] = 1
if arr_item in counter:
counter[arr_item] += 1
else:
counter[arr_item] = 1
for _, value in counter.items[]:
if value % 2 != 0:
return False
return True
Masuk ke mode layar penuh Keluar dari mode layar penuh
Di sini kita mengulang melalui array [_______________] dan melalui hashmap [_______________], apakah kompleksitas runtime adalah O[N]. Tapi sekarang kita menggunakan peta, jadi kompleksitas ruangnya adalah O[N] untuk skenario terburuk
Masalah Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution memberi kita dua array. Salah satunya adalah array target dan yang lainnya adalah array input. Menggunakan array input, kita perlu membuat array target. Kita dapat membalikkan salah satu sub-array dalam larik input. Tapi kita tidak bisa mengubah elemen array input. Kita tidak perlu mencari cara untuk melakukan manipulasi. Kembalikan benar jika mungkin jika tidak salah. Nah, seperti biasa sebelum menyelam jauh ke dalam solusi mari kita lihat beberapa contoh
target = [1,2,3,4], arr = [2,4,1,3]
true
Penjelasan. Kita bisa membalikkan sub-array pertama dari indeks 0 ke 2, lalu kita membalikkan sub-array dari 1 ke 2. Pada akhirnya, kami membalik indeks 2 menjadi 3. Dan dengan cara ini, kita bisa membuat array target. Ini bisa lebih dipahami dengan melihat gambar di atas
Daftar isi
Pendekatan untuk Membuat Dua Array Sama dengan Membalik Solusi Leetcode Sub-array
Masalah dapat dengan mudah diselesaikan dengan menggunakan metode penghitungan. Metode penghitungan adalah beberapa algoritma standar. Ini digunakan dalam pengurutan hitungan serta dalam banyak pertanyaan lainnya. jadi di sini kami menghitung elemen dari array target. Kemudian kami melintasi elemen array input. Saat kami menemukan elemen apa pun, kami mengurangi jumlahnya dari frekuensi atau larik hitungan. Jika entah bagaimana selama operasi ini, indeks apa pun memiliki nilai negatif, kami mengembalikan false
Hitungan negatif dalam larik frekuensi menunjukkan larik input memiliki hitungan yang lebih besar untuk suatu elemen. Tetapi bagaimana melakukan ini menyelesaikan masalah? . Setelah Anda mencoba melakukan beberapa pembalikan sub-array. Anda dapat dengan mudah mengetahui bahwa Anda dapat menempatkan elemen apa pun dari larik masukan di tempat mana pun yang Anda inginkan. Jadi, dengan menggunakan aturan ini kita perlu memeriksa apakah elemen dalam larik target sama dengan larik masukan