Ces derniers jours, je recherche un emploi par temps frais de 40 ° à Shanghai. Je me sens tellement heureux. Chaque fois que j'interviewe, je dois m'asseoir là et transpirer pendant longtemps avant que je puisse revenir à mes sens. Je ressens le profond amour du monde pour moi. Je suis revenu sur le sujet. Au cours de l'entretien, j'ai rencontré plusieurs tests écrits. Il y a une question. Comme je ne l'ai jamais rencontré dans mon travail réel, j'y fais attention. La question est la suivante:
Il y a un tableau: var arr = [1,2,1,3,3,2,4,6,3], qui est changé en distribution normale par traitement: [1,2,3,3,6,4,3,2,1].
J'expliquerai brièvement la distribution normale. En fait, vous pouvez comprendre à peu près le tableau transformé. Les deux extrémités sont petites et le milieu est grand. La courbe normale reflétée dans l'axe de coordonnées est en forme d'horloge, avec les deux extrémités bas et moyen. La gauche et la droite symétriques parce que ses courbes sont en forme de cloche, donc les gens l'appellent souvent des courbes en forme d'horloge.
C'est la dernière question de l'entretien. Quand je l'ai eu ici, j'étais serré et le temps était chaud, soif et affamé. La fille de la réception avait l'air si bonne (arrête de parler de bêtises, c'était parce que l'algorithme était faible ...). Après une petite réflexion, j'ai écrit le code suivant:
var arr = [1,2,1,3,3,2,4,6,3] ~ (fonction (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (fonction (a, b) {return ab}) // arrange d'abord le tableau de petit à grand pour obtenir [1, 1, 2, 3, 3, 3, 4, 6] pour (; i <l; if (i% 2 == 0) {temp [i / 2] = triarr [i] // mettez les indices à l'avant dans l'ordre des nombres uniformes} else {temp [l- (i + 1) / 2] = sortarr [i] // mettez les indices à l'avant dans l'ordre des nombres impairs}} parfait}) (arr)Comme c'était un test écrit, j'ai fait le programme dans mon esprit pendant un certain temps et j'ai senti qu'il n'y avait pas de gros problème et remis le journal. Plus tard, l'intervieweur a examiné le document de test et n'a pas mentionné cette question lors de l'entretien. J'ai donc senti qu'il n'y avait aucun problème avec cette méthode, donc je n'ai pas demandé à nouveau lors de l'entretien. Cependant, sur le chemin du retour, j'ai soudainement pensé à une situation comme ceci:
var arr = [1,2,3,4,5,6,7,8,9] // un tableau d'incrémentation régulière ~ (fonction (arr) {var temp = [], i = 0, l = arr.length, sortarr = arr.sort (fonction (a, b) {return ab}) pour (; i <l; i ++) {if (i% 2 == 0) {temp [i / 2] temp [l- (i + 1) / 2] = sortarr [i]}} console.log (temp) // [1, 3, 5, 7, 9, 8, 6, 4, 2] Le problème s'est produit.Oui, de cette manière, les parties gauche et droite de ce tableau ne sont pas symétriques, avec 9 comme centre, avec 1 + 3 + 5 + 7 = 16 à gauche, et 2 + 4 + 6 + 8 = 20 à droite. Il est évident que la gauche est légère et que la droite est lourde, pas une distribution normale uniforme. À mesure que le tableau se développe, les problèmes deviendront de plus en plus graves.
STACHES DE LIGNES. . . . Je suis un bourgeon qui est sur le point de fleurir. Ne me traitez pas comme ça. . .
Il semble que le code précédent ne peut pas être utilisé, je ne peux donc repenser la solution. En fait, le cœur du problème est de s'assurer que les côtés gauche et droit du réseau sont égaux ou à peu près égaux. Qu'il s'agisse d'un tableau de nombres impairs ou même de nombres, le tableau peut être divisé en deux parties (la valeur maximale des nombres impairs peut également être considérée comme un tableau de nombre uniforme. Même s'il y a plusieurs valeurs maximales identiques, cela n'a pas d'importance. Après le tri de petit à grand, il faut simplement supprimer le dernier). Ou selon la méthode ci-dessus, lorsque l'indice est uniforme, mettez-le sur le côté gauche et droit lorsqu'il est étrange, mettez-le sur le côté droit. Dans le processus de croissance du tableau sur le côté gauche et droit, lorsque les longueurs du réseau sont égales, comparez la somme des côtés gauche et droit. Parce qu'il est disposé de petit à grand, dans des circonstances normales, le côté droit sera plus grand que le côté gauche, puis échangera le premier à droite et le dernier sur le côté gauche pour atteindre le but de l'équilibre. Le code est le suivant:
var arr = [1,2,3,4,5,6,7,8,9], sortarr = arr.sort (fonction (a, b) {return ab}), l = arr.length, temp_left = [], temp_right = [] fonction tri (arr) {var i = 0 pour (; i <l; i ++) {var eq = trirAr [i] i% 2 == 0? temp_left.push (eq): temp_right.unshift (eq) if (i> 1) {if (temp_left.length == temp_right.length &&! compare (temp_left, temp_right)) {wrap_left, temp_right) // lorsque le retour est égal et que la droite est plus importante que le côté gauche est échangé Temp_left.concat (temp_right)} // Array Sum Fonction Sum (arr) {return eval (arr.join ("+")); } // Fonction de comparaison du tableau Compare (Arr1, Arr2) {return sum (arr1)> = sum (arr2)} // Le dernier sur les échanges de gauche avec le premier sur la fonction de bonne fonction (l, r) {var m = r.shift () r.unshift (l.pop ()) l.push (m)} console.log (SORT (ARR) // Get 5, 3, 2]De cette façon, toute la distribution normale sera beaucoup plus uniforme. Faites quelques autres ensembles de tests pour voir l'effet:
Arr = [1,333 444 555,66,7788,909] console.log (Sort (arr)) // [1 444 909, 7788 555,333,66] ARR = [168.6,177.5,174.2,189.3,167.2,177.6,167.8,175.5] Console.log (Sorh
Ça a l'air plutôt bien. Il y a un autre article dans le petit site qui a cliqué sur la vue, qui a été achevé en C ++. Cependant, le résultat final de l'article n'était pas une distribution normale uniforme, mais elle était similaire à mon premier programme.
Je ne sais pas grand-chose sur C ++, et je n'ai pas exécuté plusieurs ensembles de résultats à voir. Les étudiants intéressés peuvent l'essayer en comparaison.
Je n'ai testé que tous les programmes de cet article dans Chrome. S'il y a des problèmes avec d'autres navigateurs, j'espère laisser un message pour vous informer. En fait, cette chose n'est pas difficile. Utilisez-le simplement comme enregistrement et peut être utilisé en cas de besoin.