[PYTHON] Soit Code Jour 76 à partir de zéro "3. Sous-chaîne la plus longue sans caractères répétitifs"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à ce moment-là sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day75 "15.3 Sum" à partir de zéro

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

3. Longest Substring Without Repeating Characters Le niveau de difficulté est moyen.

Le problème est, étant donné une chaîne, de trouver la longueur de la sous-chaîne la plus longue sans répéter le caractère.

Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3: Input: "pwwkew" Output: 3

Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic,length,start = {},0,0
        for i,j in enumerate(s):
            if j in dic:
                sums = dic[j] + 1
                if sums > start:
                    start = sums
            num = i - start + 1
            if num > length:
                length = num
            dic[j] = i
        return length
# Runtime: 60 ms, faster than 76.33% of Python3 online submissions for Longest Substring Without Repeating Characters.
# Memory Usage: 13.9 MB, less than 55.58% of Python3 online submissions for Longest Substring Without Repeating Characters.

«length» contient la longueur maximale et «start» contient la position de départ de la sous-chaîne.

Je n'écris pas beaucoup ...

Au fait, est-il propre à Python que les fonctions intégrées soient pratiques? Selon la langue, il peut être plus facile à implémenter avec des fonctions intégrées ...

C'est intéressant d'essayer de le résoudre dans d'autres langages, donc je l'écris parfois en Java, mais c'est difficile de s'y habituer.

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.