[Prog] Cet exo d'algo basique DETROUSSE le 18-25

Le 08 décembre 2018 à 00:57:56 stuckRANG3 a écrit :

Le 08 décembre 2018 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractères

Je veux une complexité en o(n), je vous ai laissé des indices sur les structures de données à utiliser. Les L1 de Jussieu, vous avez le droit à un tiers-temps

C'est moi qui attend ton pseudo code depuis tout a l'heure quai

Je suis sur mobile depuis tout à l'heure, c'est long à écrire

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
    Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
        retirer S[i] et S[i+1]
        si i>0  alors i--
    }
}

Propre.

Le 08 décembre 2018 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractères

Je veux une complexité en o(n), je vous ai laissé des indices sur les structures de données à utiliser. Les L1 de Jussieu, vous avez le droit à un tiers-temps parce que vous puez la défaite eh eh

C'est impossible en o(n)
Ayez un peu de rigueur quand vous donnez un énoncé, c'est O(n)

Le 08 décembre 2018 à 00:56:15 gay_pom_12 a écrit :

Le 08 décembre 2018 à 00:49:27 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:48:21 gay_pom_12 a écrit :

Le 08 décembre 2018 à 00:40:24 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:34:30 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:29:41 KheyAuxPommes a écrit :
Ma solution en 12 lignes btw :

def reduce(string):
reduction = ""
for c in string:
if not reduction:
reduction += c
continue
prev = reduction[-1]
if prev.isupper() != c.isupper() and c.lower() == prev.lower():
reduction = reduction[:-1]
else:
reduction += c
return reduction

C'est pas O(n) je pense

Pourquoi ? Je ne parcours qu'une seule fois la chaîne de caractères d'entrée.

T'es en python khey, srting est pas un type mutable
à chaque fois que tu fais reduction = reduction[:-1]ou reduction += cca te crée une nouvelle chaine et parcourt reductionpour la remplir avant d'affecter ca à la même adresse.

Mais encore une fois, on s'en fout ça, c'est un détail, ça change rien à l'algo en lui-même.

mais si putain, à chaque fois que tu fais reduction+=ctu reparcours reductionpour refaire une chaine. Rien que ca ca te fait passer de O(n) à O(n²).
C'est juste la faute de python par contre pour le coup

Mais mon code c'était pas du Python c'était du pseudo-code, désolé si tu t'es fourvoyé, c'est vrai que les deux ont une syntaxe similaire.

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
    Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
        retirer S[i] et S[i+1]
        si i>0  alors i--
    }
}

Propre.

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variables

Le 08 décembre 2018 à 01:00:19 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractères

Je veux une complexité en o(n), je vous ai laissé des indices sur les structures de données à utiliser. Les L1 de Jussieu, vous avez le droit à un tiers-temps parce que vous puez la défaite eh eh

C'est impossible en o(n)
Ayez un peu de rigueur quand vous donnez un énoncé, c'est O(n)

Rdv à l'INRIA pour un 1v1 lundi 8h

Le 08 décembre 2018 à 00:59:06 EnBaDuBlok a écrit :
Le pire c'est que vous continuez avec vos O(n) pour le palindrome alors qu'après 6 pages de topic aucun de vous a été foutu de trouver la solution du premier problème avec tous vos trucs théoriques

Allez le singe on retourne pisser du python en faisant autant d'erreurs que l'auteur

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variables

gfg = ?

Le 08 décembre 2018 à 00:59:08 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:57:56 stuckRANG3 a écrit :

Le 08 décembre 2018 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractères

Je veux une complexité en o(n), je vous ai laissé des indices sur les structures de données à utiliser. Les L1 de Jussieu, vous avez le droit à un tiers-temps

C'est moi qui attend ton pseudo code depuis tout a l'heure quai

Je suis sur mobile depuis tout à l'heure, c'est long à écrire

En fait ta méthode avec les arbres je vois pas comment ça peut marcher, parce que tu sera quand même ramené a résoudre le problème "trouver le plus grand sous arbres symétrique"

Le 08 décembre 2018 à 01:01:56 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variables

gfg = ?

Geeksforgeeks, je pioche les exos que je donne aux licences là bas

Le 08 décembre 2018 à 01:01:51 PlateauDeSACLAY a écrit :

Le 08 décembre 2018 à 00:59:06 EnBaDuBlok a écrit :
Le pire c'est que vous continuez avec vos O(n) pour le palindrome alors qu'après 6 pages de topic aucun de vous a été foutu de trouver la solution du premier problème avec tous vos trucs théoriques

Allez le singe on retourne pisser du python en faisant autant d'erreurs que l'auteur

0 erreurs dans mon code, je sais pas où tu vois ça.

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
    Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
        retirer S[i] et S[i+1]
        si i>0  alors i--
    }
}

Propre.

Presque, j'aurais du rajouter un break dans le tant que pour le cas ou on se retrouve avec une chaine vide au final mais bon j'ai eu la flemme

Le 08 décembre 2018 à 00:59:06 EnBaDuBlok a écrit :
Le pire c'est que vous continuez avec vos O(n) pour le palindrome alors qu'après 6 pages de topic aucun de vous a été foutu de trouver la solution du premier problème avec tous vos trucs théoriques

c'est quoi la solution aussi, un truc O(n) ou plus ?
J'ai jamais codé sérieusement que pour le CNRS en stage, quand tu fais un programme qui met 18 heures à finir ils te tapent sur l'épaule et sont contents

Le 08 décembre 2018 à 01:02:41 PinkHair-- a écrit :

Le 08 décembre 2018 à 01:01:56 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variables

gfg = ?

Geeksforgeeks, je pioche les exos que je donne aux licences là bas

Ils sont bons les licences en algo ?

Le 08 décembre 2018 à 01:02:41 PinkHair-- a écrit :

Le 08 décembre 2018 à 01:01:56 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 01:00:58 PinkHair-- a écrit :

Le 08 décembre 2018 à 00:59:29 KheyAuxPommes a écrit :

Le 08 décembre 2018 à 00:56:05 [carton] a écrit :
Un truc trés vite fait qui devrait se faire en O(n) :

Pour i allant de 0 à taille de S -1{
Tant que S[i] et S[i+1] sont des lettres identiques de casse différentes{
retirer S[i] et S[i+1]
si i>0 alors i--
}
}

Propre.

Cest marrant j'ai retrouvé exactement le même code C sur gfg, avec la même boucle while et les mêmes noms de variables

gfg = ?

Geeksforgeeks, je pioche les exos que je donne aux licences là bas

Ah ouais, mois je vais sur Codeforces quand je donne des exos à mon prof d'algo particulier.

lol. Je vais le faire comme un porc en Ruby.

string = "blablablablaqlksdmsqkdqsmlkdqsdlblablablaLKSQDLKDLblabla"
string = string.downcase
array ||= []

for i in 0..string.length
  array << string.byteslice(i)
end

array = array.uniq

PD

Le 08 décembre 2018 à 01:04:30 athusnadorian a écrit :
lol. Je vais le faire comme un porc en Ruby.

string = "blablablablaqlksdmsqkdqsmlkdqsdlblablablaLKSQDLKDLblabla"
array ||= []

for i in 0..string.length
  array << string.byteslice(i)
end

array.uniq!

PD

J'ai rien compris mais à mon avis c'est faux.