Le 08 décembre 2018 à 01:08:34 PinkHair-- a écrit :
Le 08 décembre 2018 à 01:03:41 PlateauDeSACLAY a écrit :
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.
https://image.noelshack.com/fichiers/2017/02/1484388157-obama.png 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
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png gfg = ?
Geeksforgeeks, je pioche les exos que je donne aux licences là bas
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png Ils sont bons les licences en algo ?
https://image.noelshack.com/fichiers/2016/47/1480064732-1467335935-jesus4.png Aussi médiocres que les centraliens, si je devais les situer
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png Plus sérieusement, ils sont bons pour programmer et pour faire du visuel. Dès lors qu'il s'agit de se creuser les méninges, les étudiants qui s'en sortent se comptent sur les doigts d'une main
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png
Si je suis ce type d'étudiant tu me conseille quoi pour pousser loin l'algo ? Irl ces mecs la tu les laisse tranquille ou tu les pousses un peu ?
Le 08 décembre 2018 à 01:06:22 Mecadam a écrit :
i=0
while(i != len(txt)):
j = i+1
while(j < len(txt) and (txt[i] == txt[j].lower() or txt[i] == txt[j].upper() or txt[i] == txt[j])):
if (j < len(txt)):
txt = txt[:i]+txt[j:]
taille = len(txt)
j+=1
i+=1Voilà en O(n) en 10 lignes en python khey
Pas du O(n) je crois à cause de txt = ...
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.
https://image.noelshack.com/fichiers/2017/02/1484388157-obama.png 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
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png gfg = ?
Geeksforgeeks, je pioche les exos que je donne aux licences là bas
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png
Ils sont bons les licences en algo ?
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 à 00:56:31 PinkHair-- a écrit :
Sinon j'attends le pseudo-code pour le plus long palindrome d'une chaîne de caractèreshttps://image.noelshack.com/fichiers/2016/41/1476132386-1.png 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
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png
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: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
https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png 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
https://image.noelshack.com/fichiers/2018/47/1/1542653887-95803-full.jpg
à chaque fois que tu faisreduction = reduction[:-1]
oureduction += c
ca te crée une nouvelle chaine et parcourtreduction
pour 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. Tu peux pas juste ignorer comment on implémente les trucs sinon (par exemple) avoir la taille d'une liste ça va du O(1) au O(n) (différentes structures de données tout ça)
La on s'en branle oui mais faut faire gaffe
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
https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png 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
https://image.noelshack.com/fichiers/2018/47/1/1542653887-95803-full.jpg
à chaque fois que tu faisreduction = reduction[:-1]
oureduction += c
ca te crée une nouvelle chaine et parcourtreduction
pour la remplir avant d'affecter ca à la même adresse.
Le sticker bordel
Le 08 décembre 2018 à 00:41:39 KheyAuxPommes a écrit :
Le 08 décembre 2018 à 00:40:54 PlateauDeSACLAY a écrit :
Et le lru_cache sur des grosses valeurs te donne pas du n2Tu parles de détail d'implémentations là.
Idem quand tu dis que "string[1:-1]" est coûteux.
Tu donne du code donc on regarde ça oui
Et la mémoisation ça peut être très subtile, donc dire "ça marche" ça suffit pas toujours (la elle est triviale à implémenter bien oui)
Le 08 décembre 2018 à 00:39:41 KheyAuxPommes a écrit :
Ma solution pour le palindrome :@lru_cache(None)
def palin(string):
if len(string) < 2:
return string
if string[0] == string[-1] and len(palin(string[1:-1])) == len(string) - 2:
return string
return max(palin(string[:-1]), palin(string[1:]), key=len)7 lignes.
https://image.noelshack.com/fichiers/2017/14/1491667530-risitas-salut.jpg Pas aussi optimal que l'algorithme de Manacher bien sûr, mais petit O(n²) en programmation dynamique.
Pas du O(n2), le len(string[1:-1]) est couteux je crois
Le 08 décembre 2018 à 00:36:02 EnBaDuBlok a écrit :
Voilà mon implémentation en C++ :
int main()
{
string cake;
cake = "tonbordel"
bool b = true;
while (b)
{
b = false;
for(int i = 0; i < cake.size(); i++)
{
if( (cake[i+1] == cake[i] -32 ) || (cake[i] == cake[i+1] - 32 ))
{
cake.erase(i,2);
b = true;
}
}
}
cout << " Taille : " << cake.size();
return 0;
}
Je trouve 9359 de taille, donc je vois pas pourquoi j'ai un résultat différent du tiens l'auteur
Après le erase il faut revenir en arrière de un
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
https://image.noelshack.com/fichiers/2017/31/5/1501863678-risitas596bestreup.png
C'est pas O(n) je pense
Le 08 décembre 2018 à 00:11:43 stuckRANG3 a écrit :
Le 08 décembre 2018 à 00:09:58 KheyAuxPommes a écrit :
Le 08 décembre 2018 à 00:09:27 [Ban2]PTSI-PT a écrit :
[00:04:22] <PlateauDeSACLAY>
Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :
[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratosMais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelleQuand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîneQuand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions ouiJe suis d'accord ça marche et c'est plus simple que ce que j'ai proposé
Oui et c'est O(n).
Tu forces franchement khey c'est ce que j'avais fait a une ligne près
Maintenant donne moi un algo qui trouve le plus grand palindrome dans une chaîne de caractères en temps linéaire
C'est possible ça ?
Le 08 décembre 2018 à 00:08:35 [Ban2]PTSI-PT a écrit :
[00:07:26] <PlateauDeSACLAY>
Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gaucheAu pire on fait 2n opérations
Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)Chaque paire à supprimer dans la liste de départ est le début d'une récursion
Mouais admettons
Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gaucheAu pire on fait 2n opérations
Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)
Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :
[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratosMais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelleQuand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne
Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratosMais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelleQuand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
https://image.noelshack.com/fichiers/2016/41/1476132386-1.png Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
Le 07 décembre 2018 à 23:52:42 Celestin_27cm a écrit :
ca allait bien jusqu'à ce que tu dises "Faites-le en 10 lignes ou moins"https://image.noelshack.com/fichiers/2018/29/6/1532128784-risitas33.png je galere à initialiser une matrice 4x4 avec append
https://image.noelshack.com/fichiers/2018/13/4/1522325846-jesusopti.png
Ca prends une ligne une matrice