Faits: Faits: A. Lors d'un contrôle dans un salon de massage à Lausanne, le 18 février 1994, la police a rencontré A.X._, ressortissant brésilien né en 1966. Entendu le 21 février 1994, il a déclaré être arrivé en Suisse le 19 décembre 1993. Par la suite, l'intéressé a indiqué à l'Office cantonal du contrôle des habitants et de police des étrangers du canton de Vaud (ci-après: Office cantonal) être entré en Suisse le 28 mai 1994 et vouloir obtenir une autorisation de séjour afin de vivre auprès de sa conjointe, B.X._, ressortissante suisse d'origine brésilienne, qu'il avait épousée le 16 juin 1994. Le 30 juin 1994, l'Office cantonal a accordé à A.X._ l'autorisation de séjour demandée et l'a régulièrement renouvelée jusqu'au 16 juin 1998. Durant ces années, la police cantonale du canton de Vaud (ci-après: la police cantonale) a procédé à différentes auditions de A.X._ et de son épouse. Il en ressortait, notamment, que B.X._ avait donné naissance à une fille, le 22 septembre 1997, dont le père biologique était un tiers et que A.X._ avait quitté le domicile conjugal et qu'il était disposé à accepter la demande en divorce de son épouse. Par décision du 26 novembre 1998, l'Office cantonal a refusé la prolongation de l'autorisation de séjour de l'intéressé et lui a imparti un délai au 3 janvier 1999 pour quitter le territoire cantonal, car il se prévalait d'un mariage qui n'existait plus que juridiquement et que ces faits étaient constitutifs d'un abus de droit. Cette décision a été confirmée par le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif) le 19 avril 1999, et un nouveau délai au 10 juin 1999 a été fixé à A.X._ pour quitter le territoire cantonal. Par décision du 26 novembre 1998, l'Office cantonal a refusé la prolongation de l'autorisation de séjour de l'intéressé et lui a imparti un délai au 3 janvier 1999 pour quitter le territoire cantonal, car il se prévalait d'un mariage qui n'existait plus que juridiquement et que ces faits étaient constitutifs d'un abus de droit. Cette décision a été confirmée par le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif) le 19 avril 1999, et un nouveau délai au 10 juin 1999 a été fixé à A.X._ pour quitter le territoire cantonal. B. Le 1er juin 1999, A.X._ a déposé une demande de réexamen auprès de l'Office cantonal. Il invoquait sa réconciliation avec son épouse et son intention d'entreprendre un apprentissage de coiffeur. L'intéressé a été autorisé à séjourner sur le territoire vaudois jusqu'à droit connu sur sa requête et à exercer une activité d'assistant coloriste dans un salon de coiffure jusqu'à droit connu sur sa demande de réexamen. Par décision du 23 août 1999, l'Office cantonal n'est pas entré en matière sur ladite demande. Il se fondait sur une lettre de l'épouse de l'intéressé, datée du 21 juillet 1999 et adressée au Service du contrôle des habitants de Lausanne (ci-après: le Service du contrôle des habitants), où elle indiquait qu'il n'y avait eu aucune reprise de la vie commune et que l'annonce faite par son mari d'un domicile commun était une tromperie. L'Office cantonal a alors invité l'intéressé à quitter le territoire cantonal immédiatement. Par décision du 22 novembre 1999, l'Office fédéral des étrangers, qui s'est appelé par la suite Office fédéral de l'immigration, de l'intégration et de l'émigration et se nomme actuellement Office fédéral des migrations, (ci-après: l'Office fédéral), sur proposition de l'Office cantonal, a prononcé l'extension à tout le territoire de la Confédération de la décision cantonale de renvoi. Un délai au 15 janvier 2000 a été imparti à A.X._ pour quitter la Suisse. Le 31 janvier 2000, l'intéressé s'est présenté au Service du contrôle des habitants et a déclaré qu'il n'avait pas l'intention de quitter le territoire suisse et qu'il travaillait dans un salon de coiffure à Neuchâtel tout en étant domicilié à Lausanne. Le 7 mars 2000, A.X._ a déposé auprès dudit Service une demande d'autorisation de séjour annuelle en vue de l'exercice d'une activité lucrative comme employé qualifié dans un salon de coiffure sis à Neuchâtel. Entendu le 25 avril 2000 par la police vaudoise sur sa présence sur le territoire cantonal, l'intéressé a finalement déclaré qu'il était d'accord de quitter la Suisse au mois de juillet 2000. Une carte de sortie à timbrer au poste frontière lui a alors été délivrée afin qu'il puisse attester son départ de Suisse avant le 12 août 2000. Elle a été retournée à la police cantonale avec un timbre apposé le 12 août 2000 par les services douaniers de l'aéroport de Genève. Selon un avis du Service du contrôle des habitants du 20 juillet 2000, le divorce des époux X._ est entré en force le 20 juin 2000. Le 31 janvier 2000, l'intéressé s'est présenté au Service du contrôle des habitants et a déclaré qu'il n'avait pas l'intention de quitter le territoire suisse et qu'il travaillait dans un salon de coiffure à Neuchâtel tout en étant domicilié à Lausanne. Le 7 mars 2000, A.X._ a déposé auprès dudit Service une demande d'autorisation de séjour annuelle en vue de l'exercice d'une activité lucrative comme employé qualifié dans un salon de coiffure sis à Neuchâtel. Entendu le 25 avril 2000 par la police vaudoise sur sa présence sur le territoire cantonal, l'intéressé a finalement déclaré qu'il était d'accord de quitter la Suisse au mois de juillet 2000. Une carte de sortie à timbrer au poste frontière lui a alors été délivrée afin qu'il puisse attester son départ de Suisse avant le 12 août 2000. Elle a été retournée à la police cantonale avec un timbre apposé le 12 août 2000 par les services douaniers de l'aéroport de Genève. Selon un avis du Service du contrôle des habitants du 20 juillet 2000, le divorce des époux X._ est entré en force le 20 juin 2000. C. Le 10 octobre 2000, C._, a présenté auprès du Service des étrangers du canton de Neuchâtel une demande de main-d'oeuvre étrangère en faveur de A.X._ pour l'engager en qualité de coiffeur dans son salon de coiffure à Neuchâtel. Le 28 novembre 2000, la Section main-d'oeuvre du Service précité a répondu que l'intéressé ne pouvait pas prendre un emploi dans la mesure où il n'était pas en possession d'une autorisation de séjour. Le 27 février 2001, C._ a réitéré sa demande qui a été refusée le 20 avril 2001. Le Département de l'économie publique du canton de Neuchâtel a rejeté, par décision du 3 mai 2002, le recours de celui-ci. Selon le questionnaire rempli le 12 décembre 2000 par le Contrôle des habitants de Neuchâtel, A.X._ a déclaré qu'il était arrivé à Neuchâtel le 1er novembre 2000 en provenance du Brésil et qu'il avait déposé ses papiers le 29 novembre 2000. Il a aussi indiqué, comme motif d'entrée en Suisse, qu'il avait l'intention de séjourner et de travailler dans ce pays pour une durée indéterminée. Le 18 janvier 2001, le Service des étrangers du canton de Neuchâtel a refusé d'octroyer une autorisation de séjour à l'intéressé et lui a imparti un délai au 28 février 2001 pour quitter le territoire cantonal. Par décision du 17 septembre 2002, le Département de l'économie publique du canton de Neuchâtel a confirmé ce refus et indiqué qu'un nouveau délai de départ pour quitter le territoire lui serait imparti. Selon le questionnaire rempli le 12 décembre 2000 par le Contrôle des habitants de Neuchâtel, A.X._ a déclaré qu'il était arrivé à Neuchâtel le 1er novembre 2000 en provenance du Brésil et qu'il avait déposé ses papiers le 29 novembre 2000. Il a aussi indiqué, comme motif d'entrée en Suisse, qu'il avait l'intention de séjourner et de travailler dans ce pays pour une durée indéterminée. Le 18 janvier 2001, le Service des étrangers du canton de Neuchâtel a refusé d'octroyer une autorisation de séjour à l'intéressé et lui a imparti un délai au 28 février 2001 pour quitter le territoire cantonal. Par décision du 17 septembre 2002, le Département de l'économie publique du canton de Neuchâtel a confirmé ce refus et indiqué qu'un nouveau délai de départ pour quitter le territoire lui serait imparti. D. Le 29 octobre 2002, A.X._ a sollicité auprès du Service des étrangers du canton de Neuchâtel la délivrance d'une autorisation de séjour pour cas personnel d'extrême gravité, en invoquant la longueur de son séjour en Suisse, son indépendance financière, son intégration sociale et le fait qu'il n'entretenait plus de relation sur le plan personnel et économique avec son pays d'origine. Le 15 mai 2003, le Service des étrangers du canton de Neuchâtel a informé A.X._ qu'il avait émis un préavis favorable à l'octroi d'une autorisation de séjour au sens de l'art. 13 let. f de l'ordonnance fédérale du 6 octobre 1986 limitant le nombre des étrangers (OLE; RS 823.21) et il a transmis son dossier pour examen et décision à l'Office fédéral. Le 11 juillet 2003, l'Office fédéral a refusé de mettre A.X._ au bénéfice d'une exception aux mesures de limitation au sens de l'art. 13 lettre f OLE. Il a notamment relevé que la durée du séjour en Suisse de l'intéressé était brève par rapport aux années passées dans son pays d'origine où il avait gardé ses attaches culturelles, familiales et sociales les plus étroites. L'Office fédéral a également relevé les contradictions du dossier relativement au but de son séjour, les interruptions de celui-ci et son attitude consistant à se soustraire continuellement à son renvoi. A la suite de cette décision, le Département de l'économie publique du canton de Neuchâtel a fixé à l'intéressé un nouveau délai au 15 septembre 2003 pour quitter le canton de Neuchâtel. E. Le 25 avril 2005, le Département fédéral de justice et police (ci-après: le Département fédéral) a rejeté le recours de A.X._ contre la décision de l'Office fédéral du 11 juillet 2003, et confirmé l'assujettissement de l'intéressé aux mesures de limitation. Le Département fédéral a confirmé, en les développant, les arguments retenus par l'Office fédéral. Concernant la durée des séjours de l'intéressé en Suisse, le Département fédéral a relevé notamment qu'il n'avait pu demeurer légalement dans ce pays, outre l'autorisation de séjour octroyée de 1994 à 1998 et non renouvelée à la suite d'un abus de droit, que grâce à de multiples procédures de recours et de réexamen introduites auprès des autorités de police des étrangers vaudoises et neuchâteloises, la durée totale de son séjour en Suisse devant de ce fait être sérieusement relativisée. De plus, l'intéressé ne pouvait pas se prévaloir d'une intégration socioprofessionnelle si remarquable qu'elle impose de lui accorder une exemption aux mesures de limitation. E. Le 25 avril 2005, le Département fédéral de justice et police (ci-après: le Département fédéral) a rejeté le recours de A.X._ contre la décision de l'Office fédéral du 11 juillet 2003, et confirmé l'assujettissement de l'intéressé aux mesures de limitation. Le Département fédéral a confirmé, en les développant, les arguments retenus par l'Office fédéral. Concernant la durée des séjours de l'intéressé en Suisse, le Département fédéral a relevé notamment qu'il n'avait pu demeurer légalement dans ce pays, outre l'autorisation de séjour octroyée de 1994 à 1998 et non renouvelée à la suite d'un abus de droit, que grâce à de multiples procédures de recours et de réexamen introduites auprès des autorités de police des étrangers vaudoises et neuchâteloises, la durée totale de son séjour en Suisse devant de ce fait être sérieusement relativisée. De plus, l'intéressé ne pouvait pas se prévaloir d'une intégration socioprofessionnelle si remarquable qu'elle impose de lui accorder une exemption aux mesures de limitation. F. Agissant par la voie du recours de droit administratif, A.X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler la décision du Département fédéral du 25 avril 2005 et de le mettre au bénéfice d'une exception aux mesures de limitation au sens de l'art. 13 lettre f OLE. Il se prévaut, notamment, de ses quelque douze ans de résidence en Suisse et relève sa bonne intégration professionnelle et sociale. Il invoque également la relation homosexuelle qu'il entretient en Suisse depuis plus de quatre ans. Le Département fédéral conclut au rejet du recours. 