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.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day12 à partir de zéro "617. Fusionner deux arbres binaires"
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Le niveau de difficulté est moyen. Récemment, il semble qu'il y ait beaucoup de bonnes questions car je choisis de préférence parmi les 100 questions les plus appréciées. Bien sûr, il est avantageux d'avoir des connaissances mathématiques, mais c'est très intéressant car il y a beaucoup de problèmes qui mèneront à la bonne réponse si vous réfléchissez bien même si vous ne l'avez pas.
Un nombre naturel «num» est donné. Calcule le nombre de 1 dans la représentation binaire de tous les nombres i dans la plage «0 ≤ i ≤ num» et les renvoie sous forme de tableau.
Pensez-vous que ce problème n'est qu'un énoncé de problème? Ce sera. Regardons un exemple.
Example 1:
Input: 2 Output: [0,1,1]
Dans ce cas, 2 est donné comme «num». La conversion de [0,1,2] en un nombre binaire donne [0,1,10], le comptage du nombre de 1 contenu dans chacune de ces valeurs donne «011» et la conversion en un tableau donne [0,1,10]. 1]. Renvoie enfin ce tableau.
Example 2:
Input: 5 Output: [0,1,1,2,1,2]
Dans ce cas, 5 est donné comme «num». La conversion de [0,1,2,3,4,5] en nombres binaires donne [0,1,10,11,100,101], et le comptage du nombre de 1 contenu dans ces valeurs donne «011212», [0, 1,1,2,1,2].
Tout d'abord, préparez une liste à renvoyer, ʻans`, et envisagez d'utiliser une instruction for qui répète les valeurs de 1 à num + 1.
Il effectue une conversion binaire pour chaque nombre, ajoute un compte de 1 à la liste et renvoie finalement le premier «an» préparé. Le plus important de ces problèmes est peut-être un algorithme qui effectue également une conversion binaire et compte le nombre de 1.
Divisez le i-ème de ʻanspar 2, et ajoutez la valeur au reste quand i est divisé par 2, et il sera bien converti. En effet, si la valeur denum` est impaire, le dernier chiffre sera 1 et 1 sera supprimé par décalage vers la droite, et s'il est pair, il sera toujours 0, donc même si un décalage vers la droite est effectué, la même valeur sera obtenue. Parce que cela devient l'un des.
En considérant cet exemple, par exemple, si «num» vaut 4,
ans[4/2]+(4%2)
Ce sera. Dans ce cas, c'est le deuxième de ʻans [0,1,1,2] `, c'est-à-dire 1. Le 1 et le 0, qui est le reste de (4% 2), sont ajoutés, et 1 qui est le nombre de 1 de «100» lorsque 4 est converti en binaire est ajouté à la liste.
J'ai écrit comme suit.
class Solution:
def countBits(self, num: int) -> List[int]:
ans = [0]
for i in range(1,num+1):
ans.append(ans[i//2] + (i%2))
return ans
# Runtime: 84 ms, faster than 72.90% of Python3 online submissions for Counting Bits.
# Memory Usage: 20.7 MB, less than 5.00% of Python3 online submissions for Counting Bits.
Je réfléchis à ce problème depuis longtemps. Je veux trouver une solution plus rapidement.
Recommended Posts