Dalam wawancara algoritma, pewawancara selalu suka membuat artikel di sekitar daftar tertaut, penyortiran, pohon biner, dan pencarian biner, dan kebanyakan orang dapat mengikuti buku profesional untuk menghafalnya. Pewawancara tidak ingin merekrut programmer dengan keterampilan memori yang baik tetapi tidak dapat belajar dan menerapkannya. Oleh karena itu, sangat penting untuk belajar memodelkan dan menganalisis masalah secara matematis dan menggunakan algoritma atau struktur data yang masuk akal untuk menyelesaikan masalah.
Pertanyaan Wawancara: Cetak jumlah minimum array yang berputar
Judul: Pindahkan beberapa elemen pertama dari array ke akhir array, yang kami sebut rotasi array. Masukkan rotasi array yang diurutkan secara bertahap dan output elemen minimum dari array rotasi. Misalnya, array {3, 4, 5, 1, 2} adalah rotasi array {1, 2, 3, 4, 5}, dan nilai minimum array adalah 1.
Untuk mencapai persyaratan ini, kita hanya perlu melintasi array, menemukan nilai terkecil dan keluar secara langsung. Implementasi kode adalah sebagai berikut:
test kelas publik08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {lempar runtimeException baru ("kesalahan input!"); } int result = nums [0]; untuk (int i = 0; i <nums.length - 1; i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1]; merusak; }} hasil pengembalian; } public static void main (string [] args) {// input khas, rotasi array ascending monotonic int [] array1 = {3, 4, 5, 1, 2}; System.out.println (GetThemin (Array1)); // Ada angka duplikat, dan angka terkecil yang hanya bilangan terkecil int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (GetThemin (Array2)); // Ada angka duplikat, tetapi angka duplikat bukan angka pertama dan terakhir int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (GetThemin (Array3)); // Ada angka duplikat, dan angka duplikat adalah angka pertama dan terakhir int [] array4 = {1, 0, 1, 1, 1}; System.out.println (GetThemin (Array4)); // array naik monoton, putar 0 elemen, yaitu, array naik monoton itu sendiri int [] array5 = {1, 2, 3, 4, 5}; System.out.println (GetThemin (Array5)); // Hanya ada satu angka di array int [] array6 = {2}; System.out.println (GetThemin (Array6)); // Angka -angka dalam array adalah int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (GetThemin (Array7)); }}Tidak ada yang salah dengan hasil pencetakan. Namun, metode ini jelas bukan yang terbaik. Mari kita lihat apakah ada cara untuk menemukan metode yang lebih baik untuk menghadapinya.
Tertib, masih perlu mencari?
Ketika kami menemukan dua kata kunci ini, kami pasti akan memikirkan metode pencarian biner kami, tetapi banyak teman pasti akan meminta bahwa array kami tidak lagi merupakan array yang benar -benar dipesan setelah diputar, tetapi itu seperti kombinasi dua array tambahan. Kita bisa berpikir seperti ini.
Kita dapat mengatur dua subskrip rendah dan tinggi, dan mengatur mid = (rendah + tinggi)/2, dan kita secara alami dapat menemukan array elemen [mid] di tengah array. Jika elemen tengah berada dalam array tambahan di depan, maka itu harus lebih besar dari atau sama dengan elemen yang sesuai dari subskrip rendah. Pada saat ini, elemen terkecil dalam array harus berada di belakang elemen. Kita dapat mengarahkan subskrip rendah ke elemen menengah, yang dapat mempersempit kisaran pencarian.
Demikian pula, jika elemen perantara terletak di subarray tambahan berikutnya, itu harus kurang dari atau sama dengan elemen yang sesuai dengan subskrip tinggi. Pada saat ini elemen terkecil dalam array harus berada di depan elemen perantara. Kami dapat memperbarui subskrip tinggi ke median subscript, yang juga dapat mempersempit kisaran pencarian. Elemen yang sesuai dengan subskrip tinggi setelah bergerak masih di subarray tambahan berikutnya.
Apakah itu memperbarui rendah atau tinggi, rentang pencarian kami akan dikurangi menjadi setengah dari yang asli. Selanjutnya, kami akan menggunakan subskrip yang diperbarui untuk mengulangi putaran pencarian baru. Sampai dua subskrip terakhir berdekatan, yaitu kondisi akhir loop kami.
Saya telah mengatakan banyak, dan sepertinya saya telah berantakan. Kami mungkin juga menggunakan input dalam pertanyaan untuk mensimulasikan dan memverifikasi algoritma kami.
Mari kita lihat bagaimana mengimplementasikan ide ini di Java menggunakan kode:
test kelas publik08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {lempar runtimeException baru ("kesalahan input!"); } // Jika hanya ada satu elemen, langsung kembalikan if (nums.length == 1) return nums [0]; hasil int = num [0]; int low = 0, tinggi = nums.length - 1; int mid; // Pastikan nilai yang sesuai dengan subskrip rendah berada di subarray kenaikan di sebelah kiri, dan nilainya yang sesuai dengan tinggi berada di subarray kenaikan di sebelah kanan sementara (nums [rendah]> = num [tinggi]) {// Pastikan akhir kondisi loop jika (tinggi - rendah == 1) {return nums [tinggi]; } // Ambil posisi tengah mid = (rendah + tinggi) / 2; // menunjukkan bahwa elemen tengah bertambah di sebelah kiri if (nums [mid]> = nums [low]) {low = mid; } else {high = mid; }} hasil pengembalian; } public static void main (string [] args) {// input khas, rotasi array ascending monotonic int [] array1 = {3, 4, 5, 1, 2}; System.out.println (GetThemin (Array1)); // Ada angka duplikat dan angka terkecil yang hanya mengulangi angka adalah int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (GetThemin (Array2)); // Ada angka duplikat, tetapi angka duplikat bukan angka pertama dan terakhir int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (GetThemin (Array3)); // Ada angka duplikat, dan angka duplikat adalah angka pertama dan terakhir int [] array4 = {1, 0, 1, 1, 1}; System.out.println (GetThemin (Array4)); // array naik monoton, putar 0 elemen, yaitu, array naik monoton itu sendiri int [] array5 = {1, 2, 3, 4, 5}; System.out.println (GetThemin (Array5)); // Hanya ada satu angka di array int [] array6 = {2}; System.out.println (GetThemin (Array6)); // Angka -angka dalam array adalah int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (GetThemin (Array7)); // Khusus Saya tidak tahu cara memindahkan int [] array8 = {1, 0, 1, 1, 1}; System.out.println (GetThemin (Array8)); }}Kami menyebutkan sebelumnya bahwa dalam array yang berputar, karena beberapa angka dalam array yang diurutkan secara bertahap dipindahkan di belakang array, angka pertama selalu lebih besar dari atau sama dengan angka terakhir, dan ada kasus khusus lain bahwa 0 elemen dipindahkan, yaitu, array itu sendiri juga merupakan array yang berputar sendiri. Situasi ini sendiri diperintahkan, jadi kita hanya perlu mengembalikan elemen pertama, itulah sebabnya saya menetapkan hasilnya ke angka [0] terlebih dahulu.
Apakah kode di atas sempurna? Kami tidak memenuhi persyaratan kami melalui kasus uji. Mari kita lihat input array8 secara detail. Pertama -tama mari kita analisis operasi komputer:
Tetapi kita dapat melihat sekilas bahwa nilai minimum kita bukan 1, tetapi 0, jadi ketika array [rendah], array [mid], dan array [tinggi] sama, program kami tidak tahu cara bergerak. Menurut metode pergerakan saat ini, array [mid] bertambah di sebelah kiri secara default. Ini jelas tidak bertanggung jawab.
Mari kita perbaiki kode:
test kelas publik08 {public static int getthemin (int nums []) {if (nums == null || nums.length == 0) {lempar runtimeException baru ("kesalahan input!"); } // Jika hanya ada satu elemen, langsung kembalikan if (nums.length == 1) return nums [0]; hasil int = num [0]; int low = 0, tinggi = nums.length - 1; int mid = rendah; // Pastikan nilai yang sesuai dengan subskrip rendah berada di subarray kenaikan di sebelah kiri, dan nilainya yang sesuai dengan tinggi berada di subarray kenaikan di sebelah kanan sementara (nums [rendah]> = num [tinggi]) {// Pastikan akhir kondisi loop jika (tinggi - rendah == 1) {return nums [tinggi]; } // Ambil posisi tengah mid = (rendah + tinggi) / 2; // Dalam kasus khusus di mana ketiga nilai tersebut sama, Anda perlu menemukan nilai terkecil dari awal hingga akhir jika (num [mid] == num [rendah] && num [mid] == num [tinggi]) {return midinorder (nums, rendah, tinggi); } // menunjukkan bahwa elemen tengah bertambah di sebelah kiri if (nums [mid]> = nums [low]) {low = mid; } else {high = mid; }} hasil pengembalian; } / *** Temukan nilai minimum dalam array** @param nums array* @param Mulai Posisi mulai* @param end array posisi akhir* @return angka terkecil yang ditemukan* / public static int midinorder (int [] nums, int start, int end) {int result = nums [start]; untuk (int i = start+1; i <= end; i ++) {if (hasil> num [i]) hasil = num [i]; } hasil pengembalian; } public static void main (string [] args) {// input khas, rotasi array ascending monotonic int [] array1 = {3, 4, 5, 1, 2}; System.out.println (GetThemin (Array1)); // Ada angka duplikat dan angka terkecil yang kebetulan merupakan angka paling umum int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (GetThemin (Array2)); // Ada angka duplikat, tetapi angka duplikat bukan angka pertama dan terakhir int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (GetThemin (Array3)); // Ada angka duplikat, dan angka duplikat adalah persis angka pertama dan terakhir int [] array4 = {1, 0, 1, 1, 1}; System.out.println (GetThemin (Array4)); // array naik monoton, putar 0 elemen, yaitu, array naik monoton itu sendiri int [] array5 = {1, 2, 3, 4, 5}; System.out.println (GetThemin (Array5)); // Hanya ada satu angka di array int [] array6 = {2}; System.out.println (GetThemin (Array6)); // semua angka dalam array adalah int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (GetThemin (Array7)); // Khusus Saya tidak tahu cara memindahkan int [] array8 = {1, 0, 1, 1, 1}; System.out.println (GetThemin (Array8)); }}Kami kemudian memasukkannya dengan kasus uji lengkap dan lulus tes.
Meringkaskan
Faktanya, pertanyaan ini memiliki banyak poin untuk diperiksa, tetapi sebenarnya untuk memeriksa aplikasi fleksibel pencarian biner. Banyak teman harus mengikuti secara tertib menghafal pencarian biner tanpa mempelajari gagasan pencarian biner, yang hanya akan mengarah pada pemikiran tentang nilai minimum pencarian melingkar.
Banyak teman membuat pernyataan selama wawancara bahwa ekosistem asli Android pada dasarnya merangkum algoritma umum dan memprotes algoritma yang tidak efektif ini dalam wawancara. Ini sebenarnya cukup bodoh. Kami tidak berusaha menerapkan algoritma hafalan, tetapi kami berusaha mempelajari ide -ide cerdas di dalamnya. Hanya dengan terus meningkatkan kemampuan berpikir seseorang dapat membantu seseorang mendapatkan pengembangan karir yang lebih baik.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.