Jak odwrócić ciąg w miejsce (lub w miejscu) w JavaScript, gdy jest on przekazywany do funkcji z instrukcji return, bez użycia funkcji wbudowanych ( .reverse()
, .charAt()
etc.)?
javascript
string
reverse
Kobe
źródło
źródło
Odpowiedzi:
Dopóki masz do czynienia z prostymi znakami ASCII i z przyjemnością korzystasz z wbudowanych funkcji, będzie to działać:
Jeśli potrzebujesz rozwiązania, które obsługuje UTF-16 lub inne znaki wielobajtowe, pamiętaj, że ta funkcja da niepoprawne ciągi Unicode lub prawidłowe ciągi, które wyglądają śmiesznie. Zamiast tego możesz rozważyć tę odpowiedź .
[... s] jest świadomy Unicode, mała edycja daje: -
źródło
return [...s].reverse().join("");
może działać.Następująca technika (lub podobna) jest powszechnie stosowana do odwrócenia ciągu w JavaScript:
W rzeczywistości wszystkie dotychczasowe odpowiedzi są odmianą tego wzoru. Istnieją jednak pewne problemy z tym rozwiązaniem. Na przykład:
Jeśli zastanawiasz się, dlaczego tak się dzieje, przeczytaj o wewnętrznym kodowaniu znaków JavaScript . (TL; DR:
𝌆
to symbol astralny, a JavaScript ujawnia go jako dwie oddzielne jednostki kodu).Ale jest więcej:
Dobry ciąg do testowania implementacji odwrotnych ciągów jest następujący :
Dlaczego? Ponieważ zawiera symbol astralny (
𝌆
) (który jest reprezentowany przez pary zastępcze w JavaScript ) i znak łączący (ñ
ostatnimañana
rzeczywistości składa się z dwóch symboli: U + 006E LATIN SMALL LETTER N i U + 0303 COMBINING TILDE).Kolejność pojawiania się par zastępczych nie może być odwrócona, w przeciwnym razie symbol astralny nie będzie już wyświetlany w ciągu „odwróconego”. Dlatego widziałeś te
��
znaki w danych wyjściowych dla poprzedniego przykładu.Znaki łączące zawsze są nakładane na poprzedni symbol, więc zarówno symbol główny (U + 006E LATIN MAŁY LITER N) należy traktować jako znak łączący (U + 0303 ŁĄCZĄCA TILDE) jako całość. Odwrócenie ich kolejności spowoduje sparowanie znaku łączącego z innym symbolem w ciągu. Dlatego przykładowe dane wyjściowe miały
ã
zamiastñ
.Mamy nadzieję, że to wyjaśnia, dlaczego wszystkie dotychczasowe odpowiedzi są błędne .
Aby odpowiedzieć na twoje początkowe pytanie - jak [poprawnie] odwrócić ciąg znaków w JavaScript - napisałem małą bibliotekę JavaScript, która jest w stanie odwrócić ciąg znaków rozpoznający Unicode. Nie ma żadnych problemów, o których właśnie wspomniałem. Biblioteka nazywa się Esrever ; jego kod znajduje się na GitHub i działa w prawie każdym środowisku JavaScript. Jest wyposażony w narzędzie powłoki / plik binarny, dzięki czemu możesz łatwo odwrócić ciągi znaków od terminala, jeśli chcesz.
Jeśli chodzi o część „na miejscu”, zobacz pozostałe odpowiedzi.
źródło
lub
źródło
Szczegółowa analiza i dziesięć różnych sposobów odwracania łańcucha oraz szczegóły dotyczące ich wydajności.
http://eddmann.com/posts/ten-ways-to-reverse-a-string-in-javascript/
Wydajność tych wdrożeń:
Najskuteczniejsze implementacje dla każdej przeglądarki
Oto te implementacje:
Realizacja 1:
Realizacja 2:
Realizacja 3:
Realizacja 4:
Realizacja 5:
Realizacja 6:
Realizacja 7:
Realizacja 8:
Realizacja 9:
Realizacja 10
źródło
Całe „odwrócenie sznurka na miejscu” jest przestarzałym pytaniem dla programistów C, a ludzie, z którymi zostali przesłuchani (zemsty, może?), Zapytają. Niestety jest to część „na miejscu”, która już nie działa, ponieważ łańcuchy w prawie każdym zarządzanym języku (JS, C # itp.) Używają niezmiennych łańcuchów, pokonując w ten sposób całą ideę przenoszenia łańcucha bez przydzielania nowej pamięci.
Chociaż powyższe rozwiązania rzeczywiście odwracają ciąg, nie robią tego bez przydzielania większej ilości pamięci, a zatem nie spełniają warunków. Musisz mieć bezpośredni dostęp do przydzielonego ciągu i móc manipulować jego pierwotną lokalizacją w pamięci, aby móc go odwrócić na miejscu.
Osobiście nienawidzę tego rodzaju pytań podczas wywiadów, ale niestety jestem pewien, że będziemy je widywać przez wiele lat.
źródło
Najpierw użyj,
Array.from()
aby przekształcić ciąg w tablicę, a następnieArray.prototype.reverse()
odwrócić tablicę, a następnieArray.prototype.join()
uczynić z niej ciąg z powrotem.źródło
reverse
logiki.string.split('')
nie działa. Zobacz tę odpowiedź, aby uzyskać więcej wyjaśnień.Array.from('foo 𝌆 bar mañana mañana').reverse().join('') == 'anãnam anañam rab 𝌆 oof'
Array.from('foo 𝌆 bar mañana mañana'.normalize('NFC')).reverse().join('')
stanie się"anañam anañam rab 𝌆 oof"
W ECMAScript 6 możesz jeszcze bardziej odwrócić łańcuch bez korzystania z
.split('')
metody podziału, z operatorem rozkładania w następujący sposób:źródło
('')
string.split('')
jest dla większości ludzi wyraźniejsze niż[...string]
..split('')
ma problem ze znakami z dodatkowych płaszczyzn (par zastępczych w UTF-16), ponieważ dzieli się według jednostki kodowej UTF-16 zamiast punktu kodowego . Operator spreadu iArray.from()
(moje preferencje) nie.Wygląda na to, że jestem 3 lata spóźniony na przyjęcie ...
Niestety nie można, jak już wspomniano. Zobacz Czy ciągi JavaScript są niezmienne? Czy potrzebuję „kreatora ciągów” w JavaScript?
Następną najlepszą rzeczą, jaką możesz zrobić, to utworzyć „widok” lub „opakowanie”, które pobiera ciąg znaków i ponownie implementuje dowolne części interfejsu API łańcucha, którego używasz, ale udawanie, że ciąg jest odwrócony. Na przykład:
Próbny:
Kopacz - następujące czynności wykonuje się w miejscu za pomocą czystej matematyki, odwiedzając każdą postać tylko raz i tylko w razie potrzeby:
Daje to znaczne oszczędności, jeśli zastosuje się go do bardzo dużego sznurka, jeśli bierzesz tylko jego stosunkowo niewielki kawałek.
To, czy jest tego warte (w porównaniu z odwróceniem kopii, jak w większości języków programowania), zależy w dużej mierze od przypadku użycia i wydajności ponownego wdrożenia łańcucha API. Na przykład, jeśli wszystko, czego chcesz, to manipulowanie indeksem łańcuchowym lub małe
slice
s lubsubstr
s, pozwoli to zaoszczędzić miejsce i czas. Jeśli jednak planujesz drukować duże odwrócone wycinki lub podciągi, oszczędności mogą być naprawdę niewielkie, nawet gorsze niż w przypadku wykonania pełnej kopii. Twój „odwrócony” ciąg również nie będzie miał tego typustring
, chociaż możesz być w stanie go sfałszować za pomocą prototypowania.Powyższa implementacja demonstracyjna tworzy nowy obiekt typu ReversedString. Jest prototypowany, a zatem dość wydajny, z minimalnym nakładem pracy i minimalnym nakładem miejsca (definicje prototypów są wspólne). Jest to leniwa implementacja z odroczonym krojeniem. Ilekroć wykonasz funkcję podobną do
.slice
lub.reversed
, wykona ona matematykę indeksu. Wreszcie po wyodrębnieniu danych (przez niejawne wywołanie.toString()
lub.charCodeAt(...)
coś w tym stylu), zastosuje je w „inteligentny” sposób, dotykając możliwie najmniej danych.Uwaga: powyższy ciąg API jest przykładem i może nie zostać idealnie zaimplementowany. Możesz także użyć tylko 1-2 funkcji, których potrzebujesz.
źródło
Istnieje wiele sposobów odwrócenia ciągu w JavaScript. Zapisuję trzy preferowane sposoby.
Podejście 1: Korzystanie z funkcji odwrotnej:
Podejście 2: Pętla przez postacie:
Podejście 3: Korzystanie z funkcji zmniejszania:
Mam nadzieję, że to pomoże :)
źródło
Podczas wywiadu poproszono mnie o odwrócenie łańcucha bez użycia zmiennych lub metod rodzimych. To moja ulubiona implementacja:
źródło
slice
? : - /Array.prototype.reverse()
.Można to zrobić na wiele sposobów, możesz sprawdzić następujące,
1. Tradycyjne dla pętli (inkrementacja):
2. Tradycyjne dla pętli (zmniejszanie):
3. Korzystanie z pętli for-of
4. Używając metody tablicowej forEach / high order:
5. Standard ES6:
6. Najnowszy sposób:
7. Możesz również uzyskać wynik, korzystając z następujących metod,
źródło
W ES6 masz jeszcze jedną opcję
źródło
To jest najłatwiejszy sposób
źródło
Array.prototype.reverse()
to w najprostszy sposób, stąd najpopularniejsza odpowiedź. Oczywiście wymagałoby to wcześniejszej znajomości JavaScript.LUB
// Wyjście: „gnirts elpmas”
źródło
[...str]
.Wiem, że to stare pytanie, na które dobrze odpowiedziano, ale dla własnego rozbawienia napisałem następującą funkcję odwrotną i pomyślałem, że podzielę się nią na wypadek, gdyby była przydatna dla kogokolwiek innego. Obsługuje zarówno pary zastępcze, jak i łączenie znaków:
Wszystkie rekwizyty do Mathiasa, Punycode i różnych innych odniesień do nauki mnie o złożoności kodowania znaków w JavaScript.
źródło
Nie możesz, ponieważ ciągi JS są niezmienne. Krótkie rozwiązanie nie na miejscu
Pokaż fragment kodu
źródło
Jeśli nie chcesz używać żadnej wbudowanej funkcji. Spróbuj tego
źródło
Prawdziwa odpowiedź brzmi: nie można odwrócić na miejscu, ale można utworzyć nowy ciąg znaków, który jest odwrotny.
Ćwiczenie z rekurencją: czasami, kiedy idziesz na rozmowę kwalifikacyjną, ankieter może zapytać cię, jak to zrobić za pomocą rekurencji, i myślę, że „preferowaną odpowiedzią” może być: „Wolałbym tego nie robić, ponieważ może łatwo spowodować przepełnienie stosu ”(ponieważ tak jest
O(n)
raczej niżO(log n)
. Jeśli tak jestO(log n)
, uzyskanie przepełnienia stosu jest dość trudne - 4 miliardy przedmiotów można obsłużyć przy poziomie stosu 32, ponieważ 2 ** 32 to 4294967296. Ale jeśli takO(n)
, to może łatwo przepełnić stos.Czasami ankieter wciąż pyta: „właśnie jako ćwiczenie, dlaczego nie napiszesz go za pomocą rekurencji?” A oto:
testowe uruchomienie:
wynik:
Aby spróbować uzyskać przepełnienie stosu, zmieniłem
1000
na10000
w Google Chrome i zgłosił:źródło
Same ciągi są niezmienne, ale możesz łatwo utworzyć odwróconą kopię za pomocą następującego kodu:
źródło
źródło
Mała funkcja, która obsługuje zarówno łączenie znaków diakrytycznych, jak i 2-bajtowych:
Aktualizacja
Pełniejsza lista łączenia znaków diakrytycznych to:
źródło
isCombiningDiacritic
funkcji, aby uwzględnić wszystkie 316 zakresów; nie krępuj się, wprowadzając tę zmianę, ponieważ wydaje się, że masz pod ręką dane.źródło
bez konwersji łańcucha na tablicę;
użycie Array.reverse bez konwersji znaków na punkty kodowe;
źródło
var c = array[i-1]; array[i-1] = array[i]; array[i] = c;
nie wymaga konkatenacji pary kodów. Również pętla for powinna zacząć się od 1.'\ud83c\ud83c\udfa5'.reverse()
- będzie wyświetlać to samo co wejście. Dodanie++i;
wif
instrukcji powinno to naprawić.'a\u0303bc'.reverse() === 'cba\u0303'
powinna zwrócić wartość true.Myślę, że String.prototype.reverse to dobry sposób na rozwiązanie tego problemu; kod jak poniżej;
źródło
Korzystanie z funkcji Array,
źródło
źródło
Moja własna oryginalna próba ...
http://jsbin.com/bujiwo/19/edit?js,console,output
źródło
Trzymaj to SUCHO i po prostu głupie !!
źródło
OK, dość prosty, można utworzyć funkcję, za pomocą prostego pętli zrobić ciąg wsteczny dla Ciebie bez użycia
reverse()
,charAt()
etc tak:Na przykład masz ten ciąg:
Utwórz taką funkcję, nazywam ją
reverseString
...Możesz to nazwać tak:
Rezultatem będzie:
źródło
Najlepsze sposoby na odwrócenie ciągu w JavaScript
1) Array.reverse:
Prawdopodobnie myślisz, poczekaj, myślałem, że cofamy ciąg, dlaczego używasz metody Array.reverse. Metodą String.split konwertujemy nasz ciąg znaków na tablicę znaków. Następnie odwracamy kolejność każdej wartości w tablicy, a następnie ostatecznie konwertujemy Array z powrotem na String za pomocą metody Array.join.
2) Zmniejszanie pętli while:
Chociaż dość szczegółowe, to rozwiązanie ma swoje zalety w stosunku do rozwiązania pierwszego. Nie tworzysz tablicy i po prostu konkatenujesz ciąg oparty na znakach z ciągu źródłowego.
Z punktu widzenia wydajności prawdopodobnie przyniosłoby to najlepsze wyniki (choć niesprawdzone). Jednak w przypadku bardzo długich ciągów wzrost wydajności może wypaść z okna.
3) Rekurencja
Uwielbiam to, jak proste i jasne jest to rozwiązanie. Widać wyraźnie, że metody String.charAt i String.substr są używane do przechodzenia przez inną wartość, wywołując się za każdym razem, dopóki łańcuch nie będzie pusty, z którego trójka zwróci pusty ciąg zamiast używać rekurencji do wywołania siebie . Prawdopodobnie dałoby to drugą najlepszą wydajność po drugim rozwiązaniu.
źródło