Write Up — Masalah Coding Harian (14)

Pencakar langit di cakrawala

Selamat datang dengan masalah lain untuk dipecahkan! Hari ini kita berurusan dengan masalah cepat tapi sangat bagus, yang akan melibatkan kota besar, beberapa bangunan, dan matahari terbenam! Seperti biasa, sebelum memulai, dua penafian:

• Masalah-masalah ini disediakan oleh buletin yang luar biasa Masalah Pengodean Harian, yang dapat Anda langgani di sini . Lihat dan coba selesaikan tantanganmu juga!
• Saya bukan pemrogram ahli: hanya seorang pria yang suka membagikan jepretannya! Jika Anda memiliki solusi yang lebih baik atau lebih cepat untuk suatu algoritme, silakan kirimkan di komentar! Saya ingin belajar lebih banyak tentang ini!

Mari kita lihat masalahnya, pertama kali ditanyakan oleh Mailchimp dalam sebuah wawancara kerja:

Anda diberi larik yang mewakili ketinggian bangunan tetangga di jalan kota, dari timur ke barat. Penilai kota ingin Anda menulis algoritme yang mengembalikan berapa banyak dari bangunan ini yang memiliki pemandangan matahari terbenam, untuk menilai jalan dengan benar.

Misalnya, diberikan array [3, 7, 8, 3, 6, 1], Anda harus mengembalikan 3, karena lantai atas bangunan dengan heights 8, 6, dan 1semuanya memiliki pandangan yang tidak terhalang ke barat.

Bisakah Anda melakukan ini hanya dengan menggunakan satu forward pass melalui array?

Mari kita rekap sedikit: kita diberi daftar ketinggian bangunan tetangga dan kita diminta untuk menulis algoritme untuk memeriksa bangunan mana yang memiliki pandangan terbuka ke arah barat.

• Bangunan dalam larik diurutkan sebaliknya: dari timur ke barat. Ini bukan masalah, karena membalik urutan bangunan berarti mengubah sudut pandang kita dan juga membalik timur dan barat. Bayangkan seperti Anda melihat gedung-gedung itu dari jalan dengan arah timur di sebelah kiri Anda. Sekarang Anda pergi ke sudut jalan dan melihat dari belakang. Urutan mereka terbalik dan Anda memiliki timur di kanan Anda! Gambar di bawah ini akan menunjukkan konsep ini kepada Anda. Ini berarti bahwa kami tidak akan membalikkan urutan bangunan dalam daftar: kami hanya menganggap barat berada di sisi kanan susunan dan menulis algoritme kami berdasarkan fakta itu.

• Sebuah bangunan memiliki pandangan terbuka di sebelah kanannya jika tidak ada bangunan yang lebih tinggi di sebelah kanannya. Inilah inti masalahnya dan sebenarnya yang diminta untuk kita hitung.
• Selain itu, kita diminta untuk memberikan solusi menggunakan satu lintasan maju, artinya kita harus mengulang elemen hanya satu kali dan juga mengulang dari kiri ke kanan (ingat ke timur dari barat!). Kami pada dasarnya mempertimbangkan kasus kedua yang ditunjukkan pada gambar di atas.

Solusi ke depan

Inilah kode solusinya, ditulis dengan Python:

Mari kita lihat. Pertama kita mendefinisikan fungsi kita forwardSolutionyang akan menerima array bilangan bulat, yang mewakili ketinggian bangunan kita. Kemudian kita mendefinisikan larik baru, haveSight, yang akan menampung semua bangunan yang benar-benar memiliki pemandangan bebas ke arah barat. Kami menempatkan gedung pertama dalam daftar ke dalamnya, untuk memiliki sesuatu untuk memulai perbandingan.

Setelah itu lewati semua bangunan lain, tidak termasuk yang pertama yang sudah ada dalam daftar. Kami sekarang mendefinisikan tiga kasus: mari kita gambarkan, mulai dari yang paling sederhana.

• Pada baris 7, kita memeriksa apakah gedung saat ini yang ditinjau oleh loop blebih tinggi dari gedung terakhir dalam daftar baru . Jika ya, itu berarti menutupi pandangan yang itu, jadi kami menghapusnya dari daftar dan memperbarui elemen terakhir dari daftar dengan b. Kami melakukan ini dengan memanggil haveSight[-1] = b.
• Pada baris 10, kami mengelola kasus yang btidak lebih tinggi dari haveSight[-1]. Ini berarti bmemiliki pandangan bebas (kecuali jika ditutupi oleh b+1, tetapi dalam hal ini akan dikelola oleh baris 7) dan tidak mencakup pandangan haveSight[-1]. Jadi kami hanya menambahkannya ke daftar.

• Bayangkan kasus ini: [7,6,8]. Ini tidak dapat diatur oleh dua poin terakhir dari fungsi, karena pada baris 7 angka 6 akan dihapus dan diganti dengan 8, tetapi angka 8 juga menutupi tampilan angka 7 yang masih ada dalam daftar. Kita perlu mengelola kasus di mana sebuah bangunan mencakup semua yang lain dalam daftar . Karena kita tahu bahwa yang tertinggi akan selalu ada haveSight[0]. Jadi, jika b >= haveSight[0]kita perlu menghapus semuanya dari daftar dan memulai lagi dari b, yang merupakan bangunan tertinggi yang baru. Setelah itu kami menelepon continuekarena kami dapat melewati dua pemeriksaan lainnya.

Kompleksitas waktu

Terlepas dari penjelasannya yang panjang, algoritma ini memiliki analisis kompleksitas waktu yang sangat sederhana. Hanya ada for loop, yang mengulang daftar yang diberikan oleh masalah mulai dari elemen kedua, kita dapat dengan mudah mengatakan bahwa kompleksitas waktu di sini adalah O(n-1) = O(n), di mana n adalah panjang dari daftar awal.

Kesalahan

Saya harus mengakuinya: solusi di atas agak curang, karena fakta kecil ini: apa yang terjadi jika dua bangunan tetangga memiliki ketinggian yang sama? Jika kami mempertimbangkan fakta bahwa dua bangunan tetangga dengan ketinggian yang sama memiliki pandangan bebas, algoritme berlaku, tetapi Jika kami berpikir bahwa satu menghalangi pandangan yang lain, solusi ini tidak berfungsi. Juga menambahkan >=tanda pada baris 4 dan 7 menyebabkan hasil yang aneh. Berikut dua contoh:

>>> print(forwardSolution([3, 7, 8, 3, 6, 6, 1]))
[8, 6, 6, 1]

>>> print(forwardSolution([3, 7, 6, 8, 6, 3, 6, 1]))
[8, 6, 6, 1]

Solusi mundur

Namun menurut pendapat saya, ada solusi yang lebih sederhana dan lebih cepat yang ingin saya tunjukkan kepada Anda, solusi yang melibatkan pengulangan daftar ke belakang. Ini kode sederhananya.

Pada dasarnya, karena kita tahu bahwa elemen terakhir akan selalu terlihat bebas, kita menambahkannya terlebih dahulu ke dalam daftar. Kemudian kita mengulang mundur dan membandingkan bdengan elemen pertama dari array, yang akan selalu menjadi yang tertinggi. Maka jika blebih tinggi dari haveSight[0], itu berarti yang btertinggi baru dan juga di sebelah kiri haveSight[0]. Jadi kami memperbarui daftar dengan memasukkanb indeks pertama dari daftar. Kami cukup mengembalikan daftar di bagian akhir.

Berbicara tentang kompleksitas waktu, ini juga memiliki tc O(n), karena dibatasi oleh panjang array asli.

Ini dia, kita berhasil sampai akhir. Seperti biasa, terima kasih telah membaca sampai akhir: kali ini panjang dan menyakitkan! Inilah pemandangan matahari terbenam kota yang indah sebagai hadiah atas kesabaran!

Jika Anda menyukai artikel ini dan menganggapnya berharga, silakan beri tepuk tangan atau bagikan dengan seseorang yang mungkin tertarik dengannya!

Seperti biasa, terima kasih telah membaca.

Nicola