Ceci est une question d'entretien Vous recherchez une meilleure solution optimale pour couper plusieurs espaces d'une chaîne. Cette opération doit être opérationnelle à la place.
input = "I Like StackOverflow a lot" output = "I Like StackOverflow a lot"
11 Réponses :
Gardez deux index: le prochain point disponible pour mettre une lettre dans (dire, juste boucle sur tous les caractères avec i pense cela fonctionnerait sur place ... i ), et l'index actuel que vous examinez (disons, j ).
j , et chaque fois que vous voyez une lettre, copiez-le sur index i , puis incrément i . Si vous voyez un espace qui n'a pas été précédé d'un espace, copiez également l'espace.
Assurez-vous que le chèque "n'a pas été précédé d'un espace" ne vérifie pas simplement si s [j-1] == '' parce que la matrice est modifiée au fur et à mesure que vous allez. Il est plus sûr de maintenir un drapeau qui permet de déterminer si le personnage précédent que vous avez vu était un espace.
@Kannan: Oui, je pensais en fait à écrire cela, mais je laisse le lecteur la comprendre pour lui-même. ;)
@Kannan: Ce n'est pas réellement nécessaire dans ce cas. Il suffit de vérifier s [j-1] == '' est suffisant.
utilise test: https://ideone.com/itqxb
@Matthieu: Je n'appellerais pas cet abus - l'algorithme STL est parfaitement conçu pour ce type de situation. Exiger une classe de fonctions est certes maladroitement, mais c'est une limitation assez courante des algorithmes stl pré-C ++ 0x.
@Eclipse: Je l'appelle un abus parce qu'il est un peu extrait de la version du fonctionnement, qui utilise simplement == . Ici, le foncteur change la sémantique, puisque deux articles comparables à égale ne sont pas nécessairement fusionnés ... Je suis plutôt étonné par l'astuce, surtout parce qu'un simple changement «sémantique» sur le foncteur a permis de détourner l'algorithme :)
@Matthieu M: Ce n'est rien comparé à ce que std :: inner_product peut faire lorsqu'il est appelé avec des foncteurs choisis de manière créative (comme explorés par les programmeurs APL il y a des décennies)
C'est une grande utilisation d'un algorithme de bibliothèque standard C ++!
Ici, il n'utilise que STDIO:
#include <stdio.h>
int main(void){
char str[] = "I Like StackOverflow a lot";
int i, j = 0, lastSpace = 0;
for(i = 0;str[i]; i++){
if(!lastSpace || str[i] != ' '){
str[j] = str[i];
j++;
}
lastSpace = (str[i] == ' ');
}
str[j] = 0;
puts(str);
return 0;
}
Je voudrais juste aller avec ceci:
@Vjo: soin d'expliquer le commentaire? L'algorithme (tout en pouvait être inefficace en ce qu'il copie tous les éléments valides du tableau, qu'il soit nécessaire de déménager ou non - même s'ils restent au même endroit - semble correct.
@David Oui, cela fonctionne correctement, sauf dans le boîtier de la chaîne vide. Pouvez-vous deviner quelle est la sortie lorsque l'ARR contient une chaîne vide?
@Vjo, il imprime une chaîne vide. Qu'est-ce que cela irait-il?
@eda ah, à droite. Si le premier chèque échoue, la seconde ne sera pas exécutée du tout. Désolé pour la confusion
A C ++ 0X - Solution à l'aide d'un lambda au lieu d'un objet de fonction régulier. Comparez à la solution de Cubbi.
#include <string>
#include <algorithm>
int main()
{
std::string str = "I Like StackOverflow a lot";
str.erase(std::unique(str.begin(), str.end(),
[](char a, char b) { return a == ' ' && b == ' '; } ), str.end() );
}
Au lieu de a == '' On peut utiliser Isspace (a) pour être plus cohérent.
Je proposerais une petite machine à états (juste un simple instruction de commutation). Parce que si l'intervieweur est comme moi, la première amélioration qu'ils vous demanderont de faire est de couper complètement les espaces de début ou de fuite, de sorte que: se transforme en: au lieu de: Il s'agit d'une modification très simple à une conception d'état-machine, et pour moi, il semble plus facile de comprendre la logique d'état-machine en général sur une boucle codée «simple», même si cela prend quelques lignes de code supplémentaires qu'une boucle directe. et si vous soutiendrez que les modifications apportées à La boucle directe ne serait pas trop mauvaise (ce qui peut être raisonnablement argumenté), puis je (comme l'intervieweur) jetterait pour que je souhaite aussi que les zéros de noms de chiffres soient coupés. sur le Autre main, beaucoup d'intervieweurs pourraient réellement détester une solution d'état-machine comme étant «non optimale». Je suppose que cela dépend de ce que vous essayez d'optimiser.
Cela aiderait les gens à se rapporter à cet avis si vous avez mis en œuvre les deux conséquences, les implications ont été prises tangibles ;-).
Très belle amélioration. Et être juste, il a été demandé :). Ce serait bien si vous pouvez donner quelques algo pour cela aussi ...
La réduction de plusieurs espaces signifie également qu'un espace doit toujours être suivi d'un caractère non espace.
int j = 0;
int k=0;
char str[] = "I Like StackOverflow a lot";
int length = strlen(str);
char str2[38];
for (int i = 0; i < length; i++)
{
if (str[i] == ' ' && str[i+1] == ' ')
continue;
str2[j] = str[i];
j++;
}
str2[j] =NULL;
cout<<str2;
Avez-vous testé avec une chaîne se terminant par ''? str [i + 1] devrait échouer quand je pointe de la dernière fois
La question posée pour une version en place et ces copies à un tampon séparé (STR2). De plus, STR2 est alloué statiquement sur la pile et déborde de certains intrants - ce n'est pas une bonne idée. Et vous avez déclaré une variable 'K' que vous n'utilisez pas.
void trimspaces(char * str){
int i = 0;
while(str[i]!='\0'){
if(str[i]==' '){
for(int j = i + 1; j<strlen(str);j++){
if(str[j]!=' '){
memmove(str + i + 1, str + j, strlen(str)-j+1);
break;
}
}
}
i++;
}
}
Variante fonctionnelle dans HASKELLL:
import Data.List (intercalate) trimSpaces :: String -> String trimSpaces = intercalate " " . words
Il s'agit d'une implémentation très simple consistant à supprimer des espaces supplémentaires supplémentaires.
#include <iostream>
std::string trimExtraWhiteSpaces(std::string &str);
int main(){
std::string str = " Apple is a fruit and I like it . ";
str = trimExtraWhiteSpaces(str);
std::cout<<str;
}
std::string trimExtraWhiteSpaces(std::string &str){
std::string s;
bool first = true;
bool space = false;
std::string::iterator iter;
for(iter = str.begin(); iter != str.end(); ++iter){
if(*iter == ' '){
if(first == false){
space = true;
}
}else{
if(*iter != ',' && *iter != '.'){
if(space){
s.push_back(' ');
}
}
s.push_back(*iter);
space = false;
first = false;
}
}
return s;
}
Voulez-vous dire "en place" au lieu de "en mémoire"?
@MAK: Oui, merci de le pointer.