Let Code Day 15 "283. Move Zeroes" à partir de zéro

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.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 14 "136. Numéro unique" à partir de zéro

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

problème

283. Move Zeroes

Le niveau de difficulté est facile. Cette fois-ci est également un extrait des 100 questions les plus appréciées.

Le problème est que, étant donné un tableau, il lèche tous les éléments qu'il contient et, si la valeur est «0», insère ce «0» à la fin. À ce moment-là, le problème est que l'ordre des éléments avec des valeurs autres que 0 doit être conservé.

Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0]

Solution

J'ai proposé deux idées, alors j'en ai implémenté une. L'un consiste à déplacer 0 et l'autre à déplacer une valeur non nulle. Tout d'abord, j'ai mis en œuvre le premier.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(1,len(nums)+1):
            if nums[-i] == 0:
                nums.pop(-i)
                nums.append(0)
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

Les éléments sont supprimés et insérés à la fin avec pop et append.

En revanche, ce dernier a été mis en œuvre comme suit.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        h = -1
        for i in range(len(nums)):
            if nums[i] != 0:
                h += 1
                nums[h], nums[i] = nums[i], nums[h]
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

Tout d'abord, remplacez -1 par «h» et le nombre d'éléments par «i». Et si nums [i] n'est pas 0, ajoutez 1 à h et remplacez nums [i] par nums [h] et nums [h] par nums [i]. Il peut être remplacé par. En conséquence, en faisant cela pour tous, toutes les valeurs non nulles seront triées au début sans perturber l'ordre.

Cette fois, j'y ai pensé en deux temps. J'ajouterai s'il y a une meilleure façon de penser.