


Interview de Meituan : S'il vous plaît, écrivez à la main un programme rapide, j'ai été choqué !
Aujourd'hui, l'intervieweur m'a demandé d'écrire un tri rapide sur place. La scène est la suivante :
Intervieweur : Continuons à parler de structures de données et d'algorithmes. (Tout en parlant, il a retourné mon CV et m'a tendu un stylo, ce qui signifie qu'il m'a demandé d'écrire au dos de mon CV)
Rookie moi : Que veux-tu dire ? L'écrire ici ? (Montrant le CV)
Intervieweur : Ouais
Moi recrue : Non
Intervieweur : D'accord, c'est tout pour l'interview d'aujourd'hui
Moi recrue : (Je suis très en colère, je veux le mettre sur mon plan de gestion du travail reprendre Écrire du code ? ) Shadiao
Intervieweur : (Avec le recul, confus)
Pensez-y, je suis encore trop jeune, ce ne serait pas comme ça maintenant. Écrivez simplement, ce n’est qu’un morceau de papier de toute façon.
En fait, bien que la file d'attente rapide soit simple, je suppose que beaucoup de gens ne peuvent pas l'écrire à la main. Est-ce difficile ? Il y a beaucoup de gens qui peuvent l'écrire à la main sur place de plusieurs manières.
Je suis un débutant, mais je peux encore écrire à la main. Après tout, avant l'entretien, j'ai juste délibérément préparé "Écriture rapide par dictée".
Maintenant, analysons et analysons ---- tri rapide.
Contexte
De l'Encyclopédie :
Le tri rapide a été proposé par C. A. R. Hoare en 1962. Son idée de base est de diviser les données à trier en deux parties indépendantes via un tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis d'utiliser cette méthode pour séparer rapidement les deux parties des données. . Tri, l'ensemble du processus de tri peut être effectué [de manière récursive], de sorte que l'ensemble des données devienne une séquence ordonnée.
C’est assez difficile de comprendre ce concept.
Cela peut être compris comme ceci :
Le tri rapide est une version améliorée du tri à bulles. L'ensemble du processus consiste à supprimer et à réparer les éléments, à les démolir et à les réparer, à les démolir et à les réparer, jusqu'à ce que tous les éléments atteignent un état ordonné.
Idée de base :
Prenez d'abord un nombre de la séquence comme numéro de base, puis effectuez un partitionnement par taille ;
Dans le processus de partitionnement, tous les nombres supérieurs à ce nombre sont placés à sa droite, et les nombres inférieurs à ce nombre ; ou égal à celui-ci sont Mettez-les tous à gauche ;
Répétez la deuxième étape pour les intervalles gauche et droit jusqu'à ce qu'il n'y ait qu'un seul nombre dans chaque intervalle et que le tri soit terminé.
Cas de mise en œuvre
Démontons-le étape par étape à travers des images et des textes.
Prenons [4,1,6,2,9,3]
ce tableau comme exemple.
Premier passage :
Divisez d'abord [4,1,6,2,9,3] et sélectionnez l'élément 4 comme point pivot Vérifiez si 1 < 4 (point pivot) Vérifiez si 6 < (point pivot) Vérifiez si 2 < 4 (point pivot) 2 < 4 (point pivot) est vrai, échangez l'index 2 avec l'index stocké 6 Vérifiez si 9 < (point pivot) Vérifiez si 3 < 4 (point pivot) 3 < 4 (point pivot) Si vrai, stockez les index 3 et 6 Effectuez l'échange Échangez le point pivot 4 et le stockage index 3 À ce moment, le côté gauche du point pivot 4 est inférieur à 4 et le côté droit est supérieur à 4
L'ordre actuel du tableau est [3, 1, 2, 4, 9, 6].
Étape suivante :
Triez d'abord le côté gauche Sélectionnez l'élément 3 comme point pivot Vérifiez si 1 < (point pivot) Échangez le point pivot 3 et la valeur de l'index de stockage 2 Maintenant, le point pivot a été divisé à la position triée [2,1] Sélectionnez 2 comme point pivot -
Vérifiez si 1 <2 (point pivot) Le parcours à gauche est terminé, et le point pivot 2 et l'index de stockage 1 sont échangés Il en va de même pour le côté droit...à éviter visuel Je ne décrirai pas la fatigue une par une, mais vous pouvez voir l'image de démonstration dynamique ci-dessous.
2. L'ensemble du processus de la méthode de tri rapide
3.
import java.util.Arrays; public class QuickSortDemo { //四个步骤: //1.比较startIndex和endIndex,更喜欢理解为校验 //2.找出基准 //3.左边部分排序 //4.右边排序 public static void quickSort(int[] arr, int startIndex, int endIndex) { if (startIndex < endIndex) { //找出基准 int partition = partition(arr, startIndex, endIndex); //分成两边递归进行 quickSort(arr, startIndex, partition - 1); quickSort(arr, partition + 1, endIndex); } } //找基准 private static int partition(int[] arr, int startIndex, int endIndex) { int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; //等于就没有必要排序 while (left != right) { while (left < right && arr[right] > pivot) { right--; } while (left < right && arr[left] <= pivot) { left++; } //找到left比基准大,right比基准小,进行交换 if (left < right) { swap(arr, left, right); } } //第一轮完成,让left和right重合的位置和基准交换,返回基准的位置 swap(arr, startIndex, left); return left; } //两数交换 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] a = {3, 1, 2, 4, 9, 6}; quickSort(a, 0, a.length - 1); //输出结果 System.out.println(Arrays.toString(a)); } }
Résultat de sortie :
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Vous devez connaître Spring, alors parlons de l'ordre de toutes les notifications d'Aop. Comment Spring Boot ou Spring Boot 2 affecte-t-il l'ordre d'exécution d'aop ? Parlez-nous des pièges que vous avez rencontrés en AOP ?

MOO signifie qu'il existe une vulnérabilité dans le programme, qui peut être causée par la configuration du code ou des paramètres JVM. Cet article explique aux lecteurs comment dépanner lorsqu'un processus Java déclenche le MOO.

Ne sous-estimez pas les questions d’examen écrit de nombreuses entreprises. Il existe des pièges et vous pouvez y tomber accidentellement. Lorsque vous rencontrez ce genre de question de test écrit sur les cycles, je vous suggère de réfléchir calmement et de procéder étape par étape.

Le chapitre supplémentaire de la série de programmation simultanée Java, C A S (Comparer et échanger), est toujours dans un style facile à comprendre avec des images et des textes, permettant aux lecteurs d'avoir une conversation folle avec l'intervieweur.

La semaine dernière, un ami du groupe est allé passer un entretien avec Ping An Insurance. Le résultat a été un peu regrettable, ce qui est bien dommage, mais j'espère que vous ne vous découragerez pas, comme vous l'avez dit, essentiellement toutes les questions rencontrées. l'entretien peut être résolu en mémorisant les questions de l'entretien. C'est résolu, alors s'il vous plaît, travaillez dur !

Cet article examinera 5 questions d'entretien sur la classe Java String. J'ai personnellement rencontré plusieurs de ces cinq questions au cours du processus d'entretien. Cet article vous aidera à comprendre pourquoi les réponses à ces questions sont ainsi.

Meituan, tu vois si tu peux y répondre ?

Le tri rapide a été proposé par C. A. R. Hoare en 1962. Son idée de base est de diviser les données à trier en deux parties indépendantes via un tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis d'utiliser cette méthode pour séparer rapidement les deux parties des données. . Tri, l'ensemble du processus de tri peut être effectué [de manière récursive], de sorte que l'ensemble des données devienne une séquence ordonnée.
